范俊甫，孔維華，馬 廷，周成虎，季 民，周玉科

1.山東理工大學(xué)建筑工程學(xué)院，山東 淄博255049；2.中國科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國家重點實驗室，北京100101；3.山東科技大學(xué)測繪科學(xué)與工程學(xué)院，山東 青島266590

1 引 言

多邊形疊加分析是地理信息系統(tǒng)常用的空間分析工具之一，具有典型的高算法復(fù)雜度和計算時間密集性特征［1］，在空間分析算法體系中占有重要地位，是地理數(shù)據(jù)處理領(lǐng)域所面臨的核心且困難的基礎(chǔ)問題之一［2－3］。簡單多邊形的相交測試是線性時間且可以變換為線段求交問題采用Shamos－Hoey算法［4］或 Bentley－Ottmann算法［5］實現(xiàn)快速求解，而對于復(fù)雜多邊形的疊置分析問題，最壞情況下則需要O（N2）的時間［6］。簡單要素模型條件下的任意多邊形疊加分析問題通?；诙噙呅尾眉羲惴ń鉀Q，目前公認的既支持任意形狀多邊形裁剪又能在有限時間內(nèi)獲得正確計算結(jié)果的算法包括 Weiler算法［7］、Vatti算法［8］和Greiner－Hormann算法［9－10］。其中后兩者所采用的雙線性鏈表數(shù)據(jù)結(jié)構(gòu)和計算速度均優(yōu)于前者［11］。盡管 Greiner－Hormann算法被認為比Vatti算法具有更簡單的原理和實現(xiàn)過程，也聲稱擁有更高的執(zhí)行效率，但在某些情況下其計算效率卻低于 Vatti算法［12－13］。文獻［14］實現(xiàn)了對Vatti算法的改進，解決了輸入多邊形中不允許出現(xiàn)水平邊的問題，增強了算法穩(wěn)定性，但其依靠遞歸實現(xiàn)的交點求解在處理大數(shù)據(jù)時易出現(xiàn)資源消耗過大的問題［15］。盡管上述多邊形裁剪算法具有精度高的優(yōu)點，但是在數(shù)據(jù)結(jié)構(gòu)復(fù)雜度和計算量等多個方面卻表現(xiàn)出了一定的不足。根據(jù)文獻［16］的試驗結(jié)果，基于平面掃描和線段求交等算法實現(xiàn)的多邊形裁剪算法的時間開銷隨多邊形頂點數(shù)量的增加幾乎均呈上升趨勢，以Vatti算法為例，其計算時間隨多邊形頂點數(shù)量的增加表現(xiàn)出近似O（N2）的快速增長特征［17］，這對處理包含大量頂點的多邊形疊加分析問題非常不利。

與矢量數(shù)據(jù)相比，柵格數(shù)據(jù)更適用于空間建模、尺度分析和疊加分析操作［18－19］，且柵格數(shù)據(jù)分辨率越精細，越能更加細致地表現(xiàn)地理特征［20］，柵格化處理是擴展矢量數(shù)據(jù)共享范圍的常用手段［21］。矢量數(shù)據(jù)的柵格化處理是克服矢量數(shù)據(jù)計算復(fù)雜、效率低且實現(xiàn)困難的有效途徑。文獻［22］將柵格化的思想應(yīng)用于矢量電子地圖的更新變化檢測中，在大幅提高計算速度的同時保證了計算結(jié)果的可靠性。而多邊形柵格化的過程是有損過程，涉及多邊形面積、周長、形狀以及拓撲結(jié)構(gòu)等多方面信息，因此必須對柵格化處理后的計算結(jié)果的面積誤差進行分析并加以控制［23－24］，柵格化處理過程產(chǎn)生的誤差受網(wǎng)格單元大小、圖形形狀和結(jié)構(gòu)等多個因素的影響［25］。本文嘗試將離散化處理思想引入多邊形裁剪過程中，提出了一種基于柵格化處理思想的多邊形裁剪算法——RaPC算法，來解決傳統(tǒng)多邊形裁剪算法在處理包含大量頂點的多邊形疊加時的低效問題。

本文組織結(jié)構(gòu)為：首先闡述RaPC算法原理，重點描述邊界搜索追蹤方法和頂點構(gòu)環(huán)方法；其次分析RaPC算法計算結(jié)果的面積誤差特征；再開展試驗比較其與Vatti算法的計算效率及算法復(fù)雜度差異；最后得出結(jié)論。

