首先吐槽一下：今天考IT項(xiàng)目管理，100道選擇題。前幾天考配置管理，10道大題。如今的老師都喜歡走極端……

    這個(gè)方法是在考完試回宿舍的路上想到的，適用于2D與3D。主要想法是這樣的。給定兩個(gè)幾何圖形A、B，把A和B都分成『內(nèi)『、『外』兩部分。A的『內(nèi)』就是處于B內(nèi)部的部分。于是A和B就變成了A內(nèi)、A外、B內(nèi)、B外。然后就有如下公式：
    ·A and B=A外+B外
    ·A sub B=A外+B內(nèi)
    ·A or B=A內(nèi)+B內(nèi)
    ·A xor B=A外+B外+A內(nèi)+B內(nèi)
    這種數(shù)據(jù)結(jié)構(gòu)是為了滿足如下算法：一個(gè)A點(diǎn)在圖形內(nèi)<==>過(guò)這個(gè)點(diǎn)的直線交圖形與點(diǎn)集P，其中|{Pi|Pi<=A}|和|{Pi|Pi>=A}|都是奇數(shù)。注意我們使用的是<=和>=，這樣的話兩個(gè)集合的數(shù)量的奇偶性都是一致的。這個(gè)算法無(wú)論2D、3D多邊形還是3D多面體都能適用，就算是這個(gè)圖形有孔（鑲嵌）也可以，而且跟凹凸體無(wú)關(guān)。這個(gè)算法只有一種情況是不能用的：就是自己跟自己有交叉，譬如我們習(xí)慣的5條直線構(gòu)成五角星的畫(huà)法。這樣的話首先要對(duì)這個(gè)圖形進(jìn)行處理，成為鑲嵌的圖形。

    讓我們來(lái)圖示一下。現(xiàn)在我們給出兩個(gè)回形的紅色和藍(lán)色向前多邊形：

    然后我們把兩個(gè)圖形分為內(nèi)外一共四部分，其中內(nèi)使用粗線：
    我們把這個(gè)圖形轉(zhuǎn)換成拓?fù)浣Y(jié)構(gòu)，得到了下面的連線圖。現(xiàn)在讓我們來(lái)求藍(lán) sub 紅，也就是藍(lán)外+紅內(nèi)：
    我們可以很容易地看到現(xiàn)在圖形分成了4各部分，因?yàn)橄旅娴耐負(fù)浣Y(jié)構(gòu)構(gòu)成的圖一共有4個(gè)連同體。

    后來(lái)我自己做過(guò)實(shí)驗(yàn)，求藍(lán) And  紅的時(shí)候圖形會(huì)被分成6個(gè)連同體，其中有5個(gè)是鑲嵌的孔。但是哪個(gè)是孔在整個(gè)過(guò)程中并沒(méi)有關(guān)系。因?yàn)槲覀冎恍枰阉械腃omponent求出來(lái)，內(nèi)Component就是Component內(nèi)的一點(diǎn)在另一個(gè)圖里，而且判斷是不是內(nèi)部點(diǎn)的算法已經(jīng)給出了。整個(gè)流程跟哪一個(gè)連同體是孔并沒(méi)有關(guān)系。而且在實(shí)際情況下，2D多邊形和3D多面體的渲染并不在乎哪個(gè)是孔，可以正確渲染出來(lái)。唯獨(dú)3D多邊形在乎。這種情況下再慢慢處理吧。而且判斷的算法也是差不多的。不過(guò)我似乎沒(méi)有見(jiàn)到3D多邊形的布爾運(yùn)算有什么常見(jiàn)的應(yīng)用。

    期末考過(guò)后就可以開(kāi)始寫(xiě)布爾運(yùn)算的代碼了。