У меня выпуклый полигон ABCDE... (он может иметь любое количество точек). Мне нужно отсортировать все его вершины так, чтобы ни одна из рёбер не пересекалась.
пример:
A _____ B
\ /
\ /
X
/ \
/___\
C D
Этот полигон в порядке ABCD имеет пересекающиеся рёбра, однако в порядке ABDC:
A _____ B
| |
| |
| |
| |
|___|
C D
Ни одна из рёбер не пересекается, поэтому ABDC является ожидаемым выходом.
Как это сделать?