Boost 矩形布爾運算

本文主要介紹boost庫中矩形布爾運算的思路和代碼決議，在此感謝Intel對開源事業的貢獻，

基本概念

圖形的插入

所有的操作的第一步都是進行圖形的插入，我們需要宣告定義好我們要使用的圖形型別，以矩形為例，方式為：

rectangle_data(T xl, T yl, T xh, T yh)

實體如下：

ps1.insert(rectangle_data<int>(3,5,7,9));
ps2.insert(rectangle_data<int>(2,4,6,8));

xl, yl, xh, yh分別為x最小值，y最小值，x最大值，y最大值，分別為矩形的右下角左邊和左上角坐標，

頂點與多邊形的轉化——微分

在Boost演算法中，一個基本的實作邏輯是通過計算多邊形的導數來代表多邊形的x和y坐標點變化

在對矩形的端點進行導數計算后，從左到右掃描所有矩形的點y坐標形成的豎直區間，對于矩形，豎直區間導數值等于下端點的導數值， 在代碼實作上，boost并不真的求導，而只是按順序分配，給四個頂點以1和-1的值，以加快運行速度，

從左到右掃描所有矩形的點形成的區間，累加導數值，記錄為count,來判斷是否應該將該區間加入結果中，

假設有n個矩形進行布爾運算，那么設立一個長度為n的陣列count，count[i]代表第i個矩形，布爾運算完成之后的圖形設為 Result，掃描的方式是從左到右進行掃描，

計算加入區間ivl前總體狀態值before和加入ivl之后after，對于不同的布爾運算，總體狀態值的計算方式也不一致，
1.對于或運算，從count[0]和count[1]任一值為1，就能計算出當前總體狀態值為true，
2.對于與運算，就需要從count[0]和count[1]所有值全為1，才能計算出當前總體狀態值為true，
總體狀態值before或after等于true，那么代表位于Result內部，
等于false自然代表位于Result外部，
顯然對于一個區間，加入他前后如果都在Result內部，或者都在Result外部，這個區間就不是Result的邊，反之，如果由內到外或者由外到內，這個區間就是Result的邊，應該加入結果中，

布爾運算代碼詳解

首先宣告矩形，方式為

rectangle_data(T xl, T yl, T xh, T yh)

xl, yl, xh, yh分別為x最小值，y最小值，x最大值，y最大值，
定義三個矩形集合ps1, ps2和ps_tmp，
ps1內包含一個值為(3,5,7,9)的矩形, ps2包含一個值為(2,4,6,8)的矩形，ps_tmp保存結果，

做布爾與運算

ps_tmp=ps1*ps2

通過多載運算子*的形式，進入布爾運算流程，

polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd>
(
    lvalue, 
    rvalue,
    polygon_90_set_traits<geometry_type_1>::orient(lvalue),
    boolean_op::BinaryAnd()
);

lvalue即ps1， rvalue即ps2，

初始化

資料型別介紹：

1. interval_data：區間資料，用于掃描線，

2. polygon中端點資料結構形如：

   (first,(second.first,second.second))

   first存盤端點的x值，second.first存盤端點的y值，second.second存盤端點的導數值，

有幾個變數需要得到初始化：

1. orient:方向，每個 polygon_90_set_data 都有，默認為1.
2. data_:保存著端點的資料，

data_的初始化在insert時就已經完成，首先默認如下圖所示，標記各個頂點,標記名為corner_，值為0,1,2,3（矩形條件下），按照0，1，2，3的順序依次標記各個點的導數值為1,-1,-1,1，需要注意的是在有hole的情況下，導數值會發生變化，具體執行函式位于iterator_geometry_to_set.hpp 52行 inline reference operator*()處，

compute_90_set_value

計算首先在名為 compute_90_set_value 的結構體中進行，將ps1,ps2分別作為lvalue_和rvalue_傳入，
假如ps1和ps2的orient（方向）相同，那么：

1. 對ps1和ps2均進行端點sort，先按x坐標升序排序，若x坐標相同，再按y坐標升序排序，如下圖所示,ps1排序后頂點順序為(3,5),(3,9),(7,5),(7,9)，

