深入 Canvas/SVG 的布爾運算（Martinez 法）
?????♀??編者按：本文作者是螞蟻集團前端工程師阿侎，和大家深入探討 Canvas/SVG 的布爾運算，包括環(huán)繞規(guī)則、分割、求交、線段內(nèi)外性、線段注釋、擴展曲線、選擇結(jié)果、強制奇偶等等，歡迎查閱～
前言
支付寶 LOGO 的結(jié)構(gòu)圖相信很多人看過。它通過若干形狀和線段，描述了整體矢量圖形的邏輯構(gòu)造。比如：背景是個圓角矩形；內(nèi)部減去一個“支”矢量圖。
這種將任意 2 個矢量圖形，通過合、減、交、差的集合方法，組合成新的矢量圖形的方法叫做多邊形的布爾運算?？瓷先ズ臀粓D的 mask 遮罩很相似，但功能更強大一些。因為 mask 的作用相當于“交集”，反向 mask 或者說 clip 裁剪相當于“減集”，合集和差集則很不常見。矢量的計算處理，涉及一定程度的幾何圖形學(xué)知識，也比位圖 mask 要難。
環(huán)繞規(guī)則
矢量圖形繪制有個基本概念，需要定義區(qū)分一個閉合區(qū)域的內(nèi)部或外部，這樣在渲染時只會填充內(nèi)部。通過環(huán)繞數(shù)（winding number）來判斷內(nèi)外，也叫環(huán)繞規(guī)則或填充規(guī)則。一個閉合區(qū)域的邊的順序分為順時針和逆時針 2 種情況。如下圖三角形內(nèi)部填充紅色，3 條邊可以順時針畫也可以逆時針畫。
從區(qū)域中任意方向引一條射線，判斷射線和邊的相交結(jié)果（相切不算），如果遇到逆時針的邊記+1，順時針的邊記-1，那么最終所有次數(shù)相加的和，即環(huán)繞數(shù)，可能有 3 種情況：正數(shù)、零、負數(shù)。通過定義不同情況便可確立填充規(guī)則，常見的是非零環(huán)繞和奇偶環(huán)繞。前者指環(huán)繞數(shù)非零為內(nèi)部、其它為外部，后者指奇數(shù)為內(nèi)部、偶數(shù)為外部。上面 2 個三角形的環(huán)繞數(shù)是-1和+1，無論哪種規(guī)則效果都是一樣的。再看下圖左，按照黑色箭頭的筆畫方向繪制一個星形，在非零和奇偶 2 種規(guī)則下填充效果分別為圖中和圖右。星形正中間區(qū)域環(huán)繞數(shù)是-2，非零認為是內(nèi)部，奇偶認為是外部。
在 Canvas/SVG 中，默認是非零，可以通過傳值更改：
Bentley-Ottmann
Bentley-Ottmann 是一個求平面上所有線段交點的算法，屬于掃描線算法的一種。掃描線算法是指引入一條直線，可以是水平或者垂直的，從一端掃描到另一端，中間經(jīng)過頂點位置時會觸發(fā)事件。在這個過程中完成求交的結(jié)果。如下圖，有紅色線段 a 和藍色線段 b，能看出它們有個交點。垂直掃描線從左側(cè)掃描到右側(cè)，依次經(jīng)歷了：a 左側(cè)開始點、b 左側(cè)開始點、a 和 b 交點（后面會說特殊性）、b 右側(cè)結(jié)束點、a 右側(cè)結(jié)束點。處在掃描線范圍內(nèi)的線段稱為活動線段。5 個頂點位置觸發(fā) 5 個事件，配合上不同的處理，便可完成整體算法（例子中交點這個頂點事件很特殊，并不是一開始就已知的，而是 a 和 b 開始事件后求得的，如果不相交就不會有）。
這個算法的好處是線段很多的情況下，時間復(fù)雜度約為 O(nlogn)。不像兩兩對比需要 O(n^2)。具體可以搜索或者看《Wiki》，這里不過多深入。Bentley-Ottmann 揭示了 2 個要點：
兩條相交的線段必定是臨近的：掃描過程中只檢測相鄰的兩條活動線段是否相交，大大減少了對比次數(shù)；
兩條線段相交后會交換上下位置：起初 a 在 b 上面，相交后 a 在 b 下方，相鄰關(guān)系發(fā)生變化。
Martinez 以此為根據(jù)寫了篇算法論文（見末尾參考），在掃描求交的同時進行線段的內(nèi)外性注釋，最后給出布爾運算的結(jié)果?？上У氖?，它只支持直線多邊形，不支持曲線多邊形?，F(xiàn)實情況中貝塞爾曲線矢量圖形更加常見，比如文章開頭支付寶 LOGO 中大量的圓弧。雖然可以通過將弧線離散為很多細小的直線，但這樣會產(chǎn)生精度問題，頂點過多也會影響性能。
筆者借鑒 Vatti 的方法將弧線分割為x單調(diào)性的弧線，將求交的部分用普通掃描線算法實現(xiàn)，再以 Martinez 的線段內(nèi)外性注釋方法完成布爾運算。這樣做的原因是邏輯比較清晰簡單，方便拆分解耦。如果有同時求交和注釋的詳細解法，請不吝賜教。另：Martinez 法強制參與運算的規(guī)則是奇偶環(huán)繞，Sketch 似乎就是如此，見后文。
分割
算法的第一步是檢查是否有非 x 單調(diào)性的曲線，如果有則求導(dǎo)確定單調(diào)變化的極值點，然后分割曲線，確保 x 一定是單調(diào)增或者單調(diào)減。這么做是為了后面線段注釋算法，可以先跳過。如圖，多邊形右側(cè)的非x單調(diào)性曲線切割為上下 2 份，原本 4 條邊 4 個頂點變成 5 條邊 5 個頂點：
求交
普通的掃描線求交算法理解起來要簡單一些，不像 Bentley-Ottmann 有諸多限制，還能包含曲線。具體做法是先遍歷求得每條線段的 bbox，即包圍盒。直線比較簡單，曲線需要求導(dǎo)求極值。可以參考：
https://www.iquilezles.org/www/articles/bezierbbox/bezierbbox.htm
注意文中遺漏了特殊情況，當 2 次項系數(shù)為 0 時，方程降級為一元一次。
有了 bbox 后，掃描線經(jīng)過的點即每個 bbox 的左側(cè)開始和右側(cè)結(jié)束。每掃過開始，將這條線段加入活動列表；掃過結(jié)束則剔除。處于活動列表中的線段且 bbox 有重疊的，才進行真正求交。再有交點結(jié)果的，從相交處分割線段。
如上圖，3 條線段 abc 的 bbox 都用半透明底色填充供可視化觀察（圖左）。
當掃描線掃到 b 的開始時（圖中），活動列表是 a 和 b，且 a 和 b 的 bbox 重疊，求交但沒有交點。
當掃到 c 的開始時（圖右），活動列表是 a 和 c，且 a 和 c 的 bbox 重疊，求交有交點。將 a 分割為 a1 和 a2，c 分割為 c1 和 c2（圖下）。
注意，如果遇到線段重合，包括部分重合和完全重合，重合的部分只計一次，多余的要舍棄掉。但重合次數(shù)要記下來，比如 a、b 線段中間部分重合，求交后重合部分提取出來作為一條線段，次數(shù)是 2。
另外垂線是個特殊的情況，它會和掃描線重合。這時記下端點是開始，上端點是結(jié)束。在進入活動列表時要特殊注意下，不要剛進來就被剔除了。
線段內(nèi)外性
這里我直接借用了@velipso 的 blog 的例子，他畫得非常漂亮！原文鏈接在末尾參考。
紅色多邊形和藍色多邊形如上圖，它們重合的邊（線段）有 2、3、4，次數(shù)都是 2。Martinez 法是基于邊的思考，不同于 Greiner-Hormann 基于點的思考，它最重要的是可以處理重合問題。我們先將 2 個多邊形各自查看，每條邊（線段）都有兩側(cè)的概念，其中一側(cè)是多邊形內(nèi)部，另外一側(cè)是外部。
以同色實心圓圈標識內(nèi)部，空心圓圈標識外部，很容易理解上圖中紅藍多邊形每條邊的內(nèi)外性。然后再將 2 個多邊形放在一起看，為每條邊添加對方顏色的內(nèi)外性圓圈，就得到了這樣一張圖：
如果你有足夠的洞察力，相信看到這張圖之后，就能想象出算法結(jié)果：選取符合內(nèi)外性要求的邊組成新的多邊形。例如交集的結(jié)果是紅藍重疊的 2 個三角形，重疊的邊有什么特征？一側(cè)的紅藍圓圈都是實心的。
線段注釋
那么接下來最重要的事情就是給每條邊（線段）注釋內(nèi)外性了。我們?nèi)匀贿x用垂直掃描線算法，但要掃描 3 次：
只掃描紅色多邊形，計算紅色邊的注釋；
只掃描藍色多邊形，計算藍色邊的注釋；
同時掃描紅藍多邊形，計算對方邊的注釋。
掃描前先給出幾點說明：
掃描線是從左到右的，因此所有線段的左端點為開始點，右端點為結(jié)束點；
維持一個活動列表，當掃過開始點時將線段加入，掃過結(jié)束點時剔除；
活動列表中的線段，按照相同x值的部分比較 y 大小來確定上下排序；
同一時刻掃描線可能經(jīng)過多個頂點（x 坐標相同），按從下到上順序觸發(fā)；
開始點和結(jié)束點重合時（兩條線段交點），優(yōu)先結(jié)束；
線段會把所在平面分為上下兩部分，這樣說有點不嚴謹，可以想象線段延長為直線；
垂線比較特殊，記下端點為開始點，上端點為結(jié)束點，這時左邊稱為上，右邊稱為下；
最重要的來了，通過 Bentley-Ottmann 帶給我們的思考，能得出以下觀察（先考慮前 2 次分別掃描注釋紅藍自己）。首先，掃描過程中，處于活動列表底部的邊，它的下面沒有其它線段了，所以下面這側(cè)一定是外部。如下圖，線段 1、2、3、4、5、6，都是底部的。結(jié)合之前注釋的圓圈圖，無論紅色還是藍色，下方都是空心的。
然后，當我們得知一條邊的一側(cè)的內(nèi)外性后，另外一側(cè)也就知道了。一般是相反，除非是重合線段。下圖的繪制順序是：abcabd。根據(jù)奇偶規(guī)則，底部的邊 ab 重合 2 次，因此它的上方也是空白的。由此不難發(fā)現(xiàn)：在奇偶規(guī)則下，重合邊的兩側(cè)，根據(jù)重合次數(shù)的奇偶性，決定了是否內(nèi)外性一致。
最后，活動列表中相鄰的 2 條線段，如果已知下面一條線段的上方內(nèi)外性，那么上面一條線段的下方必然是相等的。這條太直觀了，就像公理。
完成前 2 次掃描后，可以得到上圖的注釋信息。注意紅藍重合的 3 條邊，已經(jīng)提前知道對方的注釋了。
接下來該考慮第 3 次掃描注釋對方。普通非重合線（這里重合是指和對方多邊形的重合，注意區(qū)分）的情況下，依舊是查看是否處于活動列表最底部，是的話一定在對方多邊形外，上下注釋對方都是空心圓圈。如下圖 1 號紅色線段，是底部線段，那么兩側(cè)的藍色都是外部空心。
普通非底部的話，查看活動列表中下方的邊，如果和自己同色，取其上方的對方注釋，否則取其上方的自己注釋。如上圖 2 號線段，下方是 1 號線段，同色，取 1 號上方的對方藍色空心圓圈給自己注釋；而 6 號線段又是底部，兩側(cè)都是藍色空心；7 號線段的下方是 6 號，不同色，取 6 號上方自己紅色實心圓圈給自己注釋。特殊的和對方重合的 3、4、5線段，無需多余計算，因為前 2 次掃描時紅色和藍色早已各自計算好了，此時拼在一起即可。
擴展曲線
曲線的注釋和直線并無區(qū)別，規(guī)則都是一樣的，麻煩點在于判斷曲線相鄰邊上下順序。先看下圖直線。圖左是常見情況，此時可以說 a 在 b 的上方。因為之前的規(guī)則是：按照相同 x 值的部分比較y大小來確定上下排序。掃描線在經(jīng)過 b 左側(cè)開始到 a 右側(cè)結(jié)束時，a 和 b 都處于活動列表內(nèi)且 x 值有相同的一段，此時 a 的 y 值比 b 大，所以說 a 在 b 的上方。圖右是個特殊情況，a 是垂線，但 a 仍然在這部分 y 比 b 大。
再說曲線。實際曲線可以看做是分割成許多條細小的直線組成，當數(shù)量趨向于無窮時等價。這些直線首尾相連不會與其它線段相交，上下內(nèi)外性也保持一致，因此還是符合已有的排序規(guī)則，看相同 x 部分的 y 大小。
還記得開始按 x 分割曲線單調(diào)性嗎？如果不分割的話，就無法滿足這種等價性。
選擇結(jié)果
注釋結(jié)束之后，每條邊就有 4 個圓圈：上紅、下紅、上藍、下藍。每個圓圈有實心/空心 2 種可能，所以就有 16 種變化。用 1 來代表實心，0 代表空心，16 種變化可以寫成一個[0, 15]的二進制數(shù)字。
上紅上藍下紅下藍是否保留1/01/01/01/0？
還是以交集舉例，保留的邊是一側(cè)都是紅藍實心，那么就可以組成這樣一個矩陣：
很漂亮的一個對稱矩陣。但有意排除了 1111=15 這種情況，因為兩側(cè)都是紅藍實心的話，這種邊是毫無意義的，也不會出現(xiàn)。其它幾種情況的矩陣：
選擇最終保留的邊（線段）后，把它們鏈接起來就行。從任意一條線段開始，循環(huán)遍歷所有線段。
如果是開始線段，將其作為一條新鏈（chain）；
后面的線段嘗試能否和已有 chain 連上，如果可以則加入 chain，不能則視作情況1；
每條 chain 加入新邊后，要檢查能否和其它 chain 連接起來，再檢查能否閉合形成一個多邊形子區(qū)域。
到最后會發(fā)現(xiàn)，剩下的邊剛剛好能形成若干個閉合區(qū)域，這就是我們想要的結(jié)果。因為選擇邊的任意性，最終多邊形邊的順序和組合可能也多種多樣。如下圖左紅藍多邊形的異或操作，可能連成隔開的 2 個子區(qū)域，也可能連成重疊的樣子（奇偶環(huán)繞）。
強制奇偶
可以看到，Martinez 法有個前提條件，就是強制奇偶規(guī)則，這樣運算過程中重合的線段部分，才能根據(jù)重合次數(shù)得出兩側(cè)的內(nèi)外性是一致還是相反。像下圖這個 abcabd 的多邊形，奇偶規(guī)則是左邊的樣子，非零則是右邊。
然而無論什么規(guī)則，在 Sketch 中，參與布爾運算后結(jié)果都是奇偶情況下的，因此很可能 Sketch 也使用了類似的解法。下圖的交集都是空：
另外運算的結(jié)果 Sketch 則同時支持了奇偶和非零兩種規(guī)則。
上圖這個例子中右邊 2 個連接結(jié)果，奇偶是一定正確的，非零則必須要求紅色和藍色輪廓的時鐘序是相反的，否則繪制結(jié)果會是全集的樣子。如何確保連接出相反的時鐘序，我并沒有很好的理論證明，只是大概有如下猜測：
優(yōu)先從處于對方內(nèi)部的邊開始循環(huán)（對方兩側(cè)填充性都是實心）；
當新加入的邊有多條 chain 可選時，優(yōu)先選擇和自己不同色的；
如此便會形成包含情況（圖右），用鞋帶定理求得包含的 2 個多邊形的時鐘序，進行相反操作。
如有錯誤，敬請指正。
參考
《A new algorithm for computing Boolean operations on polygons》F. Martinez 2008?
《The method of finding points of intersection of two cubic bezier curves using the sylvester matrix》BI Barbara?
《Polygon-clipping-pt2》@velipso
