如何將不規則形狀沿路徑切割成兩部分？

Question

我有一個相當複雜的幾何問題，我需要解決，我想知道是否有人可以指點我的資源來解決它。

我有一個不規則的形狀組成的垂直和水平喜歡。它由順時針方向的一系列x，y點描述，形成一條路徑。最後一點加入第一個形成形狀的邊界。沒有一條線彼此交叉。當我在屏幕上繪製形狀時，我沿着Y軸使用經典的掃描線算法將形狀變成一系列填充的矩形。

但是現在我希望用戶能夠切片形狀通過使用水平線或垂直線再次從邊界上的一個點到邊界上的另一個點繪製路徑爲兩部分。在該圖中，用戶從1開始繪製並在2處結束切片發生。

所以這裏有幾個我必須削減的事情的例子。使用用戶繪製的用紅色顯示的切割路徑將原始形狀切割成部分A和B.請注意，用戶不能保證與我的區域相同的順時針方向切換（即，下面的1和2可以顛倒），所以我必須處理這個問題。

該線路將被完全包含在邊界形狀內，並且不會越過本身。即當我用路徑切割形狀時，它將導致剛好2個新形狀。

思考出來大聲，我認爲這樣做的僞代碼可能是這樣的：

1. 描述的形狀爲一系列的X，Y點，編號爲0到Nñ加入到0，關閉形狀。
2. 允許用戶繪製在形狀路徑上的某處開始和結束的切割路徑。用戶界面可以防止用戶跨越自己的線或在形狀外繪圖。
3. 計算出剪切路徑開始和結束的形狀中的哪些線索引。線索引由點索引0-> 1，1-> 2，... N-1-> N，N-> 0來描述。爲了確保用戶的切割路徑與形狀的方向相同，將其路徑如果： a）結束形狀​​線索引<開始形狀線索引 b）或形狀結束線索引==形狀起始線索引但結束切割點更接近線索引起始點
4. 構造兩個點列表。 a）行> =結束索引< =開始索引+剪切路徑，剪切點處的剪切開始/結束行 b）剪切路徑+行> =開始和< =結束索引，修剪剪切處的開始/結束行點數
5. 從點列表創建新區域。

我認爲這可能會工作，但顯然它會更容易，如果有實際的代碼已經這樣做了！

Answer 1

我不知道那裏已經有這個工作的代碼。

實際上，您需要爲兩個新形狀中的一個反轉切割路徑，而不是爲另一個反轉。 （如果你所說的所有順時針方向的形狀都是正確的。）我認爲最簡單的方法就是看你周圍的哪條路要爲每個形狀採取這樣的路徑：（1）從UI交互中，你將知道剪切路徑在形狀上的位置; （2a）從切割路徑的一端開始，順時針繞着形狀行進，直到你碰到另一端，然後沿着切割路徑返回到第一端，給出一個形狀; （2b）現在從原始末端開始，沿着另一個方向的切割路徑，然後沿着該形狀順時針方向行走，直到返回到原始切割路徑終點，從而爲您提供其他形狀。

除此之外，您的僞代碼對我來說看起來還不錯。