呼叫

output_.applyBooleanBinaryOp
(
	lvalue_.begin(), lvalue_.end(),
	rvalue_.begin(), rvalue_.end(), 
	boolean_op::BinaryCount<op_type>()
);

進入applyBooleanBinaryOp函式，

applyBooleanBinaryOp

變數介紹：

1. itr1：迭代器，用于ps1遍歷，
2. itr2：迭代器，用于ps2遍歷，
3. output：布爾運算得到的結果，
4. container: vector型別，保存著每次計算得到的結果，其中元素型別為
   pair<interval_data<Unit>, int>
5. curCoord：記錄當前x值，
6. curPosition：記錄當前y值，
7. curCount：curCount[0]記錄當前區間的屬于ps1的端點導數值，curCount[1]記錄當前區間的屬于ps2的端點導數值，
8. prevCoord：前一個被處理的點的x值，
9. prevPosition：前一個被處理的點的y值，
10. count：累加所有已處理的區間的下端點的導數值，

遍歷ps1和ps2中的所有點,當他們都未被遍歷完時：

1. 選擇itr1和itr2之中x值更小的點，使curCoord為其x值，curPosition為對應的y值，curCoount=defaultCount，如果選擇itr1，curCount[0]加上itr1的導數值，否則，curCount[1]加上itr2的count值，

2. 如果prevCoord!=curCoord，即兩個端點的x值不一致，不能形成一條豎直方向的掃描線區間，不再進行后續處理，直接進行下次回圈，呼叫advanceScan函式使scanData迭代器回到scanData.begin()，并直接更新prevCoord,prevPosition,count，如下圖所示，當前一點為(2,8)，現端點為(3,5)時，二者不在同一豎直線上，不再進行后續處理，
   

3. 否則，繼續處理，宣告并定義變數ivl，ivl的下界為prevPosition,上界為curPosition，

4. 清理container為空，

5. 呼叫boolean.processInterval(container, ivl, count)進行區間的處理和計算,將結果加入container中，

6. 遍歷container中所有interval元素，將prevCoord和元素的上界high聯合成為新端點P1并加入output中，另外，當將prevCoord和元素的下界low聯合成新端點P2,但若P2與output中最后一個端點A重合（如下圖所示，點A與low重合），則將點A移除(為了合并區間),否則加入P2到output，
   

遍歷結束，回傳output，計算完畢，如下圖所示，(3,5),(3,8),(6,5),(6,8)四個點就是布爾運算后的結果中所保存的點，

processInterval

processInterval函式用于計算結果，
變數介紹：

1. ivl：即輸入變數interval，下界和上界分別為low和high，
2. outputContainer：一個vector向量，用于保存結果interval，即輸出，
3. deltaCount：也就是count，累加所有已處理的區間的下端點的導數值，

具體來說：

1. 對比當前interval與scacnData，如果當前interval覆寫到了scanData沒有覆寫到的區域，根據當前interval擴展scanData，例如第一次進入processInterval時，將區間[4,8]傳入，此時scanData 中沒有資料，擴展scanData ，
2. 在scanData中，由輸入的ivl的下界low開始，到ivl的high結束，生成新interval，將新生成的interval輸入到evaluateInterval進行判斷，判斷是否加入outputContainer中，
3. 在evaluateInterval函式中，通過

以 ps1和ps2為例，流程如下

1. 將區間[4,8]傳入processInterval ，此時scanData 中沒有資料，擴展scanData ，
   判斷[4,8]是否需要加入outputContainer中，判斷結果為不需要，
2. 將區間[5,9]傳入，傳入之前scanData為[4,8]，擴展，擴展后為[4,5,8,9]，
   判斷[5,8],[8,9]是否需要加入outputContainer中，[5,8]加入，
3. 將區間[4,8]傳入 ，判斷[4,5],[5,8]，[5,8]加入，
4. 將區間[5,9]傳入，判斷[5,9]，不加入，

判斷區間

