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

Question

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

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

Answer 1

Вы хотите, чтобы вы заказали результат P1, P2, ... P13?

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

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

EDIT

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

и нет:

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

Answer 2

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

Answer 3

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

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

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

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