從兩條相交路徑中獲取三條合成路徑

Question

我在xy平面中有兩條相交路徑，請參閱圖像。

路徑由一系列點定義，以便每兩個連續的點形成路徑邊。路徑總是關閉。點標記以指示它們是否來自邊緣或曲線。 我想寫一個函數來獲得如下三個路徑。

我嘗試了以下方法。

create temp path Object path_C 
go through every edge in path_A 
    go through every edge in path_B 
     if current edge of path_A intersects edge of path_B 
     find the intersection 
     store the intersection point in path_C 
    inner loop ends here 
outer loop ends here 
go through every point in path_A 
    if a point lies within the path_B 
    add it to the path_C 
    and remove it from path_A 
end of loop 
go through every point in path_B 
    if a point lies within the path_A 
    add it to the path_C 
    and remove it from path_B 
end the loop 

在我運行它之前，我的一位朋友指出，並不能保證path_C按照正確的順序得到了點。現在我無法弄清楚如何解決這個問題。 如果你可以建議一些更好的優化。

附註：我其實想實現在Adobe Illustrator中的探路者面板鴻溝功能。

Answer 1

你要找的術語是一個「圖形循環」，看看這個堆棧溢出線程：finding all cycles in graph。基本上你想從兩條路徑構建一個圖形。這是通過加入兩條路徑（帶入所有的邊和垂直）並在每個交點上引入新的頂點來完成的。交點是圖形合併的地方。在實現過程中，考慮所有的邊緣情況，即交叉點可以發生在穿過頂點的邊緣，共線邊緣/垂直等之間。還要注意，對於某些形狀，比如說U形和矩形，可以產生幾個週期。