Найти центр набора точек, чтобы отсортировать их по часовой стрелке?

Question

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

Не работает на вогнутых частях

Спасибо

Вот изображение:

Зеленый круг - это центр.

Это должно выглядеть примерно так:

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

См. Барицентр . Может быть, это то, что вы ищете