陳占龍,吳信才,吳 亮

1.中國(guó)地質(zhì)大學(xué)信息工程學(xué)院,湖北武漢430075;2.教育部地理信息系統(tǒng)軟件開(kāi)發(fā)及應(yīng)用工程中心,湖北武漢430074

基于單調(diào)鏈和STR樹(shù)的簡(jiǎn)單要素模型多邊形疊置分析算法

陳占龍1,2,吳信才1,吳 亮1

1.中國(guó)地質(zhì)大學(xué)信息工程學(xué)院,湖北武漢430075;2.教育部地理信息系統(tǒng)軟件開(kāi)發(fā)及應(yīng)用工程中心,湖北武漢430074

針對(duì)簡(jiǎn)單要素類(lèi)疊置分析的特點(diǎn),利用STR(sort-tile-recursive)樹(shù)索引改進(jìn)算法能夠?qū)⒈M量多的多邊形節(jié)點(diǎn)存儲(chǔ)在STR樹(shù)的葉節(jié)點(diǎn)中,減少在空間數(shù)據(jù)庫(kù)中檢索多邊形時(shí)的磁盤(pán)讀取次數(shù)。算法對(duì)多邊形邊界進(jìn)行關(guān)于坐標(biāo)軸的單調(diào)鏈分割,并在多邊形求交過(guò)程中引入平面圖的概念,利用平面圖元素與各個(gè)多邊形的拓?fù)潢P(guān)系來(lái)組織疊加后的多邊形。該算法能有效減少求交點(diǎn)的時(shí)間,在線段求交中加入對(duì)連續(xù)出入點(diǎn)特殊數(shù)據(jù)的處理。同時(shí)該算法使用單調(diào)鏈減少多邊形求交過(guò)程的比較次數(shù),與其他使用雙鏈表或單鏈表的算法相比具有占用空間少及處理速度快的特點(diǎn)。

簡(jiǎn)單要素模型;單調(diào)鏈;STR樹(shù);平面圖;空間疊置

1 引 言

矢量圖形疊加算法是 GIS空間分析中各種功能的基礎(chǔ)。自從1999年OGC提出簡(jiǎn)單要素模型以來(lái),在當(dāng)今各主流地理信息軟件中,大部分都引入了不維護(hù)拓?fù)湫畔⒌臄?shù)據(jù)模型,如ArcGIS中的shapefile數(shù)據(jù)格式和Map GIS 7.0簡(jiǎn)單要素類(lèi)模型等。拓?fù)淠Ｐ偷氖噶刊B置分析要求在操作前每一層都是平面增強(qiáng)的,即已經(jīng)建立了完整的拓?fù)潢P(guān)系,操作后的結(jié)果也是平面增強(qiáng)的[1]。因此,在拓?fù)淠Ｐ偷寞B置分析中,如果疊置前數(shù)據(jù)層中的數(shù)據(jù)無(wú)完整的拓?fù)潢P(guān)系,則應(yīng)首先建立完整的拓?fù)潢P(guān)系。當(dāng)數(shù)據(jù)量過(guò)大時(shí),構(gòu)建拓?fù)潢P(guān)系的操作需要較多時(shí)間,且新數(shù)據(jù)層中的拓?fù)潢P(guān)系并不為用戶所關(guān)心。矢量數(shù)據(jù)的空間疊置分析能夠生成用戶感興趣的新數(shù)據(jù)層。如果能夠?qū)?fù)雜要素模型中的分析功能在簡(jiǎn)單要素模型下實(shí)現(xiàn),則可免除構(gòu)建數(shù)據(jù)拓?fù)潢P(guān)系這一約束條件,使操作更簡(jiǎn)單快捷。因無(wú)需構(gòu)建全局拓?fù)湫畔?處理速度將比原來(lái)的復(fù)雜要素模型分析更快[2]。

