一種基于拓?fù)湫畔⒌亩噙呅螖?shù)據(jù)自動生成算法

0　引言

在 GIS中，多邊形數(shù)據(jù)的自動生成是一種常用操作，而算法性能是研究的重點(diǎn)之一。多邊形邊界和區(qū)域內(nèi)是多邊形數(shù)據(jù)的兩個(gè)基本組成部分，GIS軟件中的多邊形數(shù)據(jù)處理功能的完善和性能的提高均直接依賴于對這兩個(gè)基本要素的處理。例如：左轉(zhuǎn)算法的發(fā)現(xiàn)導(dǎo)致了多邊形拓?fù)湫畔⑸傻淖詣踊?，點(diǎn)與多邊形包含關(guān)系的判定定理使得島區(qū)判定實(shí)現(xiàn)了計(jì)算機(jī)處理[1]。在多邊形數(shù)據(jù)的自動生成過程中，一個(gè)重要的步驟是對于簡單多邊形數(shù)據(jù)間包含關(guān)系進(jìn)行判定。齊華[2]給出了一個(gè)根據(jù)多邊形內(nèi)點(diǎn)和面積排序的閉合邊界包含關(guān)系判定算法，該算法依賴于兩個(gè)判定：判定1(閉合邊界包含關(guān)系判定準(zhǔn)則)：對于任意閉合邊界a、b，如果a上有任意一點(diǎn)位于b的內(nèi)部，則a被b所包含;判定2(父邊界判定準(zhǔn)則)：父邊界是對于內(nèi)邊界滿足判定1的外邊界序列中面積最小的外邊界。該算法主要通過判斷多邊形內(nèi)點(diǎn)與其它多邊形的空間位置關(guān)系得到多邊形包含關(guān)系，而沒有利用相關(guān)拓?fù)湫畔ⅰ?/p>

多邊形數(shù)據(jù)自動生成算法主要步驟總結(jié)為弧段鄰接關(guān)系確定、多邊形搜索、拓?fù)潢P(guān)系確定3個(gè)過程。相關(guān)研究有：閆浩文等[3]提出了基于方位角計(jì)算的多邊形自動生成算法，利用自動生成的內(nèi)點(diǎn)進(jìn)行點(diǎn)與多邊形包含關(guān)系的判定;梁曉文等[4]提出了基于夾角變化趨勢的多邊形自動生成算法，根據(jù)相鄰弧段夾角和判斷多邊形搜索方向，避免了無效多邊形的生成;李大軍等[5]在閆浩文[3]算法基礎(chǔ)上，提出了一種改進(jìn)算法，只進(jìn)行2　N(N 為弧段數(shù))次邊的搜索，即可搜索出所有的多邊形。但這些研究較少

涉及包含關(guān)系判定過程的改進(jìn)。本文提出了一種基

于拓?fù)湫畔⒌亩噙呅螖?shù)據(jù)自動生成算法(PG-TI)，通過使用多邊形搜索過程中生成的弧段左右多邊形信

息，將此拓?fù)湫畔⒔馕龊笥糜诤罄m(xù)的多邊形包含關(guān)系判定中，使得多邊形生成效率有了較大提升。

1　空間拓?fù)潢P(guān)系

地理實(shí)體間的空間拓?fù)潢P(guān)系是一種不隨空間旋轉(zhuǎn)、平移、放大/縮小等變換而發(fā)生改變的定性空間信息[6]，反映了空間目標(biāo)的邏輯關(guān)系，其對空間推理、查詢、分析等眾多空間操作具有重要意義。研究較多的確定性空間拓?fù)潢P(guān)系模型包括 Egenhofer等在“四交模型”基礎(chǔ)上提出的“九交模型”[7]，Randell等運(yùn)用區(qū)域演算理論來表達(dá)空間區(qū)域拓?fù)涮匦缘目臻g邏輯模型[8]，Li等基于空間代數(shù)方法提出的空間代數(shù)模型[9]，吳建新等提出的基于 Voronoi圖的混合方法(用空間對象的 Voronoi區(qū)域作為其外部，對原模型進(jìn)行了改進(jìn))[10]。

有學(xué)者將多邊形拓?fù)潢P(guān)系的建立過程歸結(jié)為：弧段結(jié)點(diǎn)的匹配和弧段連接關(guān)系的建立、同一結(jié)點(diǎn)上弧-弧拓?fù)潢P(guān)系的建立、閉合邊界弧段相鄰關(guān)系的建立以及閉合邊界包含關(guān)系的確定等步驟[2]。針對計(jì)算較為耗時(shí)的同一結(jié)點(diǎn)上弧-弧拓?fù)潢P(guān)系的建立，眾多學(xué)者提出了改進(jìn)算法，包括使用泰勒級數(shù)展開近似值替代，使用函數(shù)Qi(x，y)[11]作為參數(shù)，基于計(jì)算幾何矢量外積的算法[12]。而對于較為復(fù)雜的閉合邊界包含關(guān)系確定過程研究和改進(jìn)較少，本文則著重針對該過程進(jìn)行基于拓?fù)湫畔⒌难芯亢透倪M(jìn)。

2　改進(jìn)算法描述

本文算法在弧段鄰接關(guān)系確定過程中，通過使用均勻網(wǎng)格索引來加速鄰接關(guān)系建立過程;在多邊形搜索過程中主要使用左轉(zhuǎn)算法，但會將弧段的左右多邊形信息同步記錄下來;由于左轉(zhuǎn)算法會生成一些無效多邊形，拓?fù)潢P(guān)系確定過程包括無效多邊形的剔除和拓?fù)浒P(guān)系的確定。

2.1　弧段鄰接關(guān)系確定

由于算法輸入為離散的弧段數(shù)據(jù)，首先需要建立弧段之間的鄰接關(guān)系，才可以進(jìn)行后續(xù)的多邊形搜索。而鄰接關(guān)系的實(shí)質(zhì)是公共結(jié)點(diǎn)的標(biāo)識，因此該過程主要生成結(jié)點(diǎn)和弧段的雙向索引。

更多內(nèi)容請查看pdf