Сортировка точек полигона

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

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

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

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

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

Как это сделать?

10
задан andand 10 September 2011 в 05:58
поделиться