簡(jiǎn)單數(shù)據(jù)模型的疊置分析的核心算法思想是任意多邊形裁剪,文獻(xiàn)[3]中介紹了基于拓?fù)淠Ｐ秃秃?jiǎn)單數(shù)據(jù)模型的兩類(lèi)算法,比較了兩者的優(yōu)劣并提出可實(shí)際應(yīng)用的基于交點(diǎn)搜索的多邊形疊加分析算法?，F(xiàn)有的多邊形裁剪算法或者局限于解決某類(lèi)多邊形,或者算法結(jié)構(gòu)復(fù)雜、時(shí)間消耗大,如Sutherl-Hodgeman、梁-Barsky、NLN算法要求裁剪多邊形是凸多邊形[4-6]。而在GIS的矢量數(shù)據(jù)的實(shí)際應(yīng)用中,只有對(duì)于一般多邊形的裁剪才有普遍意義。在一般多邊形的裁剪算法中,普遍認(rèn)為只有Weiler算法和近年出現(xiàn)的Vatti算法及 Greiner-Hormann算法可以在合理的時(shí)間內(nèi)處理一般的情況[8]。在文獻(xiàn)[8]中,劉勇奎等提出用單線性鏈表數(shù)據(jù)結(jié)構(gòu)的一般多邊形的裁剪算法并給出與Vatti算法及Greiner-Hormann算法的比較結(jié)果。

本文中提出的算法首先采用單調(diào)鏈算法對(duì)輸入的多邊形進(jìn)行單調(diào)處理以減少多邊形比較的次數(shù),然后計(jì)算兩個(gè)多邊形的交點(diǎn),同時(shí)將交點(diǎn)插入到相對(duì)應(yīng)的多邊形中,該算法引入平面圖的概念,通過(guò)計(jì)算各個(gè)平面圖元素相對(duì)于兩個(gè)多邊形的拓?fù)潢P(guān)系來(lái)得到形成結(jié)果多邊形的各個(gè)平面圖元素,最后形成結(jié)果多邊形。該算法沒(méi)有運(yùn)用傳統(tǒng)的引入、引出交點(diǎn)交替配對(duì)的生成原則進(jìn)行結(jié)果多邊形的構(gòu)建,這樣做的好處是簡(jiǎn)化實(shí)現(xiàn)的過(guò)程和對(duì)異常交點(diǎn)的處理。最后引入STR樹(shù)空間索引的空間數(shù)據(jù)高效存取機(jī)制,對(duì)算法進(jìn)行改進(jìn),進(jìn)一步提高運(yùn)算速度。實(shí)踐結(jié)果表明,該算法快速、有效,具有較強(qiáng)的應(yīng)用價(jià)值。

2 相關(guān)概念

2.1 平面圖與拓?fù)湮恢?/h3>

平面圖由一系列的平面圖構(gòu)成元素組成。平面圖構(gòu)成元素主要包括節(jié)點(diǎn)(nodes)、邊(edges)和有向邊(directed edges)。節(jié)點(diǎn)記錄該節(jié)點(diǎn)的位置以及在該節(jié)點(diǎn)處的有向邊的集合,邊則記錄組成多邊形的邊界的坐標(biāo)串的結(jié)構(gòu),該結(jié)構(gòu)還是正反兩個(gè)有向邊的組合,有向邊記錄了由邊結(jié)構(gòu)的坐標(biāo)串形成的順時(shí)針和逆時(shí)針的兩個(gè)方向邊。在本文介紹的算法中,參與運(yùn)算的兩個(gè)任意多邊形通過(guò)其記錄的坐標(biāo)串組成兩個(gè)平面圖。拓?fù)湮恢檬侵竷蓚€(gè)平面圖的各個(gè)平面圖構(gòu)成元素與這兩個(gè)平面圖的位置關(guān)系。各個(gè)平面圖構(gòu)成元素中記錄了其與兩個(gè)平面圖的拓?fù)湮恢藐P(guān)系,拓?fù)湮恢玫膶傩允怯扇M〈on,left,right〉組成,on表示平面圖元素是在(on)平面圖的什么位置,left表示該平面圖元素的左邊是平面圖的什么位置, right表示該平面圖元素的右邊是平面圖的什么位置。拓?fù)湎鄬?duì)位置的值由三元組〈interior, boundary,exterior〉組成,分別記錄了該元素是在平面圖的里面、邊界和外部。本算法正是利用這些拓?fù)湮恢藐P(guān)系,建立拓?fù)湟?guī)則,從候選邊集合中找到構(gòu)成結(jié)果多邊形的邊,從而形成結(jié)果平面圖,最終形成結(jié)果多邊形。

