Как соединить рандомные точки на координатной плоскости в многоугольник?

Question

[pinkclouds]

На координатной плоскости x,y есть рандомно разбросанные точки с известными координатами, количество которых не менее трех. Нужно высчитать, как точки необходимо соединить друг с другом, чтобы получить многоугольник. ( Если расположение точек это позволяет )
Если соединять точки рандомно, то фигура может получится разрезанной ( Пример привел на скрине, надо понять, что провести требуется именно вектор 1, а не вектор 2)
Может существуют какие-то формулы или подходы. Желательно эффективные ( Чтобы миновать полный перебор всевозможных соединений )

Answer 1

[Wataru]

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

Надо точки как-то отсортировать. Например, берете самую нижнюю, из всех таких самую левую. Сортируете все оставшиеся точки по углу, относительно этой (по значению atan2(yi-y0, xi-x0)), при равенсве угла по расстоянию (не важно по возрастанию или убыванию). Потом в таком порядке их соединяйте, пересечений не будет.

В примере из вопроса оно как раз отсортирует их как на картинке.

Edit, а еще, можно вместо atan сравнивать углы через векторное произведение. Если входные данные - целые точки, то вообще все вычисления будут в целых переменных.

Comments

[pinkclouds]

Очень хорошо работает. Спасибо

[U235U235]

триангуляция Дирихле это не то что требуется?..

[Wataru]

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

Answer 2

[Vindicar]

Твоя задача называется выпуклая оболочка - convex hull.
Попробуй поискать по этим терминам.

Answer 3

[alex_ak1]

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