2 RaPC算法原理

2.1 算法基本思想及流程

RaPC算法的基本思想是將空間范圍進行離散化，按照離散化后網(wǎng)格與疊加多邊形間的包含關(guān)系將空間區(qū)域定義為4種類型：目標多邊形區(qū)域、裁剪多邊形區(qū)域、重疊區(qū)域、空白區(qū)。與之對應(yīng)，離散網(wǎng)格同樣包含4種類型：SUBJP（1）、CLIPP（2）、SUBJP＿CLIPP（3）、NONE＿SUBJP＿CLIPP（0）。完成網(wǎng)格離散化過程后，按照計算需求搜索特定類型的網(wǎng)格進行輸出，即完成了多邊形裁剪過程。

RaPC算法由多邊形離散化、網(wǎng)格填充、結(jié)果輸出3個核心步驟構(gòu)成。多邊形離散化的實質(zhì)是將空間區(qū)域劃分為規(guī)則網(wǎng)格，可采用矩陣結(jié)構(gòu)來存儲。初始化矩陣需要3個參數(shù)，分別是多邊形幾何對象P、網(wǎng)格單元大小cellsize和多邊形類型type（目標多邊形或裁剪多邊形）。矩陣的元素代表空間區(qū)域內(nèi)的網(wǎng)格單元，元素取值的不同代表所屬空間區(qū)域的不同。疊加操作算子支持求交（INTSEC）、求差（DIFF）、合并（MERGE）3 種類型。

網(wǎng)格填充的過程是遍歷矩陣并對每個元素進行多邊形包含測試的過程，每個網(wǎng)格根據(jù)其特征點與目標或裁剪多邊形的包含關(guān)系的不同被賦予不同的值，本文采用射線法進行點在多邊形內(nèi)探測［26］。

RaPC算法支持兩種不同的結(jié)果輸出形式：離散網(wǎng)格輸出和單一多邊形整體輸出，前者指將每個網(wǎng)格作為單一的裁剪結(jié)果進行輸出，后者則是將裁剪完成的所有網(wǎng)格進行聚合，形成單一的幾何對象并輸出。

2.2 邊界網(wǎng)格環(huán)繞追蹤算法

不失一般性，考慮簡單多邊形的情形，如圖1所示，假設(shè)多邊形P1是兩個多邊形疊加分析的計算結(jié)果，與之相對應(yīng)，RaPC算法的計算結(jié)果如圖1中8×8的格網(wǎng)所示，環(huán)繞邊界追蹤算法的目標是在該矩陣中進行搜索追蹤，找出所有外環(huán)的入口，在每個入口定義出1個外環(huán)和若干個內(nèi)環(huán)，構(gòu)造出最接近于多邊形P1的圖斑。

邊界環(huán)繞追蹤算法的具體流程如下：

（1）按照從上至下、從左至右的規(guī)則遍歷網(wǎng)格，遍歷過的網(wǎng)格標記為已訪問狀態(tài)。

（2）將首個未被訪問且為期望類型的網(wǎng)格標記為入口網(wǎng)格，如圖1中第2行第4列的網(wǎng)格，記為g（1，3），同時創(chuàng)建一個新的外環(huán)對象RE（采用雙向鏈表實現(xiàn)）并將g（1，3）作為頭節(jié)點加入RE，此時頭節(jié)點的前驅(qū)和后繼節(jié)點都為空，開始環(huán)繞追蹤構(gòu)環(huán)的過程。

（3）以g（1，3）為中心，采用圖2（a）所示3×3窗口進行掃描，基于圖2所示行程規(guī)則搜索下一新網(wǎng)格節(jié)點并加入RE末尾，標記當前網(wǎng)格為已訪問狀態(tài)同時設(shè)置當前節(jié)點為新節(jié)點的前驅(qū)，新節(jié)點為當前節(jié)點的后繼，移動窗口至新網(wǎng)格節(jié)點繼續(xù)上述掃描過程。

（4）當尋找得到的節(jié)點為RE的頭節(jié)點時，標志環(huán)RE發(fā)生閉合，以該頭節(jié)點為入口的追蹤構(gòu)環(huán)過程完成。

（5）在環(huán)RE內(nèi)部執(zhí)行內(nèi)環(huán)的搜索追蹤過程，搜索到的內(nèi)環(huán)加入RE的holes容器并輸出。