例如,對(duì)于如圖1所示的兩個(gè)多邊形 A和B,其中多邊形 A(A1,A2,…,A5)與 B(B1,B2,…,B4)相交于點(diǎn) I1、I2、…、I4。多邊形A和B分別組成平面圖 P1和 P2,其中 P1由多邊形的 A的邊界(A1,A2,…,A5)構(gòu)成的邊組成,P2由多邊形的B的邊界(B1,B2,…,B4)構(gòu)成的邊組成。多邊形A和多邊形B的交點(diǎn)I1、I2、…、I4將多邊形A和B的邊界分割,組成結(jié)果多邊形的候選集。關(guān)于候選集的計(jì)算在后面詳細(xì)介紹。如圖1,候選集由 E1、E2、…、E5組成,其中 E1由點(diǎn) I4、A1、A2和 I1組成,E2由點(diǎn) I1、A3和 I2組成,以此類(lèi)推。由上述對(duì)拓?fù)湮恢酶拍畹亩x,在圖1中, E1相對(duì)于平面圖 P1的表達(dá)式 E1(P1,on)= boundary表示 E1在平面圖 P1的邊界上; E1(P1,left)=exterior表示 E1邊的左邊是平面圖 P1的外部;E1(P1,right)=interior,表示 E1邊的右邊是平面圖 P1的內(nèi)部;E1(P2,left)= exterior和 E1(P2,right)=exterior表示無(wú)論是E1的左邊還是 E1的右邊都在平面圖 P2的外部,因此 E1(P2,on)沒(méi)有意義,以此類(lèi)推。對(duì)于 E2,其拓?fù)湮恢萌缦率剿?/p>

圖1 多邊形平面圖示例Fig.1 The plane graph of two polygons

2.2 STR Tree和單調(diào)鏈

Leutenegger等在 1997年提出一種 STR (sort-tile-recursive)壓縮算法[9]。該算法易于實(shí)現(xiàn)。其基本思想為:假設(shè)在2維空間中有N個(gè)矩形,M是R樹(shù)結(jié)點(diǎn)的最大容量,用矩形中心點(diǎn)的x坐標(biāo)對(duì)數(shù)據(jù)矩形排序,用S= N/M個(gè)垂直切片切割數(shù)據(jù)空間,使得每個(gè)切片包含足夠的多邊形從而壓縮個(gè)節(jié)點(diǎn)。其中每個(gè)切片具有S個(gè)結(jié)點(diǎn)和S×M個(gè)矩形(最后一個(gè)切片會(huì)少于S×M個(gè)矩形)。然后在每一個(gè)垂直切片中,用矩形中心點(diǎn)的y坐標(biāo)對(duì)數(shù)據(jù)矩形排序,每M個(gè)矩形一組依次壓入結(jié)點(diǎn),自下而上一次一層遞歸生成整個(gè)R樹(shù)。

由STR的壓縮算法可知,在壓縮R樹(shù)中的每一層中,除了最后一個(gè)結(jié)點(diǎn)可能不滿外,其他所有結(jié)點(diǎn)都是滿的。因此可以獲得幾乎100%的空間利用率。這種索引樹(shù)的方式正好滿足簡(jiǎn)單要素類(lèi)疊加分析中一次建立索引的需求,即一次建立,不需要?jiǎng)討B(tài)構(gòu)建索引樹(shù),而經(jīng)典的R樹(shù)大都是動(dòng)態(tài)建立,空間利用率不高。

鏈(或稱(chēng)多邊形鏈)C=(u1,u2,…,un)是一個(gè)具有頂點(diǎn)集{u1,…,un}和邊集n-1}的平面圖。若正交于 l的一條直線恰好交C于一點(diǎn),則稱(chēng)折線 C關(guān)于直線l是單調(diào)的,如圖2。下面介紹單調(diào)鏈的概念。將折線C上的各個(gè)頂點(diǎn)ui投影到直線l上,得到投影點(diǎn) l(ui),若l(ui)(i≠0)距離 l(u0)以遞增的順序出現(xiàn),則稱(chēng)折線C關(guān)于直線l單調(diào)[10]。單調(diào)鏈主要有以下兩個(gè)性質(zhì):①不相交性質(zhì),屬于同一個(gè)單調(diào)鏈的各個(gè)線段不會(huì)相交;②端點(diǎn)組成外包矩形性質(zhì),在一個(gè)單調(diào)鏈中連續(xù)的線段的外包矩形為這些線段組成的子單調(diào)鏈的端點(diǎn)組成的外包矩形。圖2是單調(diào)鏈的定義圖,圖3是多邊形分割的各個(gè)單調(diào)鏈的示意圖。

