尋找一組點的中心順時針排序嗎？

我想按順時針順序排列一個點的矢量以形成一個多邊形，但我需要適當的中心來完成。我已經嘗試過平均法，但是有幾點沒有正確排序。以順時針方式排序點時，找到將工作的中心的正確方法是什麼？尋找一組點的中心順時針排序嗎？

它是在凹部沒有

感謝

這裏有一個畫面： enter image description here

綠圈是中心。

應該看起來更像是這樣的： enter image description here

來源

2011-08-11 jmasterx

鑑於多邊形只是由它的點定義並且是非凸的，我不確定沒有一些進一步約束的解決方案。目前尚不清楚多邊形是否被唯一定義。 – Keith

「按順時針順序排序」的概念是不明確的，如果你沒有一個預先定義的中心點。

如果你已經是隻是一堆，你需要理清點的，你不知道事先的中心，那麼問題一般沒有單一的解決方案。這個問題有許多其他的解決方案，每個解決方案都會給你一個不同的多邊形作爲結果。

此外，找到一個允許您通過CW（或CCW）排序重新創建原始多邊形的中心僅適用於特殊類別的多邊形：所謂的多邊形star-shaped。星形多邊形的主要特性是可以在多邊形內部找到一個點，多邊形的整個內部都是「可觀察的」（我希望在沒有定義的情況下清楚「可觀察」是什麼意思）。

如果多邊形不星狀的，那麼這樣的中心點根本不存在。而且，由於這個原因，不可能通過CW排序重新創建原始多邊形。在圖片

你牛的輪廓顯然不是一個星形多邊形，這意味着你將永遠無法被身邊的一些中心，任何中心分揀點，重新創建原始牛的輪廓。沒有「正確的方式」。這不可能。

來源

2011-08-11 03:30:13 AnT

那麼什麼樣的算法會讓我成爲最初的母牛？ – jmasterx

@Milo：設想一個更簡單的多邊形，比如一個五角星。如果擦除線條並只看點，則至少有兩種可能的重建方法：一個星形或兩個同心五邊形，每個缺失一邊，由兩條線連接。擦除線條會拋出有價值的信息，問題不能可靠地解決。（巧合的是，正如安德烈所說，恆星確實適合你已經嘗試過的算法，但牛不是恆星。） – Potatoswatter

@Milo：如果輪廓點非常密集（尤其是彎曲部分），那麼你可以通過從一個點跳到另一個最近的點來重新創建母牛。但是，如果這些點不夠密集，那麼在某些地方可能會出現錯誤。在一般情況下，根本無法從一組無序的點重新創建原始輪廓。正如我上面所說的，有許多不同的輪廓可以從一組點構建出來。既然你無法決定哪一個是正確的，你不能重新創建它。 – AnT

-1

參考Barycenter。可能這是你正在尋找的

來源

2011-08-11 03:09:14 Shadow

這就是他說他已經試過了。 – Potatoswatter

以任意點爲中心，你應該能夠確定到集合中所有點的距離和角度，然後按角度排序很簡單。但是，選擇中心點會影響排序順序，所以在選擇點作爲中心之前很難知道「正確」順序應該是什麼。因此，如果您選擇質心作爲中心（看起來是一個不錯的選擇），但是有些點相對於該點錯誤地排序，那麼我會說您的排序代碼存在問題。或者，如果您對排序順序沒有達到您的算法的期望，那麼我會說您的一個假設（排序順序或中心位置）是不正確的。

來源

2011-08-11 03:18:51 Caleb

查看我的照片以獲取有關此問題的更多信息。 – jmasterx

您的排序是正確的。問題是你不能通過按照角度分類來生產牛。 – Caleb

那麼什麼樣的算法可以做到這一點？現在我只是從圖片本身獲取輪廓頂點，但它們是按照掃描線順序排列的。 – jmasterx

我認爲最可靠的戰略（除了重新設計你的程序/系統，以便在第一時間就不會出現這個問題）是儘量減少多邊形的總周長。

這不是一個簡單的問題，但這裏是應該工作以及啓發式：

對於每一個點，找到下一個最近的點。這定義了一組潛在的聯繫。
將最長的潛在連接添加到多邊形。
重複1-2，但忽略已經建立的連接和已經有兩個連接的點。

這只是一種啓發式而非解決方案。我不確定它甚至保證產生一個多邊形。

來源

2011-08-11 04:03:45 Potatoswatter

尋找一組點的中心順時針排序嗎？

回答

相關問題