（6）從上一入口網(wǎng)格處的下一（右側(cè)）網(wǎng)格開始，繼續(xù)遍歷剩余網(wǎng)格單元，直至完成所有網(wǎng)格的遍歷，找出所有的外環(huán)及每個外環(huán)所包含的內(nèi)環(huán)，算法結(jié)束。

圖1 簡單多邊形圖斑示意圖Fig.1 Patch of simple polygon

上述窗口掃描的規(guī)則決定了追蹤構(gòu)環(huán)為順時針進行，窗口掃描起始位置判定、窗口網(wǎng)格遍歷的詳細規(guī)則如圖2所示。圖2（a）—（c）中，3×3的窗口中心網(wǎng)格為當前節(jié)點，編號為0，從0節(jié)點左側(cè)網(wǎng)格開始順時針編碼依次為1—8，從網(wǎng)格1—8至網(wǎng)格0的實線箭頭表示從前一節(jié)點至當前節(jié)點的前進方向（也即邊界網(wǎng)格的走向），包圍窗口的虛線箭頭表示在當前前進方向條件下窗口掃描的行程（或環(huán)繞追蹤順序），Δr和Δc分別為當前網(wǎng)格與前一網(wǎng)格的行列號之差，為搜索輔助變量。窗口掃描過程中存在特殊情況，如圖1中遍歷至g（6，3）網(wǎng)格時，采用上述窗口掃描方法無法找到期望網(wǎng)格，此時需將當前網(wǎng)格的前一網(wǎng)格作為下一節(jié)點加入環(huán)的末尾，而此時當前網(wǎng)格成為“前一”網(wǎng)格，網(wǎng)格g（5，3）將會被記錄兩次，這與圖斑的真實情況相符。完成搜索后，將結(jié)果轉(zhuǎn)為GIS矢量數(shù)據(jù)結(jié)構(gòu)。

2.3 島、洞處理規(guī)則

洞是多邊形內(nèi)環(huán)的表現(xiàn)形式，RaPC算法支持包含洞、島的任意多邊形之間的疊加裁剪。當完成了一個外環(huán)的搜索過程之后即開始在該外環(huán)內(nèi)部搜索內(nèi)環(huán)，本文采用外環(huán)邊界跨越數(shù)統(tǒng)計的方式判斷掃描窗口網(wǎng)格是否位于當前外環(huán)內(nèi)。邊界跨越計數(shù)方法類似于經(jīng)典的用于解決點面包含問題的射線算法，它通過統(tǒng)計某一點沿某一方向（如水平方向）與多邊形邊界的交點個數(shù)來判斷該點是否被多邊形包圍。本文中的邊界跨越計數(shù)方法操作的點是離散網(wǎng)格，而邊界對應(yīng)于由離散網(wǎng)格按照一定次序構(gòu)成的環(huán)。RaPC算法中內(nèi)環(huán)的搜索算法過程如圖3所示。

圖2 窗口掃描追蹤的行程規(guī)則Fig.2 Route rules for window－based scanning and tracking

圖3 內(nèi)環(huán)搜索流程Fig.3 Flow for interior ring searching

圖3中，CT是掃描窗口網(wǎng)格在網(wǎng)格矩陣的每一行中從左至右對外環(huán)ring的邊界跨越次數(shù)（crossing time），根據(jù)其奇偶性的不同確定網(wǎng)格點與外環(huán)的包圍關(guān)系；“網(wǎng)格在環(huán)上”指的是某網(wǎng)格是構(gòu)成環(huán)邊界的網(wǎng)格單元，如圖1中網(wǎng)格g（1，3）在環(huán)上，而g（2，3）不在環(huán)上；奇異網(wǎng)格特指3種不構(gòu)成邊跨越條件的網(wǎng)格組合，如圖4（a）、（b）、（c）所示，假水平邊指在環(huán)上但不連續(xù)的水平相鄰網(wǎng)格組合，如圖4（d）所示。

圖4 3種類型的奇異網(wǎng)格組合與假水平邊Fig.4 Three odd combination types of grids and fake horizontal edge

如圖5所示，3個特例分別是單網(wǎng)格非跨越特例、在環(huán)上連續(xù)的水平邊構(gòu)成邊界跨越特例和同一行水平分布的相鄰網(wǎng)格單獨構(gòu)環(huán)特例。