圖2 C對(duì)l的單調(diào)鏈Fig.2 Monotone chain

圖3 多邊形的單調(diào)鏈[11]Fig.3 The monotone chains of polygons

3 算法的數(shù)據(jù)結(jié)構(gòu)

多邊形相交算法需要適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)多邊形及交點(diǎn),并能夠在其上進(jìn)行正確的操作?，F(xiàn)介紹本算法中用到的數(shù)據(jù)結(jié)構(gòu)。本算法采用基于點(diǎn)坐標(biāo)存儲(chǔ)的方法來(lái)存儲(chǔ)區(qū)、線的坐標(biāo)序列,多邊形的邊界用點(diǎn)坐標(biāo)串表示,如圖4表示的是兩個(gè)多邊形及其交點(diǎn)的存儲(chǔ)結(jié)構(gòu)。polygon1由坐標(biāo)串v1,v2,…,v8組成,且該多邊形根據(jù)多邊形單調(diào)鏈分割算法把多邊形邊界分割為 mc1,mc2,…,mc4,其中單調(diào)鏈只是記錄了坐標(biāo)序列的指針以節(jié)省存儲(chǔ)空間。

圖4 多邊形及其交點(diǎn)數(shù)據(jù)鏈圖Fig.4 The data structure of intersection point and polygons

值得一提的是,該算法的交點(diǎn)數(shù)據(jù)結(jié)構(gòu)中并沒(méi)有記錄經(jīng)典算法中的出點(diǎn)和入點(diǎn)等數(shù)據(jù)結(jié)構(gòu),只是記錄了該交點(diǎn)在兩個(gè)多邊形邊界坐標(biāo)串的插入位置,以便生成結(jié)果多邊形的候選邊集合。

與經(jīng)典的雙向鏈表結(jié)構(gòu) (如 Greiner-Hormann算法)相比,該存儲(chǔ)結(jié)構(gòu)不僅由于少用了一個(gè)指針域而節(jié)省了存儲(chǔ)空間,而且還進(jìn)一步降低了數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性。該算法中交點(diǎn)存儲(chǔ)結(jié)構(gòu)無(wú)需修改雙向鏈表或者單鏈表的指針,因此對(duì)該結(jié)構(gòu)的操作變得簡(jiǎn)單并且更加節(jié)省計(jì)算時(shí)間。

4 算法的設(shè)計(jì)與實(shí)現(xiàn)

該算法主要分為以下四個(gè)階段:第一個(gè)階段計(jì)算兩個(gè)多邊形的交點(diǎn),并根據(jù)交點(diǎn)計(jì)算相交結(jié)果多邊形的候選邊(edges)集;第二階段計(jì)算候選邊集中各個(gè)邊相對(duì)于兩個(gè)多邊形的拓?fù)湮恢藐P(guān)系;第三階段根據(jù)第二階段計(jì)算的兩個(gè)多邊形的拓?fù)湮恢藐P(guān)系來(lái)從候選邊集中挑選組成結(jié)果多邊形的邊,最終生成結(jié)果多邊形;第四階段結(jié)合簡(jiǎn)單要素類(lèi)區(qū)多邊形疊加分析的特點(diǎn),利用STR樹(shù)索引進(jìn)行大規(guī)模計(jì)算,用來(lái)提高大數(shù)據(jù)量多邊形疊加分析運(yùn)算的效率。

4.1 候選邊集的計(jì)算

