多邊形的布爾運算-或 與 異或 減法
1 人贊了文章
前文
多邊形的布爾運算是一個非常常用的演算法,網上搜一搜也可以找到輪子,如
GPC General Polygon Clipper library from The University of Manchester該頁面中最底端也有其他人的輪子.
不過呢,它們的協議大多不允許商用,就只好自己寫一個了,準確講,是基於一篇20年前的文章改編的輪子.
原演算法詳見
Polygon Boolean operations on sets of polygons
演算法正文
I.需要定義的數據結構
1.點:需要存儲一個二維點的位置信息
2.邊:需要存儲兩個點
3.多邊形:存儲邊
4.多邊形組:存儲多邊形
II.步驟
演算法規則:傳入兩個多邊形組 輸出一個多邊形組,為了方便,下文以L,R代表兩個輸入參數,以O代表輸出多邊形組
1.將傳入的點的數組轉換為邊,原作者在這一步對每個點進行了降精度操作,如:(int)(position.x*100),這樣整個操作流程就會以int型完成,不過在計算機性能足夠的情況應該不需要進行這一步.
這一步應該可以提前在new多邊形時做好,這樣可以節省演算法時間.
2.計算邊之間的交叉,這一步採用了掃描線法.先將L,R的所有點存儲到一個數組,並按照從左到右進行排序,接下來重複以下步驟:
a.選取相鄰兩個點形成一個掃描線束(scanbeam),因為已經排序,其間必定無其他點
b.遍歷所有邊,找出所有被掃描線束穿過的邊,如下圖
c.遍歷b中得到的邊,對其標記與掃描線束左側交點的y值,即上圖的ysp
d.同c,不過這次要標記右側交點,即圖中的ysn
e.按照ysn排序,並按順序遍歷ysp,如有兩邊的ysp順序不同於ysn順序,其間必有交點,計算交點位置(STFW),並為每個邊queue交點,所以一個交點會被添加到兩個邊上
比較ysn和ysp有多種辦法,比如先根據ysp排序,再根據ysn進行雞尾酒排序,每次交換即為交叉
f.移動到下一個掃描線束
3.對每條邊正式插入交點,這一步簡單,直接遍歷每條邊的交點並按照順序排列插入生成多個新邊
4.為每條邊標記是否在另一個多邊形組內,這一步其實可以在2中直接完成,原文沒有詳細講述,但我的做法如下:
對一條掃描線觀察可以發現,每次掃描線經過一條邊時會從該邊所屬多邊形外部進入內部,如圖,便可知在該掃描線交點這條邊在內外的情況
在2-d中進行此操作,對同一邊允許覆蓋之前的值,因為如果一條邊無任何交叉,它的內外值必定一致,如果有交叉,每次交叉必定會使內外值更改,要麼內->外,要麼反之.所以在3中插入新邊時,要根據2-d中求得的內外值對新邊交替設置內外值
5.根據點,線之間的連接狀況輸出圖像
通過觀察可知,如果在經歷上述步驟後無任何交叉點生成,那麼L,R要麼分離,要麼相互包含,這一步自行判斷輸出即可
若有交叉點,可以知道O中至少含有兩個交叉點,所以之前生成交叉點時可以記錄下它們,並在此步驟進行遍歷,進行以下步驟:
a.選取一個從未被選中過的(在b-e中也沒有被選中過的)交叉點作為當前點(current)
b.找出以current為頭的邊
c.若有符合條件的邊,則添加current,並把邊的尾設為current,回到b,否則到d
d.找出以current為尾的邊
e.若有符合條件的邊,則添加current,並把邊的頭設為current,回到d,否則回到b
在上述選擇中不可連續選擇同一個邊,這種情況可能發生在c剛剛到d的情況,因此應在c,e中忽視上一個選擇過的邊
在選擇過程中一旦回到最初時的點,說明已經形成環路,輸出該多邊形,並回到a,若所有交叉點已被檢查完畢,結束演算法
6.對於5中所謂"條件"
或:在L或R上,在另一個多邊形組的外部
與:同時在L和R內
異或:滿足或^滿足與
減法:以L-R為例,在L上且在R外,或在R上且在L內
如圖
至此,演算法就算結束了,原文中還有關於自交,簡化圖形的擴展,各位有興趣可以自行探索,本人也僅僅是一個高中生,會c#和unity而已,如有錯誤不足還請教誨
後記
最初的動機來自於彩虹六號這款遊戲,其中的牆體破壞令我眼前一亮,根據ubi在GDC大會上的一次演講發現需要該演算法,也就是說該演算法配合三角剖分可以進行動態的模型布爾運算,當然,僅限平面模型,現在開發的一個項目就需要這個功能.不得不吐槽國內關於計算圖形學的書真是少得可憐,之前買了一本《計算幾何—演算法設計、分析及應用》——周培德,第一眼還以為被民科坑了錢,但演算法還行,希望有這方面的大佬能分享一下好的學習來源
放個效果視頻結尾,視頻大小為2M
https://www.zhihu.com/video/1000127842692284416推薦閱讀:
※演算法 - 插入排序和希爾排序
※Leetcodes Solutions 10 Regular Expression Matching
※民間絕學八字新演算法直斷七柱法[原創3]
※12年愛唯歐鑰匙匹配方法(附密碼演算法)
※Leetcodes Solution 2 Add Two Numbers