圖5 內(nèi)環(huán)搜索過程中的3種特例情況Fig.5 Three exceptions during searching of interior ring

按照上述算法步驟尋找到滿足條件的內(nèi)環(huán)入口網(wǎng)格后，采用2.2節(jié)所述算法構(gòu)造順時針的環(huán)。由于目標是生成內(nèi)環(huán)，因此在構(gòu)環(huán)完畢后須進行點的逆序操作。生成內(nèi)環(huán)后，對內(nèi)環(huán)所包含的所有網(wǎng)格點進行遍歷，設(shè)置為未訪問狀態(tài)，目的是繼續(xù)在其內(nèi)部搜索島嶼多邊形。島的探測、邊界提取方法與之前所述外環(huán)的邊界網(wǎng)格環(huán)繞追蹤算法完全相同。然而，按照前述方法完成島嶼多邊形的邊界追蹤之后，必須在其內(nèi)部再次探測是否存在內(nèi)環(huán)，若存在則依據(jù)本節(jié)所述方法提取內(nèi)環(huán)的邊界，這說明RaPC方法可對多層洞、島嵌套的多邊形提供遞歸探測支持。

3 RaPC算法誤差分析

Vatti算法是公認的經(jīng)典任意多邊形裁剪算法［11］，被開源及商業(yè) GIS軟件廣泛采用［14］，本文選擇Vatti算法進行對比。根據(jù)前人的研究成果，柵格化處理是一個有損轉(zhuǎn)化過程，且誤差不可避免［21］，這些誤差來自多方面，例如網(wǎng)格取舍策略、柵格化算法和所采用的數(shù)據(jù)結(jié)構(gòu)等。目前對此類誤差產(chǎn)生的原因、控制模型和誤差分析方法等均有了較為詳盡的研究［25］，出現(xiàn)了一些能夠確保柵格化轉(zhuǎn)換結(jié)果面積精度和穩(wěn)定性的模型和分析方法［23－24］。由于RaPC算法在多邊形柵格化過程中采用網(wǎng)格中心點與多邊形的包含關(guān)系作為網(wǎng)格取舍依據(jù)，未涉及復(fù)雜的網(wǎng)格內(nèi)部面積計算和統(tǒng)計，因此本節(jié)針對此種處理方式下RaPC算法所得到的多邊形裁剪計算結(jié)果的相對面積誤差的變化規(guī)律進行分析。相對面積誤差e定義如下

式中，ARaPC為采用RaPC算法得到的裁剪結(jié)果面積值；AVector為采用Vatti算法得到的裁剪結(jié)果面積值。試驗所采用的數(shù)據(jù)如圖6（a）所示（試驗區(qū)長寬分別約為840km和562km），多邊形求差的計算結(jié)果如圖6（b）所示，而圖6（b－1）為 Vatti算法的計算結(jié)果細節(jié)，圖6（b－2）為RaPC算法的計算結(jié)果細節(jié)。

圖6 面積誤差統(tǒng)計試驗數(shù)據(jù)與矢量算法計算結(jié)果Fig.6 Experimental data for statistics of area error and calculation result of vector algorithm

Vatti算法得到的結(jié)果多邊形面積為102 331 740 839.384m2，當 網(wǎng) 格 大 小 為 10km時，RaPC算法計算結(jié)果的相對面積誤差為－0.324%，而當網(wǎng)格尺寸縮小至1km（圖6（b－2））時，誤差僅為－0.012%，誤差隨網(wǎng)格大小的增加整體上呈現(xiàn)出增大的趨勢，同時具有強烈的不穩(wěn)定性，這與邊界網(wǎng)格單元的取舍策略存在直接關(guān)系。當采用網(wǎng)格中心點與多邊形的包圍關(guān)系作為網(wǎng)格取舍依據(jù)時，邊界網(wǎng)格單元的取舍更多地表現(xiàn)出了一種隨機性特征，可采用EAC模型［24］進行誤差控制和約束。因此，RaPC算法誤差總體處于較低水平且可以通過調(diào)整網(wǎng)格大小進行控制。

4 RaPC算法效率分析

本文采用長春市居民地多邊形數(shù)據(jù)（兩圖層均包含3959個多邊形，試驗區(qū)長寬分別約為9.4km和7.8km）作為試驗數(shù)據(jù)比較Vatti算法與RaPC算法在計算多邊形圖層求交時的效率差異。在相同硬件試驗條件下的試驗結(jié)果如表1所示。其中，基于Vatti算法的計算時間約為1.060s，計算結(jié)果圖層內(nèi)的多邊形圖形面積為11 206 600m2。

