sortowania punktów wielokąta za

Question

Mam wielokąt wypukły ABCDE ... (może mieć dowolną liczbę punktów). Muszę posortować wszystkie jego wierzchołki, aby żadna z krawędzi nie przecinała się.
przykład:

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

To wielokąt w celu ABCD ma przecinające się krawędzie. jednak w zamówieniu ABDC:

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

Żadna z krawędzi nie przecina się, więc oczekiwane jest ABDC.

Jak mogę to zrobić?

Answer 1

Zakładając, że punkty są na wypukłej swojego wielokąta, można użyć następujących:

1. Odbiór dwóch skrajnych punktów z min i wartości max X (nazwijmy je X _min i X _max) i narysuj linię między nimi. W przypadku, gdy trzeba kilku punktów o tej samej wartości X w ekstremalnych odebrać X _min minimalnej wartości X i Y _max o maksymalnej wartości y.
2. podziału listę punktów na dwa podstrumienie, gdzie liście wszystkich punktów poniżej linii łączącej X _min i X _max są w jednej liście i wszystkich osób powyżej tej linii są w innym. Obejmują X _min z pierwszej listy i X _max na sekundę.
3. Sortuj pierwsza lista w kolejności rosnącej wartości X. Jeśli masz wiele punktów o tej samej wartości X, posortuj je w rosnącej wartości Y. To powinno się zdarzyć tylko w przypadku punktów o tym samym składniku X, co X _maks., ponieważ wielokąt jest wypukły.
4. Sortuj drugą listę w porządku malejącym według wartości X. Ponownie, posortuj malejącą wartość Y w przypadku wielu punktów o tej samej wartości X (co powinno się zdarzyć tylko dla punktów z komponentem X X _min.
5. Dołącz dwie listy razem (nie ma znaczenia, która jest pierwsza .)

Answer 2

wybrać dwa punkty na wieloboku. środkowy punkt linii będzie zawarty w tym wielokącie. Niech to będzie M.

Następnie posortuj punkty na podstawie kąta bazującego na M (wzdłuż osi X), przełamując degenerację w oparciu o odległość od M. Iteracja w tej kolejności zapewnia, że ​​żadne dwie krawędzie nie będą się przecinały.