Как отсортировать произвольные точки так, чтобы при проведении линии через них последовательно получился многоугольник?

Question

[antonwx]

Есть несколько точек в двухмерном пространстве, совершенно произвольные могут быть (но не могут совпадать).
Нужно отсортировать их так, чтобы при последовательном проведении линии через все эти точки получился - не самопересекающийся многоугольник.
Как это сделать? Существует ли вообще алгоритм, который способен на подобное?
Ну или подойдёт какая-нибудь библиотека на C# или C++, которая просто возьмёт и сделает это.

Comments

[Wataru]

Надо получить выпуклый многоугольник, или можно что-то типа звезды получать?

[ThunderCat]

Wataru, при произвольном расположении точек не всегда возможно построить выпуклый многоугольник (пример - треугольник с точкой в центре).

[antonwx]

Wataru, не увидел ваш комментарий, что-то типа звезды можно, сейчас буду пробовать что предложили

Answer 1

[Rsa97]

Точки, соединённые в любом порядке, дадут многоугольник. Он может быть самопересекающимся или невыпуклым, но у вас в задаче никаких ограничений нет.

Comments

[antonwx]

Должен не быть самопересекающимся, добавлю в описание

Answer 2

[Adamos]

Банально-наколенный вариант: находим среднюю арифметическую координату, пересчитываем координаты всех точек в радиальные относительно этой средней, сортируем по углу (а при равенстве углов - по удаленности) - и соединяем в этом самом порядке.

Comments

[Wataru]

Удобнее сортировать относительно крайней точки (например - самой левой из самых нижних). Тогда все точки лежат в одной полуплоскости и тогда не надо городить тригонометрию, чтобы получать углы - точки можно сравнивать векторным произведением.

[Adamos]

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

[Alexandroppolus]

Adamos, векторное произведение - это 2 умножения. Итого O(n * ln(n)) умножений. Тут вопрос, что быстрее - один арккотангенс, или ln(n) умножений :-)
Как вариант, можно не разводить тригонометрию, а посчитать котангенсы (вроде их, если опираемся на самую левую из самых нижних) - просто одну координату делим на другую. Там правда отдельно надо обрабатывать особые случаи, когда угол равен 0 (а котангенс равен бесконечности).
Но это надо создавать отдельный массив структур, возиться с ним... Я бы забил и оставил векторные умножения "на лету".

[Wataru]

Adamos, Векторные умножения будут чуть-чуть медленнее в сравнении и сильно быстрее в преподготовке. Но главное их достоинство - если входные координаты целые, то все можно сделать в целых числах и не парить мозг насчет точности. Плюс не надо выделять память и хранить угол вместе с точками.

Answer 3

[Alexandroppolus]

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

Answer 4

[Akina]

Возможный алгоритм.

Этап 1.

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

Этап 2.

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

В итоге получаем несамопересекающийся многоугольник. Обходим его в любом направлении от любой из вершин - полученный список и есть требуемый ответ.

Answer 5

[ThunderCat]

Самый правильный путь - найти геометрический центр скопления, и от него перейти в радиальные координаты, двигаясь по кругу соединить все точки.
Второй, и как мне кажется на порядок более простой вариант - находим геометрический центр скопления, делим область на 4 части осями х и у, далее сверху вниз проходим каждую из них, соединяя каждую нижележащую с предыдущей (полинейное сканирование). Крайние точки областей соединяем - профит.