RaPC：一種基于柵格化思想的多邊形裁剪算法及其誤差分析

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

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

1 引 言

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

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

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

2 RaPC算法原理

2.1 算法基本思想及流程

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 簡(jiǎn)單多邊形圖斑示意圖Fig.1 Patch of simple polygon

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

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

洞是多邊形內(nèi)環(huán)的表現(xiàn)形式，RaPC算法支持包含洞、島的任意多邊形之間的疊加裁剪。當(dāng)完成了一個(gè)外環(huán)的搜索過(guò)程之后即開始在該外環(huán)內(nèi)部搜索內(nèi)環(huán)，本文采用外環(huán)邊界跨越數(shù)統(tǒng)計(jì)的方式判斷掃描窗口網(wǎng)格是否位于當(dāng)前外環(huán)內(nèi)。邊界跨越計(jì)數(shù)方法類似于經(jīng)典的用于解決點(diǎn)面包含問(wèn)題的射線算法，它通過(guò)統(tǒng)計(jì)某一點(diǎn)沿某一方向（如水平方向）與多邊形邊界的交點(diǎn)個(gè)數(shù)來(lái)判斷該點(diǎn)是否被多邊形包圍。本文中的邊界跨越計(jì)數(shù)方法操作的點(diǎn)是離散網(wǎng)格，而邊界對(duì)應(yīng)于由離散網(wǎng)格按照一定次序構(gòu)成的環(huán)。RaPC算法中內(nèi)環(huán)的搜索算法過(guò)程如圖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)格矩陣的每一行中從左至右對(duì)外環(huán)ring的邊界跨越次數(shù)（crossing time），根據(jù)其奇偶性的不同確定網(wǎng)格點(diǎn)與外環(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個(gè)特例分別是單網(wǎng)格非跨越特例、在環(huán)上連續(xù)的水平邊構(gòu)成邊界跨越特例和同一行水平分布的相鄰網(wǎng)格單獨(dú)構(gòu)環(huán)特例。

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

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

3 RaPC算法誤差分析

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

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

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

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

4 RaPC算法效率分析

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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

［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.計(jì)算幾何導(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樹的簡(jiǎn)單要素模型多邊形 疊 置 分 析 算 法 ［J］.測(cè) 繪 學(xué) 報(bào)，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.（劉勇奎，高云，黃有群.一個(gè)有效的多邊形裁剪算法［J］.軟件學(xué)報(bào)，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.（謝忠，魏東琦，吳亮，等.簡(jiǎn)單矢量數(shù)據(jù)多邊形裁剪問(wèn)題的圖模型［J］.測(cè)繪學(xué)報(bào)，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種圖層級(jí)多核并行多邊形疊置分析工具的實(shí)現(xiàn)及優(yōu)化方法［J］.地理科學(xué)進(jìn)展，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.（楊存建，張?jiān)鱿?矢量數(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.（李宇光，李蓮營(yíng)，李清泉，等.基于柵格化思想的矢量電子地圖幾何變化檢測(cè)［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］.測(cè)繪學(xué)報(bào)，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áng)，楊遼，等.矢量多邊形柵格化的保積優(yōu)化模型［J］.中國(guó)科學(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.（周培德.計(jì)算幾何：算法設(shè)計(jì)與分析（第4版）［M］.北京：清華大學(xué)出版社，2011.）