在候選邊集的計(jì)算過(guò)程中,首先將參與疊加運(yùn)算的多邊形A和多邊形B的邊界分割成各個(gè)單調(diào)鏈。如圖5,多邊形 A由坐標(biāo)串{v1,v2,…, v21}和{v22,v2,…,v31}組成,其中 Edge1{v1,v2,…,v21}為多邊形 A的外圈,Edge2{v22,v2,…, v31}為多邊形 A的內(nèi)圈。單調(diào)鏈的計(jì)算過(guò)程如下:以多邊形A的外圈為例,首先計(jì)算 v1v2所在的象限,象限的計(jì)算是根據(jù)向量v1v2與 x軸的角度確定;然后計(jì)算v2v3的象限,如果相同則繼續(xù)比較,如果不相同則要進(jìn)行處理,如v3v4開(kāi)始與計(jì)算的象限不同,則{v1,v2,v3}組成一個(gè)單調(diào)鏈 mc1,然后從 v3開(kāi)始計(jì)算,可以得到{v3,v2,…,v8}組成一個(gè)單調(diào)鏈 mc2,在單調(diào)鏈的存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)了起始終止頂點(diǎn)號(hào),并沒(méi)有存儲(chǔ)實(shí)際的坐標(biāo)值以節(jié)省存儲(chǔ)空間。在求交點(diǎn)的過(guò)程中,參考文獻(xiàn)[12],利用上述方法求得的各個(gè)單調(diào)鏈,根據(jù)單調(diào)鏈的兩點(diǎn)基本特性,在掃描線算法中,僅將單調(diào)鏈的左端點(diǎn)定義為事件點(diǎn),參與排序的單元的數(shù)目就是實(shí)際單調(diào)鏈的條數(shù)。這里使用堆排序方法對(duì)單調(diào)鏈時(shí)間進(jìn)行排序。連接線段集分解為單調(diào)鏈后,幾何中元的數(shù)目會(huì)極大地減少,提高了線段求交點(diǎn)是速度。利用上述求交點(diǎn)的算法可以求得多邊形 A和多邊形B的交點(diǎn){I1,I2,I3,I4,I5,I6},如圖5所示,計(jì)算出的交點(diǎn)則將多邊形A和多邊形B的邊界分割成各個(gè)離散的邊。如表1所示。

圖5 多邊形A與B相交示意圖Fig.5 The figure of intersection of polygonAand polygonB

表1 離散子邊表Tab.1 The table of sub edges

在子邊(subEdgei)中的數(shù)據(jù)結(jié)構(gòu)中,只存儲(chǔ)了其父親邊的指針和組成該邊的起始頂點(diǎn)號(hào)和交點(diǎn)號(hào)以節(jié)省存儲(chǔ)空間,這些邊組成了結(jié)果多邊形邊的候選集。

4.2 候選邊拓?fù)湮恢玫挠?jì)算

由平面圖及拓?fù)湮恢玫亩x,以圖5為例介紹上一節(jié)計(jì)算出的各個(gè)子邊(S ubEdgei)的拓?fù)湮恢玫挠?jì)算過(guò)程。該過(guò)程主要分為兩步。

第一步:計(jì)算組成多邊形的各個(gè)邊相對(duì)于自己的拓?fù)湮恢?。例?計(jì)算組成多邊形 A的邊(Edge1和 Edge2)相對(duì)于多邊形A的拓?fù)湮恢玫倪^(guò)程為:假設(shè)多邊形A的外圈Edge1以順時(shí)針?lè)较虼鎯?chǔ)坐標(biāo)點(diǎn)序列,多邊形A的內(nèi)圈Edge2以逆時(shí)針?lè)较虼鎯?chǔ)坐標(biāo)點(diǎn)序列,則可以判斷多邊形A的邊(Edge1和 Edge2)的拓?fù)湮恢脼?/p>

同理可以計(jì)算多邊形B的兩個(gè)圈邊界的拓?fù)湮恢脼?/p>

第二步:計(jì)算各個(gè)子邊的拓?fù)湮恢?。子?subEdgei)的拓?fù)湮恢檬紫壤^承了其父類(lèi)邊的拓?fù)湮恢?然后計(jì)算該子邊相對(duì)于另外一個(gè)多邊形O(Other)的拓?fù)湮恢?。其?jì)算過(guò)程如下:因該子邊沒(méi)有組成多邊形O,所以其拓?fù)湮恢玫娜≈挡豢赡苁莃oundary,所以只需取子邊中的一頂點(diǎn)v,判斷該頂點(diǎn)v是在多邊形O的內(nèi)部和外部即可。以子邊(subEdge2)為例,因其父親邊為 Edge1,所以其繼承了 Edge1相對(duì)于 A的拓?fù)湮恢?即: subEdge2(A,on)=boundary,subEdge2(A,left) =exterior,subEdge2(A,right)=interior,只需計(jì)算子邊(subEdge2)相對(duì)于 B的拓?fù)湮恢眉纯?。取子?subEdge2)的頂點(diǎn)v12,根據(jù)點(diǎn)與多邊形的位置關(guān)系的經(jīng)典算法可以判斷,v12在多邊形B的內(nèi)部(interior)。因此可以判斷子邊(subEdge2)的對(duì)于B的拓?fù)湮恢脼?subEdge2(B,on)=interior,subEdge2(B,left)=interior,subEdge2(B, right)=interior。同理計(jì)算其他子邊的拓?fù)湮恢萌绫?所示。

