Сортировка списка точек в многоугольник
У меня есть набор очков. Этот набор точек определяет (невыпуклый) многоугольник, но он не упорядочен.
Поскольку он не упорядочен, я не могу просто рисовать от точки к точке, чтобы нарисовать его границу. Как я могу отсортировать это так, как я могу пройти через этот список точек и нарисовать многоугольник?
Моя первая идея состояла в том, чтобы использовать выпуклый корпус, но мои многоугольники, в большинстве случаев, вогнутые.
3 ответа
Я не думаю, что есть четко определенное решение для этого. Рассмотрим пять моментов, подобных этому:
. .
.
. .
Какой полигон был бы здесь правильным?
Вы должны упорядочить точки, чтобы обойти многоугольник с внутренним пространством слева (или справа) при перемещении из точки в точку. Выпуклый или вогнутый, это правильный подход.
Но знания точек недостаточно. Вы также должны знать связность каждого краевого сегмента. Зная это, вы можете начать в любой точке и идти по периметру, пока не достигнете начальной точки снова.
Я не уверен, что это самый быстрый способ, но, похоже, работает.
Вся идея состоит в том, чтобы соединить точки, используя отрезки линии, которые не пересекаются (за исключением точек, и это немного сложнее определить, чем вы думаете). Итак, начните с исходного несортированного списка, соедините их по порядку - образуя замкнутый путь, который может иметь много пересечений - и затем устраняйте пересечения по одному, обращая подпоследовательности точек в списке.
Предположим, мы начинаем с [abcdefgh] и обнаруживаем, что ребро bc пересекает ребро gh. Мы обращаемся к последовательности cg, чтобы получить новый список: [a b g f e d c h]. Два ребра были удалены и два новых созданы; остальные не потревожены (хотя у некоторых направление движения изменилось).
Я не смог найти ни одного случая, в котором этот процесс мог бы выполняться вечно (то есть список вернулся бы в предыдущее состояние), ни доказательства того, что это не может произойти.