判斷區間在evaluateInterval中進行，
變數介紹：
1.ivl：區間interval，
2.beforeCount:代表scanData尚未加入ivl時的count值，保存了所有圖形掃到的導數值之和，
3.afterCount:代表scanData加入ivl后的count值，保存了所有圖形掃到的導數值之和，

假設有n個矩形進行布爾運算，那么設立一個長度為n的陣列count，count[i]代表第i個矩形，布爾運算完成之后的圖形設為 Result.
從左到右進行掃描，count值的變化情況如下:
0(尚未掃到該矩形) -----1(當前正在該矩形內部)-----0(離開該矩形)，
判斷代碼：

bool before = (int)beforeCount > 0;
bool after = (int)afterCount > 0;
int value = https://www.cnblogs.com/BYGAO/p/(!before & after) - (before & !after);

通過多載的方式，對于布爾運算進行不同的操作，

before和after即總體狀態值，為true則代表在結果圖形Result之內，否則代表在Result之外，
對于或運算的總體狀態值，從count[0]和count[1]任一值為1，考慮到或運算需要將所有圖形加入結果中，就代表當前總體狀態值為true，
而對于與運算，就需要從count[0]和count[1]所有值全為1，才能判定位于結果圖形之內，總體狀態值為true，

當進行與運算時，代碼如下:

bool before = (int)beforeCount > 0;

呼叫

inline operator int() const { return T()(counts_[0], counts_[1]); }

再呼叫

  class BinaryAnd
  {
  public:
    inline BinaryAnd() {}
    inline bool operator()(int a, int b) { return (a > 0) & (b > 0); }
  };

推廣到其他布爾運算，則是:

  class BinaryOr
  {
   ... (int a, int b) { return (a > 0) | (b > 0); }
  };
  class BinaryNot
  {
    ...(int a, int b) { return (a > 0) & !(b > 0); }
  };
  class BinaryXor
  {
    ...(int a, int b) { return (a > 0) ^ (b > 0); }
  };

通過模板和多載的方式實作對于不同的布爾運算型別實作不同的before和after取值方法，

計算完before和after的值后，計算value值，value值為1即為入邊，為-1即為出邊，這兩種情況都需要加入outputContainer中，其他情況則不需要，

例如當第一次掃到(2,4),(2,8)邊時，判斷interavl[4,8]：

beforeCount:0,0------>before=false;

afterCount: 0,1------>after=false;

得出value：0

因此不加入，

掃到(3,5),(3,9)邊時，判斷interval[5,8]和[5,9]：

對于[5,8]

beforeCount:0,1------>before=false;

afterCount: 1,1------>after=true;

得出value：1

因此作為入邊加入，

對于[8,9]

beforeCount:0,0------>before=false;

afterCount: 1,0------>after=false;

得出value：0

掃到(4,4),(4,8)邊時，判斷interval[4,5]和[5,8]：

對于[4,5]

beforeCount:0,1------>before=false;

afterCount: 0,0------>after=false;

得出value：0

對于[5,8]

beforeCount:1,1------>before=true;

afterCount: 1,0------>after=false;

得出value：-1

作為出邊加入，

掃到(7,5),(7,9)邊時，判斷interval[5,9]：

對于[5,9]

beforeCount:1,0------>before=false;

afterCount: 0,0------>after=false;

得出value：0  

最后兩個interval判斷通過，需要注意的是,雖然都是[5,8]區間，但后續5，8會分別與prevCoord（x坐標）聯合形成端點坐標，

體現在結果里就是(3,5),(3,8),(6,5),(6,8)四個端點，

參考資料：

https://www.boost.org/doc/libs/1_75_0/libs/polygon/doc/index.htm
https://www.boost.org/doc/libs/1_75_0/libs/polygon/doc/GTL_boostcon2009.pdf
https://www.boost.org/doc/libs/1_75_0/libs/polygon/doc/GTL_boostcon_draft03.pdf

標籤：其他

上一篇：女生25歲結婚算晚嗎

下一篇：U校園自動答題和雨課堂刷視頻腳本使用教程