表2 各子邊的topology表Tab.2 The topology of sub edges

表2中,i代表interior;e代表exterior;b代表boundary;“/”符號(hào)前面是相對(duì)于多邊形 A的拓?fù)湮恢藐P(guān)系,“/”符號(hào)后面是相對(duì)于多邊形 B的拓?fù)湮恢藐P(guān)系,例如subEdge1(on)=b/e表示subEdge1對(duì)于多邊形A是在A的邊界(b)上,對(duì)于多邊形B是在多邊形B的外部(e)。

4.3 結(jié)果多邊形的計(jì)算

在完成以上的計(jì)算后,計(jì)算結(jié)果多邊形就比較容易了。根據(jù)疊加操作的類(lèi)型從表3的候選集中挑出子邊組成結(jié)果集。挑選的規(guī)則如表3所示。

由以上定義的規(guī)則,以多邊形交操作為例,參考表3中計(jì)算出的拓?fù)湮恢藐P(guān)系,可以得出組成結(jié)果多邊形子邊集合為{subEdge2,subEdge4, subEdge7,subEdge11,S ubEdge15,S ubEdge17},如圖5陰影部分所示。

表3 疊置操作規(guī)則表Tab.3 The operation rule table of overlay

4.4 利用STR樹(shù)索引進(jìn)行計(jì)算

如果考慮利用STR樹(shù)對(duì)整個(gè)圖層的圖元?jiǎng)?chuàng)建索引,即將圖層中的所有圖元的MBR按STR樹(shù)的層次形式來(lái)組織[13]。這樣,就可以通過(guò)STR樹(shù)本身的高效訪問(wèn)機(jī)制,在疊加操作之前,對(duì)空間數(shù)據(jù)進(jìn)行快速查詢和篩選,減少參與疊加處理的圖元數(shù)目,從而提高空間操作的效率。

具體操作步驟如下:

1.比較疊加分析操作兩個(gè)圖層的圖元數(shù)目,對(duì)圖元較多的那個(gè)圖層創(chuàng)建STR樹(shù)索引。

2.遍歷圖元較少的圖層中的每個(gè)圖元,并用該圖元的MBR作為查詢窗口矩形,對(duì)索引圖層進(jìn)行STR樹(shù)窗口區(qū)域查詢,這樣,利用STR樹(shù)索引快速地查找出僅與查詢窗口相關(guān)(相交或包含)的索引圖層中的圖元。

3.將作為查詢窗口的圖元(疊加圖元)與查找出來(lái)的這些相對(duì)較少的圖元(被疊加圖元)進(jìn)行遍歷疊加操作(調(diào)用前面介紹的兩個(gè)多邊形疊加算法)。

5 算法分析及試驗(yàn)結(jié)果

與經(jīng)典的算法相比,本算法無(wú)需對(duì)生成的出點(diǎn)、入點(diǎn)作判斷,無(wú)需對(duì)多邊形的各個(gè)邊界點(diǎn)都實(shí)施計(jì)算操作以形成結(jié)果多邊形,只需要從生成的邊中根據(jù)疊置操作的規(guī)則找到形成結(jié)果多邊形的邊。這使得在實(shí)際處理異常交點(diǎn)時(shí)變得非常簡(jiǎn)單。

對(duì)基于單調(diào)鏈的求交點(diǎn)算法性能分析如下:設(shè)平面線段集的線段條數(shù)為 n,分解后的單調(diào)鏈條數(shù)為m。初次過(guò)濾只涉及簡(jiǎn)單的點(diǎn)在矩形內(nèi)的判斷,只需對(duì)每條線段遍歷一次即可完成,這一步處理的時(shí)間復(fù)雜度為O(n)。對(duì)單調(diào)鏈分解可以在O(n)時(shí)間內(nèi)完成,然后對(duì)單調(diào)鏈進(jìn)行排序,這一步處理的時(shí)間復(fù)雜度為O(mlgm)。根據(jù)文獻(xiàn)[12]中對(duì)基于單調(diào)鏈的線求交性能分析,每一次單調(diào)鏈的過(guò)濾處理可以在O(milgmi)+O(mi)時(shí)間內(nèi)完成。設(shè)一次粗掃描的單調(diào)鏈過(guò)濾最多處理M條單調(diào)鏈,整個(gè)掃描處理需處理 T條線段,K為整個(gè)平面線段集的交點(diǎn)個(gè)數(shù),則掃描求交的總時(shí)間復(fù)雜度的上限可表示為

