Сортировка точек в 2D пространстве

Предположим, что случайные точки P1 до P20, рассеянные в плоскости. Тогда есть способ отсортировать эти точки в часовом или против часовой мутации. enter image description here

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

Ответы

Ответ 1

Вы утверждаете, что хотите получить упорядоченный результат P1, P2,... P13?

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

В практическом смысле взгляните на OpenCV documentation - вызов convexHull с помощью clockwise=true дает вам вектор точек в том порядке, в котором вы хотите. Ссылка предназначена для С++, но там есть API C и Python. Другие пакеты, такие как Matlab, должны иметь аналогичную функцию, так как это общая геометрическая проблема.

ИЗМЕНИТЬ

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

enter image description here

и не:

enter image description here

В обеих диаграммах зеленый - это исходный выпуклый корпус, другие цвета - обваленные области.

Ответ 2

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

Ответ 3

Найдите правую часть этих точек (в O(n)) и отсортируйте по углу относительно этой точки (O(nlog(n))).

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

Изменить: На самом деле это просто невозможно, так как многоугольное представление (то есть выходной порядок) ваших точек неоднозначно. Алгоритм выше будет работать только для выпуклых многоугольников, но он может быть расширен и для работы с звездообразными многоугольниками (вам нужно выбрать другую "опорную точку" ).

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