表1 RaPC求交算法試驗結(jié)果及面積誤差統(tǒng)計結(jié)果Tab.1 Experimental results of RaPC－based intersection algorithm and statistical results of area error

上述結(jié)果表明，隨網(wǎng)格單元的增大，RaPC算法的計算效率迅速提高，同時誤差也隨之增大，當網(wǎng)格單元為15m時，得到了與Vatti算法相當?shù)挠嬎阈?。因此，RaPC算法能夠通過調(diào)整網(wǎng)格大小獲得精度與效率的平衡。Vatti算法的計算效率對多邊形頂點數(shù)量高度敏感［17］。本文通過比較具有相同形狀但不同頂點數(shù)量的多邊形間的求交計算時間來觀察兩種算法的效率差異。多邊形頂點數(shù)量從1000至30 000遞增時，試驗結(jié)果如圖7所示。

圖7 不同網(wǎng)格大小和多邊形頂點數(shù)量條件下RaPC算法與Vatti算法的時間開銷對比Fig.7 Time costs comparison of the RaPC algorithm and the Vatti algorithm with different grid sizes and polygon vertex amounts

圖7表明，與Vatti算法類似，多邊形頂點數(shù)量同樣影響RaPC算法的計算效率。當多邊形所包含的頂點數(shù)量較少時，Vatti算法具有較高的計算效率，隨著多邊形頂點數(shù)量的增加，Vatti算法的計算效率快速降低。而RaPC算法的時間開銷則表現(xiàn)出了較為平穩(wěn)的線性增長模式，且隨網(wǎng)格增大，線性增長模型的斜率降低，說明增長變慢。因此，盡管當采用較小的網(wǎng)格時RaPC算法的時間開銷要高于Vatti算法，但是在處理包含大量頂點的多邊形的疊加操作時，RaPC算法更有優(yōu)勢。實際上，RaPC算法的計算效率更多地受網(wǎng)格大小的影響。

從時間復(fù)雜度角度比較，最差情況下，Vatti算法的時間復(fù)雜度為O（（p－2）2），其中p為單次疊置操作中兩個多邊形多具有的頂點數(shù)量［9］。RaPC算法的原子操作為點在多邊形內(nèi)的判斷過程，該過程所需要的浮點數(shù)計算次數(shù)是多邊形頂點數(shù)量的線性函數(shù)，而點在多邊形內(nèi)的判斷次數(shù)為2N，其中N為網(wǎng)格單元數(shù)量，它是網(wǎng)格單元大小的二次函數(shù)。因此，當網(wǎng)格單元大小恒定時，RaPC算法的時間復(fù)雜度為O（2N），這與本文的試驗結(jié)果相符。

從空間復(fù)雜度角度比較，RaPC算法的柵格化處理過程具有典型的高空間復(fù)雜度特征。Vatti算法僅通過定義一組邊界線來存儲多邊形的所有頂點，通過自底向上的“掃描束”實現(xiàn)交點結(jié)算，同時僅為每個掃描束維護一個活動邊表。因此Vatti算法的內(nèi)存開銷僅與多邊形頂點數(shù)量線性相關(guān)，其空間復(fù)雜度為O（n），n為多邊形頂點數(shù)量。而RaPC算法并不存儲多邊形頂點，它存儲的是多邊形所包圍的離散化空間范圍，因此每次疊加計算所占用的存儲空間與多邊形空間范圍和網(wǎng)格大小的比例系數(shù)密切相關(guān)。當空間范圍確定時，RaPC算法的空間復(fù)雜度為O（p2），即RaPC算法的空間復(fù)雜度隨網(wǎng)格單元邊長減小呈平方增長，其中p為比例系數(shù)，可由公式（2）計算

式中，L、W分別為離散化空間范圍的長和寬；l為網(wǎng)格單元邊長；N為網(wǎng)格單元數(shù)量。盡管存在上述不足，但在當今計算機硬件技術(shù)進步的背景下，內(nèi)存限制已不再是算法面臨的主要瓶頸，RaPC算法以空間換時間的處理方式能獲得可期待的計算效率改進，同時也有望在GPU等新型計算架構(gòu)下進一步提高計算效率。