所以掃描求交的時(shí)間復(fù)雜度為O(mlgM+m+T+ K),相關(guān)詳細(xì)信息請(qǐng)參看文獻(xiàn)[12]。

簡(jiǎn)單要素模型下的多邊形疊置分析,其規(guī)模是線性增長(zhǎng)的,線段求交操作對(duì)算法效率的影響最大,本算法通過(guò)空間數(shù)據(jù)索引和空間數(shù)據(jù)內(nèi)存管理調(diào)度機(jī)制保障算法的效率。拓?fù)淠Ｐ拖碌寞B置分析除了線段求交外,還要重新構(gòu)建拓?fù)潢P(guān)系,因此當(dāng)線段求交效率接近時(shí),拓?fù)淠Ｐ偷寞B置效率略差于簡(jiǎn)單要素模型。本文以MapGIS 7.0平臺(tái)為基礎(chǔ),按照算法的設(shè)計(jì)思想實(shí)現(xiàn)了簡(jiǎn)單要素模類(lèi)的疊置分析,在對(duì)實(shí)際數(shù)據(jù)的處理中得到了較好的應(yīng)用,并與拓?fù)淠Ｐ拖碌寞B置分析進(jìn)行對(duì)比試驗(yàn)。實(shí)驗(yàn)的結(jié)果分析如表4所示。

表4 各個(gè)數(shù)據(jù)量級(jí)別下該算法與要素模型的執(zhí)行時(shí)間比較T ab.4 The comparison of the simple data model and the topological data mode

6 結(jié)束語(yǔ)

本文的多邊形疊置算法不僅適用于凹多邊形,也適用于帶孔洞的多邊形,不僅可以求多邊形的“交”(多邊形裁剪),還能夠求多邊形的“并”和“差”。該算法無(wú)需對(duì)生成的交點(diǎn)進(jìn)行出點(diǎn)和入點(diǎn)的判斷,無(wú)需把所有的兩個(gè)多邊形的各個(gè)邊界點(diǎn)都讀出來(lái)進(jìn)行計(jì)算來(lái)形成結(jié)果多邊形,只需要從生成的候選邊中找到結(jié)果邊生成結(jié)果多邊形,因此該算法比同類(lèi)算法實(shí)現(xiàn)簡(jiǎn)單。本文還提出一些新的技術(shù)和方法如利用單調(diào)鏈求交點(diǎn)和利用拓?fù)湮恢糜?jì)算結(jié)果多邊形等。最后,以MapGIS 7.0平臺(tái)為基礎(chǔ),將該算法與拓?fù)淠Ｐ偷乃惴ㄟM(jìn)行比較,實(shí)驗(yàn)結(jié)果表明該算法性能優(yōu)于其他同類(lèi)算法。由于簡(jiǎn)單要素類(lèi)模型下的各個(gè)多邊形之間沒(méi)有拓?fù)潢P(guān)系,因此該模型較拓?fù)淠Ｐ透子趯?shí)現(xiàn)疊置分析算子的并行化操作[2]。大規(guī)模數(shù)據(jù)量下的并行化操作的實(shí)現(xiàn)將進(jìn)一步提高簡(jiǎn)單要素模型下疊置運(yùn)算的效率。將該算法進(jìn)行并行化處理將是作者今后研究的方向。

[1] WU Xincai.Geographic Information System Principles,Methods and Applications[M].Beijing:Electronics Industry Press, 2002.(吳信才.地理信息系統(tǒng)原理、方法及應(yīng)用[M].北京:電子工業(yè)出版社,2002.)

[2] XIE Zhong,YE Zi,WU Liang.Polygon Overlay Analysis Algorithm Using the Simple Data Model[J].Geography and Geo-Information Science,2007,23(3):19-23.(謝忠,葉梓,吳亮.簡(jiǎn)單要素模型下的多邊形疊置分析算法[J].地理與地理信息科學(xué),2007,23(3):19-23.)

