從多邊形中減去矩形

我正在尋找一種算法，它將從一個簡單的凹多邊形中減去一個矩形並返回多邊形的其餘部分。如果矩形包圍多邊形，則餘數爲空。在大多數情況下，看起來至少有一條邊將在矩形和多邊形之間共享。從多邊形中減去矩形

我一直在挖掘互聯網，但我還沒有找到一個好的主角。

有人能指出我正確的方向嗎？

2012-11-02 Josh C.

我試圖在[張貼在MathOverflow同樣的問題（http://mathoverflow.net/questions/111296/subtract-rectangle-from-polygon/111323#111323）來回答。 –

這很簡單：找到矩形和簡單多邊形的邊界之間的交集並在那裏剪切這些分段。這不需要空間搜索結構，因爲多邊形的四條邊是一個常數因子，因此可以在線性時間內運行。

然後計算所有分段的約束Delaunay三角剖分並使用種子點來生長區域。合適地組合區域（簡單多邊形內的三角形減去矩形內的三角形減去外部的三角形，剩下的三角形是你的結果，邊界邊緣是結果多邊形的邊緣。如果答案是太短了。下圖顯示了這個想法。
一）這兩個輸入多邊形
b）在CDT的（板缺）鏈段的插入
c）在生長區域
d）綠色區域之後減去紅色區域
e）d區域的邊界邊緣。

enter image description here

來源

2012-11-04 02:30:20 leftangle

不是批評你的答案，但我發現這些解釋可以通過一支鉛筆和一張紙進行得更好...... – num3ric

由於矩形的至少一條邊與我的多邊形共線。我應該先合併這些邊緣嗎？而且由於我使用的是面向對象編程，我應該將點結構加強到跟蹤邊的頂點類中嗎？另外，我對計算幾何知之甚少。你能提出德勞內如何提供幫助的圖表嗎？ –

我已添加圖片。如果合併重複邊緣是必要的，取決於您使用的庫。 – leftangle

從多邊形中減去矩形

回答

相關問題