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

Question

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

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

Answer 1

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

Answer 2

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

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

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

EDIT

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

а не:

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

Answer 3

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

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

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

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