По заданному вектору точек (возможно, не по порядку) найдите многоугольник (не выпуклый корпус)

Question

У меня сейчас есть вектор точек

vector<Point> corners;

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

Теперь у меня есть функция, которая, учитывая вектор точек, соединяет их и рисует замкнутую фигуру. Однако мне нужно дать этой функции последовательность точек в том порядке, в котором они должны быть связаны. Может кто-нибудь предложить способ, которым я мог бы отсортировать эти пункты в правильном порядке? Они образуют очень простой вогнутый многоугольник, а не выпуклый корпус. Алгоритм нахождения центральной точки среди всех (7) точек также был бы полезен:)

Answer 1

Не существует уникального решения для вогнутого многоугольника:

Выпуклый многоугольник можно найти уникально как выпуклую оболочку точек (если вы знаете, что точки образуют выпуклый многоугольник).

Answer 2

Заданный набор точек, как правило, можно объединить многими способами, чтобы сформировать несамопересекающийся многоугольник. Вам может не повезти, если у вас нет дополнительной информации о видах полигонов, которые могут представлять точки.

Answer 3

1. Эвристика для определения формы

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

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

Оба метода на самом деле не работают вообще, они даже не гарантируют избежание пересечений. Вы можете попытаться решить эту проблему путем обратного отслеживания, если вы обнаружите явную ошибку (например, пересечение), затем вернитесь к последней точке решения и воспользуетесь подходом «второй лучший», ....

Но опять же, поскольку решение не уникально, не ожидайте слишком многого от этой эвристики.

2. Среднее по вершинам

Среднюю точку для вершин легко вычислить. Просто сложите все баллы вместе и разделите на количество баллов, которое вы только что добавили, это среднее значение. Что вас, вероятно, больше всего интересует, так это центральная точка в смысле «центра масс», см. Ниже.

3. Центральная точка

Чтобы определить центр масс, сначала нужно определить форму. Это означает, что вы должны сделать что-то вроде шага 1.

Легко реализуемый метод для вычисления центральной точки с учетом многоугольника.

• Поместите ограничивающий прямоугольник вокруг многоугольника.
• Случайно генерировать точки внутри ограничительной рамки.
• Для каждого из этих пунктов определите, находится ли он внутри ограничительной рамки, если нет, то выбросьте его. Чтобы определить, находится ли точка внутри произвольного многоугольника, используйте тест ray .
• Для всех сохраненных вами точек примените подход 2. Средняя точка этих точек является хорошим приближением к центральной точке.