排列多邊形的點

Question

我有一個凸多邊形ABCDE ...（它可以有任意數量的點）。我需要對它的所有頂點進行排序，這樣所有的邊都不會相交。
例如：

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

，在ABCD順序多邊形具有交叉的邊緣。但是在ABDC順序中：

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

沒有邊相交，因此ABDC是預期輸出。

我該怎麼做？

Answer 1

假設你的點都在你的多邊形的凸包，您可以使用以下命令：

1. 選擇與最小和最大X值的兩個極端點，（叫他們X _分鐘和並繪製它們之間的界限。如果您在極端情況下有多個具有相同X值的點，請選擇帶有最小Y值的X _分鐘以及帶有最大Y值的X _max。
2. 拆分點的列表到其中所有的線以下的點的連接X _分鐘和X _最大兩個子列表是在一個列表中，所有上述這條線是在另一個。在第一個列表中包括X _分鐘並且在第二個列表中包括X _max。
3. 按X值的升序對第一個列表進行排序。如果您有多個具有相同X值的點，請按升序Y值對其進行排序。由於多邊形是凸面的，因此這隻應發生在與X分量相同的點上。
4. 按X值的降序對第二個列表進行排序。再次，在具有相同X值的多個點的情況下，按照下降的Y值進行排序（其僅應用於具有X分量的點X _分鐘,
5. 將兩個列表追加到一起（哪個是第一個。）

Answer 2

選擇多邊形上的兩個點。該線的中點將包含在該多邊形內。假設該點爲M.

然後，根據基於M（沿着X軸）的角度對點進行排序，基於距離M的距離打破簡併度。按順序進行迭代確保沒有兩條邊相交。