Сортировка точек многоугольника

Question

У меня выпуклый многоугольник ABCDE ... (он может иметь любое количество точек).Мне нужно отсортировать все его вершины, чтобы ни одно из ребер не пересекалось.
пример:

A _____ B
  \   /
   \ /
    X
   / \
  /___\
C       D

Этот многоугольник в порядке ABCD имеет пересекающиеся ребра.однако в порядке ABDC:

A _____ B
  |   |
  |   |
  |   |
  |   |
  |___|
C       D

Ни одно из ребер не пересекается, поэтому ABDC является ожидаемым выводом.

Как я могу это сделать?

Answer 1

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

1. Выберите две крайние точки с минимальным и максимальным значением X (назовите их X _min и X _max ) и проведите линию между ними. В случае, когда у вас есть несколько точек с одним и тем же значением X в крайних значениях, выберите X _min с минимальным значением Y и X _max с максимальным значением Y.
2. Разбить список точек на два подсписка, где все точки под линией, соединяющей X _min и X _max , находятся в одном списке, а все те, что выше этой линии, находятся в другой. Включите X _min в первый список и X _max во второй.
3. Сортировка первого списка в порядке возрастания значения X. Если у вас есть несколько точек с одинаковым значением X, сортируйте их по возрастанию. Это должно происходить только для точек с тем же компонентом X, что и X _max , поскольку многоугольник выпуклый.
4. Сортировка второго списка в порядке убывания значения X. Опять же, сортировка по убыванию значения Y в случае нескольких точек с одинаковым значением X (что должно происходить только для точек с компонентом X X _min .
5. Добавьте два списка вместе (не важно, какой из них первый).

Answer 2

выберите две точки на многоугольнике.средняя точка линии будет находиться внутри этого многоугольника.Пусть эта точка равна M.

Затем сортируйте точки по углу, основанному на M (вдоль оси X), ломая вырождение на основе расстояния от M. Повторение в таком порядке гарантирует, что никакие два ребра не пересекаются.