[3] XUE Sheng,PAN Mao,W ANG Yong.Research of the Algorithms of Polygon’s Overlay[J].Computer Engineering and Applications,2003(2):57-59.(薛勝,潘懋,王勇.多邊形疊置分析算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2003(2):57-59.)

[4] SUTHERLAND I E,HODGEMAN G W.Reentrant Polygon Clipping[J].Communications of the ACM,1974,17(1): 32-42.

[5] LIANG Y,BARSKY B A.An Analysis and Algorithm for Polygon Clipping[J].Communications of the ACM,1983,26 (11):868-877.

[6] FOLEYJ D,DAM A,FEINER S K,et al.Computer Graphics, Principles and Practice[M]. Boston: Addison-Wesley,1990.

[7] MAILLOT P G.A New,Fast Method for 2D Polygon Clipping:Analysis and Software Implementation[J].ACM Transactions on Graphics,1992,11(3):276-290.

[8] LIU Yongkui,GAO Yun,HUANG Youqun.An Efficient Algorithmfor Polygon Clipping[J].Journal of Software,2004,14 (4):845-856.(劉勇奎,高云,黃有群.一個(gè)有效的多邊形裁剪算法[J].軟件學(xué)報(bào),2004,14(4):845-856.)

[9] LEUTENEGGER S,EDGINGTON J M,LOPEZ M A.STR: A Simple and Efficient Algorithm for Rtree Packing[C]∥Proceedings of the 13th IEEE ICDE.Birmingham:IEEE Computer Society,1997:497-506.

[10] ZHOU Peide.Computational Geometry[M].Beijing:Tsinghua University Press,2000.(周培德.計(jì)算幾何[M].北京:清華大學(xué)出版社,2000.)

[11] VIVID.VIVID Solutions:J TS T opology Suite Technical Specifications[EB/OL].[2008-05-12].http:∥www.vividsolutions.com,2003.

[12] YANG Chongjun,REN Yingchao,LI Jinping.Red-Blue Sweep Line Algorithm Based on Monotone Chains for Connected Line Segment Intersection Problems[J].Geomatics and Information Science of Wuhan University,2006,31(9): 835-838.(楊崇俊,任應(yīng)超,李津平.基于單調(diào)鏈的Red_ Blue掃描線求交算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版, 2006,31(9):835-838.)

[13] DONG Peng,YANG Chongjun,LIU Donglin,et al.A Dual Loop Map Overlay Algorithm Based on R+Tree[J].Journal of Image and Graphics,2003,6(8A):703-710.(董鵬,楊崇俊,劉冬林,等.基于R+樹(shù)的地圖疊加分析雙重循環(huán)算法[J].中國(guó)圖象圖形學(xué)報(bào),2003,6(8A):703-710.)

Polygon Overlay Analysis Algorithm Based on Monotone Chain and STR Tree in the Simple Feature Mode

CHEN Zhanlong1,2,WU Xincai1,WU Liang1
1.Faculty of Information Engineering,China University of Geosciences,Wuhan 430075,China;2.China GIS Software Research and Application Engineering Center of the Ministry of Education,Wuhan 430074,China

An improved overlay analysis algorithm based on monotone chain and STR(sort-tile-recursive)tree index is introduced.The algorithm can save the time for vertex listing and intersection point computation,also the memory space.Making full use of the function of overlay analysis for simple features,as many as possible nodes of the polygon can be filled in the STR tree index structure.The algorithm reduces the access times when querying the polygons in the spatial database.The algorithm splits the edges in the polygon by the monotone chain algorithm to compute the intersect point firstly.Secondly,the concept of plane graph is used in this algorithm.The algorithm organizes the result polygons by computing the topology location between the plane graph components of the two polygons.It has been reduced the computing intersect point time and emphasizes on the solution of the problem of the entry point or exit-point successive and the alternative searching of the intersected polygon.

simple feature model;monotone chain;STR tree;plane graph;polygon intersection

CHEN Zhanlong(1980—),male,PhD,majors in theory and method of GIS.

1001-1595(2010)01-0102-07

P208

A

國(guó)家863計(jì)劃(2006AA12Z218);國(guó)家自然科學(xué)基金(40771165);中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金(CUG L090251)

(責(zé)任編輯:叢樹(shù)平)

2008-07-22

2009-07-06

陳占龍(1980—),男,博士,研究方向?yàn)榈乩硇畔⑾到y(tǒng)研究與應(yīng)用。

E-mail:chenzhanlong2005@126.com