直線多邊形交集

我正在尋找/嘗試爲rectilinear polygon交叉矩形開發最佳算法。我正在測試的多邊形沒有孔。直線多邊形交集

類似here和here的答案適用於非常一般的多邊形，並且解決方案的理解相當複雜。

希望S.O.社區可以幫助我記錄只有直線多邊形的特殊情況的算法。

我找下面充滿綠色的圖像中的多邊形：

rectilinear polygon intersection with a rectangle

2011-05-21 jedierikb

是直線多邊形的邊和平行於軸的矩形？ – 2011-05-21 19:45:56

@Andre - 是 - 所有行都是平行的 – jedierikb 2011-05-21 19:47:46

作爲第一個想法，將直線多邊形存儲在[segment tree]（http://en.wikipedia.org/wiki/Segment_tree）（二維）中我腦海。假設直線多邊形是不變的矩形，而且矩形也是變化的。 – 2011-05-21 19:53:57

書計算幾何：通過Preparata的介紹和Shamos對直線多邊形的一章。

2011-05-21 17:59:14 lhf

謝謝。我會看第2章和第8章。我看到我想要的術語是等度多邊形。 – jedierikb 2011-05-21 19:32:00

使用掃描線算法，利用直線多邊形由其頂點定義的事實。

表示頂點以及它們所屬的矩形，即類似(x, y, #rect)。對於這組點，添加由所有邊的交點所產生的點。這些新點的格式爲(x, y, final)，因爲我們已經知道它們屬於所得到的一組點。

現在：

排序的x值
所有點使用掃描線，從第一個x座標;對於每個新點：
- 如果它是「起點」，則將其添加到臨時集T。如果它是來自矩形A的點，並且來自T中的矩形B的點的y座標（或反之亦然），則將其標記爲「最終」。
- 如果它是一個「終點」，從T.

之後刪除它和它的相應的起點，被標記爲「最終」的所有點表示結果多邊形的頂點。

設N是點的總數。進一步假設測試我們是否應該將點標記爲「最終」，通過查找T花費時間O（log（n）），整個算法在O（N * log（N））中。

請注意，查找所有交叉點的任務可以合併到上述算法中，因爲通常有效地查找所有交點本身就是一個掃掠線算法。還要注意，得到的一組點可能包含多個多邊形，這使得重建「最終」頂點之外的解多邊形變得稍微困難。

2011-05-23 11:40:12 Philip

回答