盧 浩,鐘耳順,王天寶,王少華
(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所,北京100101;2.中國(guó)科學(xué)院研究生院,北京100039;3.北京超圖軟件股份有限公司,北京100015)
一種基于拓?fù)湫畔⒌亩噙呅螖?shù)據(jù)自動(dòng)生成算法
盧 浩1,2,鐘耳順1,3,王天寶1,2,王少華1,2
(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所,北京100101;2.中國(guó)科學(xué)院研究生院,北京100039;3.北京超圖軟件股份有限公司,北京100015)
在GIS的眾多應(yīng)用中,多邊形數(shù)據(jù)的自動(dòng)生成和多邊形數(shù)據(jù)拓?fù)潢P(guān)系的構(gòu)建與維護(hù)都是一種高頻率的操作。該文在分析和總結(jié)已有多邊形數(shù)據(jù)自動(dòng)生成算法和拓?fù)潢P(guān)系生成算法基礎(chǔ)上,提出了一種基于拓?fù)湫畔⒌亩噙呅螖?shù)據(jù)自動(dòng)生成算法(PG-TI)。介紹了該算法的數(shù)據(jù)結(jié)構(gòu)以及弧段鄰接關(guān)系確定、多邊形搜索和拓?fù)潢P(guān)系確定3個(gè)核心過(guò)程,重點(diǎn)探討了使用多邊形搜索過(guò)程中建立的拓?fù)湫畔?lái)提升拓?fù)潢P(guān)系確定過(guò)程性能,在此基礎(chǔ)上與傳統(tǒng)算法和Arc GIS中對(duì)應(yīng)算法的時(shí)間復(fù)雜度進(jìn)行了對(duì)比分析和驗(yàn)證。
地理信息系統(tǒng);多邊形;拓?fù)湫畔?;包含關(guān)系
在GIS中,多邊形數(shù)據(jù)的自動(dòng)生成是一種常用操作,而算法性能是研究的重點(diǎn)之一。多邊形邊界和區(qū)域內(nèi)是多邊形數(shù)據(jù)的兩個(gè)基本組成部分,GIS軟件中的多邊形數(shù)據(jù)處理功能的完善和性能的提高均直接依賴于對(duì)這兩個(gè)基本要素的處理。例如:左轉(zhuǎn)算法的發(fā)現(xiàn)導(dǎo)致了多邊形拓?fù)湫畔⑸傻淖詣?dòng)化,點(diǎn)與多邊形包含關(guān)系的判定定理使得島區(qū)判定實(shí)現(xiàn)了計(jì)算機(jī)處理[1]。在多邊形數(shù)據(jù)的自動(dòng)生成過(guò)程中,一個(gè)重要的步驟是對(duì)于簡(jiǎn)單多邊形數(shù)據(jù)間包含關(guān)系進(jìn)行判定。齊華[2]給出了一個(gè)根據(jù)多邊形內(nèi)點(diǎn)和面積排序的閉合邊界包含關(guān)系判定算法,該算法依賴于兩個(gè)判定:判定1(閉合邊界包含關(guān)系判定準(zhǔn)則):對(duì)于任意閉合邊界a、b,如果a上有任意一點(diǎn)位于b的內(nèi)部,則a被b所包含;判定2(父邊界判定準(zhǔn)則):父邊界是對(duì)于內(nèi)邊界滿足判定1的外邊界序列中面積最小的外邊界。該算法主要通過(guò)判斷多邊形內(nèi)點(diǎn)與其它多邊形的空間位置關(guān)系得到多邊形包含關(guān)系,而沒(méi)有利用相關(guān)拓?fù)湫畔ⅰ?/p>
多邊形數(shù)據(jù)自動(dòng)生成算法主要步驟總結(jié)為弧段鄰接關(guān)系確定、多邊形搜索、拓?fù)潢P(guān)系確定3個(gè)過(guò)程。相關(guān)研究有:閆浩文等[3]提出了基于方位角計(jì)算的多邊形自動(dòng)生成算法,利用自動(dòng)生成的內(nèi)點(diǎn)進(jìn)行點(diǎn)與多邊形包含關(guān)系的判定;梁曉文等[4]提出了基于夾角變化趨勢(shì)的多邊形自動(dòng)生成算法,根據(jù)相鄰弧段夾角和判斷多邊形搜索方向,避免了無(wú)效多邊形的生成;李大軍等[5]在閆浩文[3]算法基礎(chǔ)上,提出了一種改進(jìn)算法,只進(jìn)行2 N(N為弧段數(shù))次邊的搜索,即可搜索出所有的多邊形。但這些研究較少涉及包含關(guān)系判定過(guò)程的改進(jìn)。本文提出了一種基于拓?fù)湫畔⒌亩噙呅螖?shù)據(jù)自動(dòng)生成算法(PG-TI),通過(guò)使用多邊形搜索過(guò)程中生成的弧段左右多邊形信息,將此拓?fù)湫畔⒔馕龊笥糜诤罄m(xù)的多邊形包含關(guān)系判定中,使得多邊形生成效率有了較大提升。
地理實(shí)體間的空間拓?fù)潢P(guān)系是一種不隨空間旋轉(zhuǎn)、平移、放大/縮小等變換而發(fā)生改變的定性空間信息[6],反映了空間目標(biāo)的邏輯關(guān)系,其對(duì)空間推理、查詢、分析等眾多空間操作具有重要意義。研究較多的確定性空間拓?fù)潢P(guān)系模型包括Egenhofer等在“四交模型”基礎(chǔ)上提出的“九交模型”[7],Randell等運(yùn)用區(qū)域演算理論來(lái)表達(dá)空間區(qū)域拓?fù)涮匦缘目臻g邏輯模型[8],Li等基于空間代數(shù)方法提出的空間代數(shù)模型[9],吳建新等提出的基于Voronoi圖的混合方法(用空間對(duì)象的Voronoi區(qū)域作為其外部,對(duì)原模型進(jìn)行了改進(jìn))[10]。
有學(xué)者將多邊形拓?fù)潢P(guān)系的建立過(guò)程歸結(jié)為:弧段結(jié)點(diǎn)的匹配和弧段連接關(guān)系的建立、同一結(jié)點(diǎn)上?。⊥?fù)潢P(guān)系的建立、閉合邊界弧段相鄰關(guān)系的建立以及閉合邊界包含關(guān)系的確定等步驟[2]。針對(duì)計(jì)算較為耗時(shí)的同一結(jié)點(diǎn)上弧-弧拓?fù)潢P(guān)系的建立,眾多學(xué)者提出了改進(jìn)算法,包括使用泰勒級(jí)數(shù)展開(kāi)近似值替代,使用函數(shù)Qi(x,y)[11]作為參數(shù),基于計(jì)算幾何矢量外積的算法[12]。而對(duì)于較為復(fù)雜的閉合邊界包含關(guān)系確定過(guò)程研究和改進(jìn)較少,本文則著重針對(duì)該過(guò)程進(jìn)行基于拓?fù)湫畔⒌难芯亢透倪M(jìn)。
本文算法在弧段鄰接關(guān)系確定過(guò)程中,通過(guò)使用均勻網(wǎng)格索引來(lái)加速鄰接關(guān)系建立過(guò)程;在多邊形搜索過(guò)程中主要使用左轉(zhuǎn)算法,但會(huì)將弧段的左右多邊形信息同步記錄下來(lái);由于左轉(zhuǎn)算法會(huì)生成一些無(wú)效多邊形,拓?fù)潢P(guān)系確定過(guò)程包括無(wú)效多邊形的剔除和拓?fù)浒P(guān)系的確定。
由于算法輸入為離散的弧段數(shù)據(jù),首先需要建立弧段之間的鄰接關(guān)系,才可以進(jìn)行后續(xù)的多邊形搜索。而鄰接關(guān)系的實(shí)質(zhì)是公共結(jié)點(diǎn)的標(biāo)識(shí),因此該過(guò)程主要生成結(jié)點(diǎn)和弧段的雙向索引。定義如下數(shù)據(jù)結(jié)構(gòu):
(1)邏輯結(jié)點(diǎn)索引數(shù)組:
TNodeInfo[NodeCount]NodeIndex;
數(shù)組類型為邏輯結(jié)點(diǎn)信息結(jié)構(gòu)體:
其中,nPos為構(gòu)成此邏輯結(jié)點(diǎn)的弧段起始索引值,n Num為構(gòu)成此邏輯結(jié)點(diǎn)的弧段數(shù)目,數(shù)組長(zhǎng)度NodeCount為邏輯結(jié)點(diǎn)數(shù)目。
(2)弧段索引數(shù)組:
int[ArcCount*2]ArcIndex;
其中,ArcCount為弧段數(shù)目,因?yàn)槊總€(gè)弧段包括起始和終止兩個(gè)結(jié)點(diǎn),因此數(shù)組長(zhǎng)度為弧段數(shù)目的二倍。
(3)弧段到邏輯結(jié)點(diǎn)索引數(shù)組:
int[ArcCount]ArcFromID;
int[ArcCount]Arc ToID;
NodeIndex和ArcIndex記錄邏輯結(jié)點(diǎn)到弧段的正向索引,其中NodeIndex為邏輯結(jié)點(diǎn)索引,因?yàn)槊總€(gè)邏輯結(jié)點(diǎn)都由一個(gè)或多個(gè)弧段的結(jié)點(diǎn)構(gòu)成,則其需要記錄的是每個(gè)邏輯結(jié)點(diǎn)對(duì)應(yīng)的多個(gè)弧段在弧段數(shù)組ArcIndex中的起始索引(多個(gè)弧段按照方位角排序)nPos以及弧段數(shù)目n Num。ArcIndex中記錄的是每個(gè)邏輯結(jié)點(diǎn)對(duì)應(yīng)的弧段ID,如果為該弧段起始結(jié)點(diǎn),則ID值為正,如果為終止結(jié)點(diǎn),則ID值為負(fù)。ArcFromID和Arc ToID記錄弧段到邏輯結(jié)點(diǎn)的反向索引,即分別記錄每個(gè)弧段起始和終止結(jié)點(diǎn)對(duì)應(yīng)的邏輯結(jié)點(diǎn)ID。索引結(jié)構(gòu)如圖1所示。
圖1 弧段鄰接索引結(jié)構(gòu)Fig.1 Arc adjacency index chart
圖1中,NodeIndex中每個(gè)元素對(duì)應(yīng)一個(gè)邏輯結(jié)點(diǎn),通過(guò)nPos和n Num可以索引到ArcIndex中對(duì)應(yīng)此邏輯結(jié)點(diǎn)的一條或多條弧段ID(即圖1中的ArcID),通過(guò)ArcID可以索引到ArcFromID和Arc ToID數(shù)組中記錄的該弧段的起始和終止邏輯結(jié)點(diǎn)索引,即從ArcFromID和Arc ToID中通過(guò)弧段到邏輯結(jié)點(diǎn)的反向索引可以回到NodeIndex中。
弧段鄰接關(guān)系確定整體過(guò)程如下:1)建立均勻網(wǎng)格索引,并計(jì)算每條弧段起始和終止結(jié)點(diǎn)對(duì)應(yīng)的索引位置;2)計(jì)算索引結(jié)點(diǎn)處對(duì)應(yīng)的方位角(此處約定為從X正半軸起逆時(shí)針旋轉(zhuǎn)角度)和所歸屬的弧段一并存儲(chǔ);3)遍歷均勻格網(wǎng)索引,進(jìn)行結(jié)點(diǎn)匹配,由多個(gè)結(jié)點(diǎn)組成的邏輯結(jié)點(diǎn)按照方位角大小排序后將索引信息存入NodeIndex、ArcIndex、ArcFromID和Arc ToID結(jié)構(gòu)中。
當(dāng)弧段鄰接關(guān)系建立后,算法初始輸入的離散弧段已通過(guò)起始和終止結(jié)點(diǎn)坐標(biāo)匹配為對(duì)應(yīng)的邏輯結(jié)點(diǎn),通過(guò)此邏輯結(jié)點(diǎn)和弧段組成的“邏輯網(wǎng)絡(luò)”即可進(jìn)行多邊形搜索(圖2)。具體搜索過(guò)程為:1)假定起始邏輯結(jié)點(diǎn)為N1,則首先進(jìn)行弧段A1搜索,通過(guò)A1到達(dá)邏輯結(jié)點(diǎn)N2后搜索到弧段A2,類似可以通過(guò)弧段A3后回到起始邏輯結(jié)點(diǎn)N1,此時(shí)構(gòu)成閉合環(huán)路,生成多邊形N1N2N3N1。2)繼續(xù)以N1為起始結(jié)點(diǎn)搜索(逆時(shí)針尋找下一個(gè)弧段),此時(shí)處理弧段A5,到達(dá)結(jié)點(diǎn)N4后根據(jù)弧段順序處理弧段A7,依次搜索到弧段A8和A1后構(gòu)成閉合環(huán)路,生成多邊形N1N4N5N2N1。3)繼續(xù)以N1為起始結(jié)點(diǎn),搜索該邏輯結(jié)點(diǎn)最后一個(gè)弧段A3,類似過(guò)程1,可以得到多邊形N1N3N4N1,此時(shí)N1所有關(guān)聯(lián)弧段的左右多邊形都已生成。4)繼續(xù)處理下一個(gè)邏輯結(jié)點(diǎn)N2,因?yàn)锳1的左右多邊形都已生成,則從A2弧段開(kāi)始搜索,順次進(jìn)行A2A8A63個(gè)弧段的搜索,生成多邊形N2N5N3N2,此時(shí)N2所有關(guān)聯(lián)弧段的左右多邊形都已生成。5)繼續(xù)處理下一個(gè)邏輯結(jié)點(diǎn)N3,生成多邊形N3N5N4N3,此時(shí)所有邏輯結(jié)點(diǎn)關(guān)聯(lián)的弧段左右多邊形都已搜索完畢,共生成5個(gè)簡(jiǎn)單多邊形(面積最大的多邊形N1N4N5N2N1為無(wú)效多邊形)。
圖2 多邊形搜索示意Fig.2 Diagram of polygon search
經(jīng)過(guò)多邊形搜索過(guò)程,所有簡(jiǎn)單多邊形都已生成,此時(shí)需要進(jìn)行無(wú)效多邊形剔除和多邊形包含關(guān)系判定(用以組合為復(fù)雜多邊形)。齊華[2]給出的判定算法主要步驟為:1)將生成的簡(jiǎn)單多邊形按照面積從小到大排序;2)從較小多邊形開(kāi)始處理,計(jì)算出此多邊形內(nèi)點(diǎn),判定內(nèi)點(diǎn)和其它多邊形的包含關(guān)系,從而得到該多邊形的父多邊形。
值得注意的是,在判定內(nèi)點(diǎn)和其它多邊形的包含關(guān)系時(shí),當(dāng)生成多邊形數(shù)目較多時(shí),容易產(chǎn)生大量的無(wú)效判定,導(dǎo)致整體判定效率較低;而通過(guò)解析多邊形搜索過(guò)程中記錄的每個(gè)弧段左右多邊形拓?fù)湫畔ⅲ梢蕴嵘卸ㄐ?。本文的主要思路是將離散的簡(jiǎn)單多邊形根據(jù)其拓?fù)溧徑雨P(guān)系組成若干拓?fù)溧徑訁^(qū)域Tn(圖3),則可以基于這些拓?fù)溧徑訁^(qū)域判定拓?fù)潢P(guān)系,而不再基于多邊形搜索過(guò)程產(chǎn)生的大量簡(jiǎn)單多邊形進(jìn)行判定。
圖3 拓?fù)溧徑訁^(qū)域Fig.3 Topology adjacency area
如圖3所示,多個(gè)離散多邊形被劃分為T1、T2和T33個(gè)拓?fù)溧徑訁^(qū)域,簡(jiǎn)單多邊形P被T3中的某個(gè)多邊形包含,但其本身不屬于任何拓?fù)溧徑訁^(qū)域(因?yàn)槠溥吔缁《螞](méi)有和其它多邊形共用),而拓?fù)溧徑訁^(qū)域具有如下優(yōu)良性質(zhì):1)如果Pn∈Ti、Pm∈Tj且i=j(luò),則Pn和Pm不存在包含關(guān)系,即同屬一個(gè)拓?fù)溧徑訁^(qū)域的多邊形之間不存在包含關(guān)系;2)如果Pn∈Ti且Pn被P包含,則有Pm∈Ti且Pm被P包含,即一個(gè)拓?fù)溧徑訁^(qū)域中的多邊形被另一個(gè)多邊形包含,則此拓?fù)溧徑訁^(qū)域中的其它多邊形也被這個(gè)多邊形包含。換言之,包含關(guān)系判定只需要在不屬于任何拓?fù)溧徑訁^(qū)域的多邊形之間和該類多邊形與拓?fù)溧徑訁^(qū)域多邊形之間進(jìn)行,且同一拓?fù)溧徑訁^(qū)域中的多邊形具有同樣的包含關(guān)系。
定義兩個(gè)數(shù)組int[ArcCount]Arc LeftPolygon和int[ArcCount]Arc RightPolygon,分別存儲(chǔ)每個(gè)弧段的左多邊形ID和右多邊形ID信息,在多邊形搜索過(guò)程中,可以同步生成并存儲(chǔ)每條弧度的左右多邊形信息。定義一個(gè)二維數(shù)組int[RegionCount][Arcs]Region ArcsID,存儲(chǔ)構(gòu)成每個(gè)多邊形的邊界弧段ID,第一維長(zhǎng)度為多邊形數(shù)目。
算法整體流程如下:1)遍歷左右多邊形數(shù)組,將構(gòu)成每個(gè)多邊形的弧段ID記錄到Region ArcsID中,其中從Arc LeftPolygon中讀取的記錄為正ID,從Arc RightPolygon中讀取的記錄為負(fù)ID。2)遍歷所有多邊形對(duì)象,使用一個(gè)棧結(jié)構(gòu)進(jìn)行廣度優(yōu)先搜索,對(duì)共用公共弧段而同屬于某一個(gè)拓?fù)溧徑訁^(qū)域的多邊形進(jìn)行標(biāo)識(shí)。3)將所有多邊形按照面積從小到大排序,從面積較大的多邊形開(kāi)始遍歷,將每一個(gè)拓?fù)溧徑訁^(qū)域中面積最大的多邊形(即外邊界圍成的無(wú)效多邊形N1N4N5N2N1)剔除。4)從面積較小的多邊形開(kāi)始遍歷,根據(jù)每個(gè)多邊形的最小外界矩形范圍建立空間索引。5)依次處理每個(gè)多邊形,通過(guò)內(nèi)點(diǎn)判定的方法尋找其是否被其它某個(gè)多邊形包含,可通過(guò)一些過(guò)濾操作來(lái)提高判定效率:根據(jù)2.3節(jié)的性質(zhì)1可知,同屬于某個(gè)拓?fù)溧徑訁^(qū)域的多邊形之間不存在包含關(guān)系,則無(wú)需對(duì)相同拓?fù)溧徑訁^(qū)域的多邊形進(jìn)行關(guān)系判定;由于在步驟4中使用多邊形最小外接矩形建立空間索引,因此可以根據(jù)多邊形最小外接矩形進(jìn)行過(guò)濾操作,即最小外接矩形不存在包含關(guān)系的多邊形之間一定不存在包含關(guān)系。
假定n為輸入弧段數(shù)目,則弧段結(jié)點(diǎn)格網(wǎng)索引生成和方位角計(jì)算次數(shù)為2n,又因?yàn)樵诟窬W(wǎng)索引基礎(chǔ)上進(jìn)行結(jié)點(diǎn)匹配,則匹配計(jì)算次數(shù)為k×n,即此過(guò)程時(shí)間復(fù)雜度為O(n)。多邊形搜索過(guò)程中因?yàn)槊織l弧段只經(jīng)過(guò)左多邊形和右多邊形兩次搜索,則其時(shí)間復(fù)雜度也為O(n)。在傳統(tǒng)拓?fù)潢P(guān)系確定算法中,需要判定每個(gè)多邊形的內(nèi)點(diǎn)與其它多邊形的包含關(guān)系,其時(shí)間復(fù)雜度為O(m2)(m為生成的簡(jiǎn)單多邊形數(shù)目);而改進(jìn)算法可以將需要判定的簡(jiǎn)單多邊形數(shù)目顯著減少為m0,時(shí)間復(fù)雜度為O(m20),且m0<<m,即算法整體時(shí)間復(fù)雜度為O(n+m20)。
為了驗(yàn)證該算法的有效性,使用C++語(yǔ)言開(kāi)發(fā)了原型系統(tǒng),并使用多組不同規(guī)模的真實(shí)弧段數(shù)據(jù)進(jìn)行對(duì)比測(cè)試,實(shí)驗(yàn)環(huán)境為一臺(tái)主頻2.6 GHz的雙核處理器PC機(jī),內(nèi)存為2 GB。為了驗(yàn)證本文提出的基于拓?fù)湫畔⒌亩噙呅紊伤惴ǎ≒G-TI)的高效性,與傳統(tǒng)算法和ArcGIS中的多邊形自動(dòng)生成功能(Feature To Polygon)進(jìn)行對(duì)比測(cè)試。
首先選取多組數(shù)據(jù)規(guī)模依次增大的弧段數(shù)據(jù)將PG-TI算法和傳統(tǒng)算法進(jìn)行對(duì)比測(cè)試(表1)。由于兩個(gè)算法中多邊形生成數(shù)目均相等(且生成的多邊形形狀一致),即PG-TI算法保證了生成結(jié)果的正確性,因此不再將生成多邊形數(shù)目單獨(dú)列出。從表1可以看出,PG-TI算法在生成效率方面較傳統(tǒng)算法有了較大幅度的提升,且隨著測(cè)試弧段數(shù)目增加,提升效果更加顯著,即PG-TI算法對(duì)于大數(shù)據(jù)量下的多邊形數(shù)據(jù)自動(dòng)生成具有較好的處理性能。
表1 多邊形自動(dòng)生成測(cè)試結(jié)果對(duì)比Table 1 The result of polygon automatic generation comparison
為了進(jìn)一步驗(yàn)證PG-TI算法的有效性,將測(cè)試弧段數(shù)據(jù)轉(zhuǎn)換為Shape文件格式后在ArcGIS的Arc ToolBox模塊中使用Feature To Polygon功能進(jìn)行對(duì)比驗(yàn)證。表1中ArcGIS中的生成時(shí)間使用Arc ToolBox進(jìn)度條中自動(dòng)記錄的處理時(shí)間(精度為秒)。通過(guò)此組對(duì)比實(shí)驗(yàn)可以看出,雖然ArcGIS的生成效率優(yōu)于傳統(tǒng)算法,但PG-TI算法整體性能仍優(yōu)于ArcGIS的多邊形自動(dòng)生成功能,且弧段數(shù)據(jù)量較大時(shí)處理性能表現(xiàn)較好,對(duì)比結(jié)果如圖4所示。
圖4 3種多邊形自動(dòng)生成算法實(shí)驗(yàn)結(jié)果比較Fig.4 Comparison of the experimental results of three methods of polygon automatic generations
多邊形數(shù)據(jù)的自動(dòng)生成是一個(gè)較為基礎(chǔ)與重要的數(shù)據(jù)處理操作,核心過(guò)程包括弧段鄰接關(guān)系確定、多邊形搜索、拓?fù)潢P(guān)系確定等步驟。本文在總結(jié)和分析已有算法基礎(chǔ)上,提出了一種基于拓?fù)湫畔⒌亩噙呅螖?shù)據(jù)自動(dòng)生成算法,通過(guò)多邊形搜索過(guò)程中生成的弧段左右多邊形信息生成拓?fù)溧徑訁^(qū)域,利用拓?fù)溧徑訁^(qū)域的優(yōu)良性質(zhì)使得拓?fù)潢P(guān)系確定過(guò)程的效率有了較大提升。對(duì)算法時(shí)間復(fù)雜度進(jìn)行了分析,并使用多組真實(shí)弧段數(shù)據(jù)與傳統(tǒng)算法、ArcGIS的多邊形生成功能進(jìn)行了對(duì)比實(shí)驗(yàn),證明本文算法處理性能優(yōu)于傳統(tǒng)算法和ArcGIS的相應(yīng)功能,且較適宜進(jìn)行大規(guī)?;《螖?shù)據(jù)的多邊形自動(dòng)生成處理。
[1] 陳春,張樹(shù)文,徐桂芬.GIS中多邊形圖拓?fù)湫畔⑸傻臄?shù)學(xué)基礎(chǔ)[J].測(cè)繪學(xué)報(bào),1996,25(4):266-271.
[2] 齊華.自動(dòng)建立多邊形拓?fù)潢P(guān)系算法步驟的優(yōu)化與改進(jìn)[J].測(cè)繪學(xué)報(bào),1997,26(3):255-260.
[3] 閆浩文,楊維芳,陳全功,等.基于方位角計(jì)算的拓?fù)涠噙呅巫詣?dòng)構(gòu)建快速算法[J].中國(guó)圖象圖形學(xué)報(bào),2000,5A(7):563-567.
[4] 梁曉文,劉宗岐,陳宜金.基于夾角變化趨勢(shì)的多邊形自動(dòng)搜索和生成算法[J].中國(guó)圖象圖形學(xué)報(bào),2005,10(6):785-789.
[5] 李大軍,劉波,趙寶貴,等.拓?fù)涠噙呅巫詣?dòng)構(gòu)建的一種改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2005(16):80-82.
[6] 鄧敏,劉文寶,黃杏元,等.空間目標(biāo)的拓?fù)潢P(guān)系及其GIS應(yīng)用分析[J].中國(guó)圖象圖形學(xué)報(bào),2006,11(2):1743-1749.
[7] EGENHOFER M J,HERRING J.Categorizing binary topological relationships between regions,lines and points in geographic databases[R].Oronoi:Technical report,Department of Surveying Engineering,University of Maine,Oronoi,ME,1991.
[8] RANDELL D,CUI Z,COHN A.A spatial logical based on regions and connection[A].Proceedings of 3rd International Conference on Knowledge Representation and Reasoning[C].Morgan-Kaufman Publishers,1992.165-176.
[9] LI Z,ZHAO R,CHEN J.An algebra model for spatial relations[A].Proceedings of the 3rd ISPRS Workshop on Dynamic and Multi-dimensional GIS[C].Bangkok,2001.170-177.
[10] 吳建新,方裕,陳斌.拓?fù)淇臻g關(guān)系描述理論研究現(xiàn)狀與發(fā)展[J].地理與地理信息科學(xué),2005,21(3):1-4.
[11] 齊華,劉文熙.建立結(jié)點(diǎn)上?。⊥?fù)潢P(guān)系的Qi算法[J].測(cè)繪學(xué)報(bào),1996,25(3):233-235.
[12] 高云瓊,徐建剛,唐文武.同一結(jié)點(diǎn)上?。⊥?fù)潢P(guān)系生成的新算法[J].計(jì)算機(jī)應(yīng)用研究,2002(4):58-59.
Abstract:It is essential to GIS for automatic generation of polygon data,creation and maintenance of polygon topology information as many GIS operations are based on them.In this paper,the current polygon data automatic generation algorithms are summarized and analyzed,as well as polygon topology information generation algorithms with other scholars,a more efficient polygon data automatic generation algorithm based on topology information is proposed.Firstly,the core contents of the algorithm data structure are presented,describing the three core process including arc adjacency,polygon search and topology relationship determination.Secondly,the topology information creation by the polygon search process is described,which can accelerate the process of topology relationship determine.Finally,the algorithm time complexity analysis is presented,as well as the experimental verification.
Key words:GIS;polygon;topology information;contain relationship
A Polygon Data Automatic Generation Algorithm Based on Topology Information
LU Hao1,2,ZHONG Er-shun1,3,WANG Tian-bao1,2,WANG Shao-h(huán)ua1,2
(1.Institute of Geographic Sciences and Natural Resources Research,CAS,Beijing 100101;2.Graduate University of the Chinese Academy of Sciences,Beijing 100039;3.Super Map Software Co.Ltd.,Beijing 100015,China)
P208
A
1672-0504(2012)04-0038-04
2012-01-09;
2012-03-06
盧浩(1984-),男,博士研究生,主要研究方向?yàn)镚IS矢量核心算法。E-mail:luhaonihao2008@163.com