5 結(jié) 論

本文針對傳統(tǒng)矢量多邊形裁剪算法在處理包含大量頂點的多邊形疊加分析時所面臨的效率下降問題，提出了一種基于柵格化處理思想的多邊形裁剪算法——RaPC算法，并對其計算結(jié)果的面積誤差進行分析和討論，與經(jīng)典的Vatti算法進行了對比。試驗結(jié)果表明，RaPC算法的計算效率受網(wǎng)格單元大小和多邊形頂點數(shù)量雙重因素的影響，其時間開銷隨多邊形頂點數(shù)量呈線性增長，隨網(wǎng)格大小增大呈冪函數(shù)規(guī)律快速下降，通過控制網(wǎng)格大小能實現(xiàn)對時間開銷和面積誤差的控制和調(diào)整。Vatti算法在處理小數(shù)據(jù)時較為高效，而RaPC算法在處理包含大量頂點的多邊形數(shù)據(jù)時更有優(yōu)勢。因此，RaPC算法為在一定精度水平下大規(guī)模多邊形間的裁剪問題提供了一個潛在的求解方法。

此外，多邊形裁剪過程具有典型的高計算密集性特征，傳統(tǒng)的多邊形裁剪算法計算過程與數(shù)據(jù)結(jié)構(gòu)緊密耦合，難以實現(xiàn)細粒度并行化，而基于RaPC算法的多邊形裁剪問題的細粒度并行加速求解是下一步的研究方向。

［1］ DOWERS S，GITTINGS B M，MINETER M J.Towards a Framework for High－performance Geocomputation：Handling Vector－topology within a Distributed Service Environment［J］.Computers，Environment and Urban Systems，2000，24（5）：471－486.

［2］ GOODCHILD M F.Statistical Aspects of the Polygon Overlay Problem［M］∥DUTTON G.Harvard Papers on Geographic Information Systems.Reading，MA：Addison－Wesley Publishing Company，1977.

［3］ AGARWAL D，PURI S，HE Xi，et al.A System for GIS Polygonal Overlay Computation on Linux Cluster：An Experience and Performance Report［C］∥Proceedings of the 2012IEEE 26th International Parallel and Distributed Processing Symposium Workshops ＆ PhD Forum.Shanghai：IEEE，2012：1433－1439.

［4］ SHAMOS M I，HOEY D.Geometric Intersection Problems［C］∥Proceedings of the 17th Annual Symposium on Foundations of Computer Science.Washington DC：IEEE，1976：208－215.

［5］ BENTLEY J L，OTTMANN T A.Algorithms for Reporting and Counting Geometric Intersections［J］.IEEE Transac－tions on Computers，1979，C－28（9）：643－647.

［6］ PREPARATA F P，SHAMOS M I.Computational Geometry：An Introduction［M］.Translated by Zhuang Xingu.Beijing：Science Press， 1990.（PREPARATA F P，SHAMOS M I.計算幾何導(dǎo)論［M］.莊心谷，譯.北京：科學(xué)出版社，1990.）

［7］ WEILER K，ATHERTON P.Hidden Surface Removal Using Polygon Area Sorting［C］∥Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques.New York：ACM Press，1977：214－222.

［8］ VATTI BR.A Generic Solution to Polygon Clipping［J］.Communications of the ACM，1992，35（7）：56－63.

［9］ GREINER G，HORMANN K.Efficient Clipping of Arbitrary Polygons［J］.ACM Transactions on Graphics，1998，17（2）：71－83.

［10］ CHEN Zhanlong，WU Xincai，WU Liang.Polygon Overlay Analysis Algorithm Based on Monotone Chain and STR Tree in the Simple Feature Mode［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：102－108.（陳占龍，吳信才，吳亮.基于單調(diào)鏈和STR樹的簡單要素模型多邊形 疊 置 分 析 算 法 ［J］.測 繪 學(xué) 報，2010，39（1）：102－108.）

［11］ LIU Yongkui，GAO Yun，HUANG Youqun.An Efficient Algorithm for Polygon Clipping［J］.Journal of Software，2003，14（4）：845－856.（劉勇奎，高云，黃有群.一個有效的多邊形裁剪算法［J］.軟件學(xué)報，2003，14（4）：845－856.）

［12］ KUI Liuyong，QIANG Wangxiao，ZHE Baoshu，et al.An Algorithm for Polygon Clipping，and for Determining Polygon Intersections and Unions［J］.Computers ＆Geosciences，2007，33（5）：589－598.

