多邊形鏈 - 在保持形狀的情況下轉換爲非交叉？

我有類似下面的多邊形鏈...多邊形鏈 - 在保持形狀的情況下轉換爲非交叉？

...給出鏈的形象，我將如何去計算定義相同的形狀但沒有交叉鏈路徑？

具體而言，在圖像的輸入鏈的情況下，結果我想是這樣的：

A1，
A2，A2和之間
相交A3，
A3和之間的相交A4，
A4，
A5，
相交和A4，
A3，
相交A3和A2，
A6之間

我之間A3正在尋找一個ALG算法來完成這個任何鏈，但我不知道我想要做什麼甚至叫，這使得搜索解決方案棘手。

如果我想要做的事情有一個名字，那麼知道它會有很大的幫助。

謝謝你的幫助！

來源

2010-06-04 Monte Hurd

你的問題不是很清楚。你能提供一個你期望輸出的數字嗎？同樣，_same shape_的意思是什麼？形狀似乎沒有很好的路徑定義... – 2010-06-04 04:35:02

@Moron，但我列出*精確*輸出我正在尋找 - 我鏈接到的圖像給出了我列出的上下文的輸出。 – 2010-06-04 04:56:25

感謝編輯Nick！我應該知道我可以嵌入圖像。 – 2010-06-04 04:57:59

這裏有一個簡單的算法：

for each line segment in the chain: 
    Identify any segments which cross this segment 
    If crossings > 0 
     Follow the branch to the right, if this doesn't lead back to the 
     current intersection follow the branch to the left 
    go to the next line segment

如果下面的一個分支不會導致回那個路口前往，這意味着你跳過一個循環鏈的末端之前，所以你需要選擇其他分支。

對於你的榜樣，運行該算法將產生

Start at segment A1-A2 
No intersections, goto next 
Segment A2-A3 
Intersection A2-A3/A6-A5 choose right path and store the current intersection somewhere 
Segment A6-A5 
Intersection A6-A5/A4-A3 choose right path and store intersection 
Segment A3-A4 
A4-A5 
A5-A6 
Back at intersection A6-A5/A4-A3, go right again to be back on A4-A3 
A3-A2 
Back at intersection A2-A3/A6-A5, go right again 
Finish

來源

2010-06-04 04:42:37

但是，如果交叉點變得複雜，那麼不會分解嗎？正如在這張圖片中：http://imgur.com/hBLwz。jpg – 2010-06-04 07:54:15

@Monte你說得對，看起來算法可能會返回到前一個路徑。但是，如果是這樣的話，它必定是存在多個不好的交點（否則另一個路徑可以穿越），所以可以記錄你已經嘗試過的交點，例如http：// img526。 imageshack.us/img526/3117/path.png – 2010-06-04 13:30:37

你真了不起。我現在對你的方法有一個更清晰的思路！ – 2010-06-04 15:37:35

多邊形鏈 - 在保持形狀的情況下轉換爲非交叉？

回答

相關問題