如何在非凸多邊形中排序頂點（如何找到許多解決方案之一）

我有點的座標，需要找到一些多邊形。對於一個點列表有更多的解決方案無關緊要。我需要一些算法來找到其中的一個。哪一個並不重要。我真的不知道如何解決這個問題。

（我已經存儲在陣列座標，我想使用某種算法在Javascript）

非常感謝。

2013-10-31 1daemon1

或許，如果你告訴我們什麼是錯的解決方案，這個問題你是指這使得它們不適合您的使用，我們可以提供精確的和有益的幫助。如果你不能，或者不能告訴我們，我們可能會得出結論，即你對問題的理解甚至不甚瞭解，並因此而將你的問題排除在主題之外。 –

你僅限於簡單的多邊形嗎？否則，您可以根據需要連接頂點。他們將永遠形成一個多邊形。 –

有一個O（n^2）算法：對於每個點的排列，構造一個多邊形並查看它是否是一個簡單的非凸多邊形。當然，如果你有很多積分，這需要一些時間。你有幾點？ –

首先，找到包含所有頂點的邊界框的中心。我們將這個點稱爲C.

根據每個點相對於C的角度對頂點列表進行排序。您可以使用atan2(point.y - C.y, point.x - C.x)來查找角度。如果兩個或兩個以上的頂點具有相同的角度，則靠近C的一個頂點應該首先出現。

然後，按照出現在列表中的順序繪製點。你將會得到一個不相交併且可能是非凸的星爆圖案。例如：

100 points randomly placed on a 400x400 pixel square

2013-10-31 19:35:58 Kevin

這正是我所需要的。非常感謝！ – 1daemon1

這會在3D場景中工作嗎？ – Ogen

@Clay，應該可能形成一個尖刺球狀的多面體，儘管我不知道你將如何決定哪個點應該共享邊緣。排序思想在兩個維度上起作用，因爲每個點只有兩個相鄰的鄰居，一個在任一個旋轉方向;但在三維中，一個點可以有多個鄰居。因此，只需訂購點數不再提供線段的完整列表。 – Kevin

回答