［13］ MARTíNEZ F，RUEDA A J，F(xiàn)EITO F R.A New Algorithm for Computing Boolean Operations on Polygons［J］.Computers ＆ Geosciences，2009，35（6）：1177－1185.

［14］ MURTA A.A General Polygon Clipping Library［EB／OL］.［2013－11－01］.http：∥www.cs.man.ac.uk／～toby／alan／software／gpc.html.

［15］ XIE Zhong，WEI Dongqi，WU Liang，et al.Graph Model of Polygon Clipping Using Simple Vector Data［J］.Acta Geodaetica et CartographicaSinica，2009，38（4）：369－374.（謝忠，魏東琦，吳亮，等.簡單矢量數(shù)據(jù)多邊形裁剪問題的圖模型［J］.測繪學(xué)報，2009，38（4）：369－374.）

［16］ LEONOV M.Comparison of the Different Algorithms for Polygon Boolean Operations［EB／OL］.［2013－11－02］.http：∥www.complex－a5.ru／polyboolean／comp.html.

［17］ FAN Junfu，MA Ting，JI Min，et al.Implementation and Optimization of Eight Parallel Polygon Overlapping Tools with OpenMP at the Feature Layer Level in GIS［J］.Progressin Geography，2013，32（12）：1835－1844.（范俊甫，馬廷，季民，等.GIS中8種圖層級多核并行多邊形疊置分析工具的實現(xiàn)及優(yōu)化方法［J］.地理科學(xué)進展，2013，32（12）：1835－1844.）

［18］ BATES P D，DEROO A P J.A Simple Raster－based Model for Flood Inundation Simulation［J］.Journal of Hydrology，2000，236（1－2）：54－77.

［19］ YANG Cunjian，ZHANG Zengxiang.Models of Accuracy Loss During Rasterizing LanduseVector Data with Multiscale Grid Size［J］.Geographical Research，2001，20（4）：416－422.（楊存建，張增祥.矢量數(shù)據(jù)在多尺度柵格化中的精度損失模型探討［J］.地理研究，2001，20（4）：416－422.）

［20］ CHEN Shupeng，LU Xuejun，ZHOU Chenghu.Introduction to Geographic Information Systems［M］.Beijing：Science Press，1999.（陳述彭，魯學(xué)軍，周成虎.地理信息系統(tǒng)導(dǎo)論［M］.北京：科學(xué)出版社，1999.）

［21］ BAI Yan，LIAO Shunbao，SUN Jiulin.Scale Effect and Methods for Accuracy Evaluation of Attribute Information Loss in Rasterization［J］.Journal of Geographical Sciences，2011，21（6）：1089－1100.

［22］ LI Yuguang，LI Lianying，LI Qingquan，et al.Vector Map Geometric Data Change Detection Based on Grid Method［J］.Geospatial Information，2010，8（1）：142－146.（李宇光，李蓮營，李清泉，等.基于柵格化思想的矢量電子地圖幾何變化檢測［J］.地理空間信息，2010，8（1）：142－146.）

［23］ CHEN Jianjun，ZHOU Chenghu，CHENG Weiming.Area Error Analysis of Vector to Raster Conversion of Areal Feature in GIS［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：344－350.（陳建軍，周成虎，程維明.GIS中面狀要素矢量柵格化的面積誤差分析［J］.測繪學(xué)報，2007，36（3）：344－350.）

［24］ ZHOU Chenghu，OU Yang，YANG Liao，et al.An E－qual Area Conversion Model for Rasterization of Vector Polygons［J］.Science in China：Series D：Earth Sciences，2007，50（S1）：169－175.（周成虎，歐陽，楊遼，等.矢量多邊形柵格化的保積優(yōu)化模型［J］.中國科學(xué)D輯：地球科學(xué)，2006，36（增刊Ⅱ）：157－163.）

［25］ SHORTRIDGE A M.Geometric Variability of Raster Cell Class Assignment［J］.International Journal of Geographical Information Science，2004，18（6）：539－558.

［26］ ZHOU Peide.Computational Geometry Algorithm Design and Analysis（Fourth Edition）［M］.Beijing：Tsinghua University Press，2011.（周培德.計算幾何：算法設(shè)計與分析（第4版）［M］.北京：清華大學(xué)出版社，2011.）