Поиск центра набора точек для сортировки по часовой стрелке?

Question

Я хочу сортировать вектор точек по часовой стрелке для формирования многоугольника, но для этого нужен соответствующий центр. Я попробовал метод средних значений, но некоторые из них не отсортировались правильно. Каков правильный способ найти центр, который будет работать при сортировке точек по часовой стрелке?

Это провал на вогнутых частях

Благодаря

Вот картина:

зеленый круг в центре.

Он должен выглядеть следующим образом:

Answer 1

Понятие «сортировка по часовой стрелке» не определено, если у вас нет предварительно заданной центральной точки.

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

Кроме того, поиск центра, который позволит вам повторно создать исходный многоугольник с помощью сортировки по CW (или CCW), возможен только для специального класса полигонов: так называемых star-shaped полигонов. Основное свойство звездообразного многоугольника состоит в том, что можно найти точку внутри многоугольника, из которой «внутреннее» многоугольник является «наблюдаемым» (я надеюсь, что без определения ясно, что означает «наблюдаемое»).

Если ваш многоугольник не имеет звездной формы, то такой центр не существует. И по этой причине невозможно повторно создать исходный многоугольник с помощью сортировки по CW.

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

Answer 2

См Barycenter. Может быть, это то, что вы ищете

Answer 3

Принимая любой как центр, вы должны быть в состоянии определить расстояние и угол для всех точек в наборе, а сортировка по углу проста после этого. Тем не менее, точка, которую вы выбираете как центр, будет влиять на порядок сортировки, поэтому трудно понять, что должен делать «правильный» порядок, пока вы не выберете точку в качестве центра.

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

Answer 4

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

Это не простая задача, но здесь эвристический, которые должны хорошо работать:

1. Для каждой точки, найти следующую ближайшую точку. Это определяет набор потенциальных связей.
2. Добавить наибольшее возможное соединение с многоугольником.
3. Повторите 1-2, но проигнорируйте уже созданные соединения и точки, которые уже имеют два соединения.

Это только эвристика, а не решение. Я не уверен, что даже гарантированно создаст многоугольник.