將點列表排序爲多邊形

Question

我有一組點。這組點確實定義了一個（非凸）多邊形，但它沒有排列。

由於沒有命令，我不能只畫出點到點的邊框。我怎樣才能通過這個點列表來繪製一個多邊形？

我的第一個想法是使用凸包，但我的多邊形在大多數情況下是凹的。

Answer 1

我不認爲有一個明確的解決方案。考慮這樣的五點：

. . 
    . 
. . 

什麼多邊形在這裏會是正確的？

Answer 2

您必須訂購點，以便在點到點移動時，您可以在左側（或右側）的內部環繞多邊形。凸或凹，這是正確的方法。

但知道這些點是不夠的。你也必須知道每個邊緣段的連通性。知道這一點，你可以隨時開始沿着周邊走，直到你再次到達起點。

Answer 3

我不確定這是最快的方法，但它似乎工作。

整個想法是使用不相交的線段連接點（除了在點上，這比您想象的有點棘手）。因此，從原始未排序列表開始，按順序連接它們 - 形成一個可能有許多交叉點的封閉路徑 - 然後通過反轉列表中的點的子序列逐個消除交叉點。

假設我們從[a b c d e f g h]開始，並且發現b-c邊緣穿過g-h邊緣。我們逆轉c-g序列以得到一個新的列表：[a b g f e d c h]。兩條邊被移除並創建了兩條新邊;其餘的都沒有受到干擾（儘管有些已經顛倒了方向）。

我一直無法找到這個過程永遠運行的情況（即列表將返回到先前的狀態），也沒有證明這不會發生。