Ordinamento punti poligono

Question

Ho un poligono convesso ABCDE ... (può avere qualsiasi numero di punti). Ho bisogno di ordinare tutti i suoi vertici in modo che nessuno dei bordi si intersecano.
esempio: bordi

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

Questo poligono per ABCD è intersecano. tuttavia nell'ordine ABDC:

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

Nessuno dei bordi si intersecano in modo che l'ABDC sia l'uscita prevista.

Come posso fare questo?

Answer 1

Assumendo i punti sono tutti sulla convesso del poligono, è possibile utilizzare il seguente:

1. scegliere i due punti estremi con il minimo ed il valore massimo X, (chiamarli X _min e X _max) e tracciare la linea tra di loro. Nel caso in cui siano presenti più punti con lo stesso valore X agli estremi, selezionare X _min con il valore Y minimo e X _max con il valore Y massimo.
2. Spalato l'elenco dei punti in due elenchi secondari in cui tutti i punti sotto la linea di collegamento X _min e X _max sono in una lista e tutti quelli sopra quella linea sono in un altro. Includere X _min nella prima lista e X _max nella seconda.
3. Ordinare il primo elenco in ordine crescente di valore X. Se hai più punti con lo stesso valore X, ordinali in valore Y crescente. Questo dovrebbe accadere solo per i punti con lo stesso componente X di X _max poiché il poligono è convesso.
4. Ordinare il secondo elenco in ordine decrescente di valore X. Di nuovo, ordina in valore Y decrescente nel caso di più punti con lo stesso valore X (che dovrebbe accadere solo per i punti con X componente X _min.
5. Aggiungi le due liste insieme (non importa quale sia il primo .)

Answer 2

scegliere due punti sul poligono. il punto medio della linea sarà contenuto all'interno di quel poligono. Lascia che questo punto sia M.

Quindi, ordina i punti in base all'angolo basato su M (lungo l'asse X), interrompendo la degenerazione in base alla distanza da M. Iterando in tale ordine si assicura che non si intersechino due bordi.