Сортировка списка точек в многоугольник

Question

У меня есть набор очков.Этот набор точек определяет (невыпуклый) многоугольник, но он не упорядочен.

Поскольку он не упорядочен, я не могу просто рисовать от точки к точке, чтобы нарисовать его границу.Как я могу отсортировать его так, как я могу пройти по этому списку точек и нарисовать многоугольник?

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

Answer 1

Я не думаю, что есть четко определенное решение для этого.Рассмотрим пять моментов, подобных этому:

.   .
  .
.   .

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

Answer 2

Я не уверен, что это самый быстрый способ, но, похоже, он работает.

Вся идея состоит в том, чтобы соединить точки, используя отрезки, не пересекающиеся (кроме точек, и этонемного сложнее определить, чем вы думаете).Поэтому начните с исходного несортированного списка, соедините их по порядку - образуя замкнутый путь, который может иметь много пересечений - и затем устраните пересечения по одному, изменив подпоследовательности точек в списке.* Предположим, мы начинаем с [abcdefgh] и обнаруживаем, что край bc пересекает край gh.Мы обращаемся к последовательности cg, чтобы получить новый список: [abgfedch].Два ребра были удалены и два новых созданы;остальные не потревожены (хотя у некоторых направление было изменено).

Мне не удалось найти случай, когда этот процесс будет выполняться вечно (то есть список вернется в предыдущее состояние),ни доказательство того, что это не может произойти.

Answer 3

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

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