Как обвести множество точек на карте?

Question

[Jhonnyman]

Есть множество точек. Как обвести это множество по крайним точкам?
Желательно, чтобы можно было указать максимальное расстояние до соседней точки.

Вот такой полигон хотелось бы получить.


Может есть название у алгоритма?

Comments

[Сергей Соколов]

convex hull, nearest neighbor

Answer 1

[Wataru]

Вот алгоритм выделения граней планарного графа: https://e-maxx.ru/algo/facets

Сначала вам придется попересекать отрезки друг с другом и получить граф: вершины - точки пересечения и концы отрезков, ребра - куски отрезков. Потом выделяете алгоритмом выше внешнюю и внутренние грани.

Потом их сглаживаете. Внешнюю грань - наружу, внутренние - внутрь. Тут придется как-то эвристически действовать. Например, берете любую точку на контуре, если две ее соседние достаточно близки, то выкидываете текущую точку. Если внутренняя грань становится достаточно маленькой по площади - выкидываете ее целиком.

Upd: Дополнение - выбрасывать можно только точки, "вогнутые" внутрь полигона, такие, что их удаление только сделает внешнюю часть больше, а внутреннюю меньше.

В итоге, если удачно подобрать границы в алгоритме выше, то получится примерно как у вас на картинке.