對描述多邊形的線段數組進行排序和分組

我解析了一些數據，這些數據是作爲描述幾個封閉的任意形狀/多邊形的線段數組給出的。這些形狀可以是凹形的。這裏是什麼，我在看一個簡單的例子：對描述多邊形的線段數組進行排序和分組

不過，我提供的數據具有以任意順序段。根據這個例子，我的數據就像{V,E,D,X,U,A,Z,C,B,W,Y}。因此，繪製這些段會顯示正確的形狀，但在形狀上進行任何操作都不會更容易。

我想對上面的數組進行排序，以便每個閉合形狀的段遵循連接順序，並且每個形狀的段被組合在一起。

所以

{V,E,D,X,U,A,Z,C,B,W,Y}

將成爲

[ {A,B,C,D,E} , {X,Y,Z} , {U,V,W} ]

每組線段的並不重要，我，只有個別段是按順序排序。我也不關心每個組的特定起始段。

這樣

[ {Y,Z,X} , {C,D,E,A,B} , {W,U,V} ]

同樣是一個有效的結果。

我對遍歷幾何沒有經驗，而且我的基本嘗試和粗略的在線搜索都沒有產生任何快速解決方案。我看着凹殼，但這似乎是過度的，因爲數據已經知道點之間的聯繫。

來源

2016-12-26 interloper

看看我的答案（編輯部分）在這裏：http://stackoverflow.com/questions/41245408/ – MBo

頭扯皮的一天後，在這裏實驗的建議，並編寫一些輔助類，我想出了一些非常普通的。在粗糙的僞代碼，我的解決辦法是：

create group list; 

while (line segments exist in pool) 
{ 
    create new group; 
    remove one segment from pool and place into group; 

    while (endpoint of last line in group != startpoint of first line in group) 
    { 
     get the endpoint of the last line in group; 
     search pool for line segment whose startpoint = that endpoint; 
     remove that segment from the pool and place into group; 
    } 

    store group in group list; 
}

代碼依賴於我的數據只包含封閉的形狀（即每個形狀的數據整齊地終止在完全相同的座標）的假設，所有的數據創建形狀，而不僅僅是孤立的線條。我不確定這是多麼高效，但考慮到這隻用作預處理步驟，這就足夠了。

來源

2016-12-27 13:38:13 interloper

如果我可以假設你知道每個段的起點和終點（讓我們稱它們爲節點），並且多邊形永遠不會與另一個段具有公共節點，那麼可以執行以下操作：

創建節點列表：每個節點由它連接的兩個段定義。例如節點1是連接段A和節點E的節點，節點2是連接A和B的節點等。
將節點分組爲多邊形，即將所有節點放在一起共享公共段。
大功告成

來源

2016-12-26 12:40:17 user7291698

對描述多邊形的線段數組進行排序和分組

回答

相關問題