面向矢量數(shù)據(jù)疊加分析的拓?fù)湟恢滦蕴幚硌芯?/h1>
2015-06-07 11:31:42王少華,鐘耳順,李紹俊,3,盧浩
地理與地理信息科學(xué) 2015年1期
王 少 華,鐘 耳 順,李 紹 俊,3,盧 浩
(1.中國科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國科學(xué)院大學(xué)，北京 100039)
?
面向矢量數(shù)據(jù)疊加分析的拓?fù)湟恢滦蕴幚硌芯?/p>
王 少 華1,2,鐘 耳 順1,李 紹 俊1,2,3,盧 浩2*
(1.中國科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國科學(xué)院大學(xué)，北京 100039)
在疊加分析、緩沖區(qū)分析、拓?fù)浞治龅雀鞣N矢量數(shù)據(jù)分析過程中，首要面對的便是矢量數(shù)據(jù)拓?fù)湟恢滦詥栴}。拓?fù)湟恢滦蕴幚硎菍IS矢量數(shù)據(jù)中由于采集、存儲、壓縮、轉(zhuǎn)換導(dǎo)致的空間拓?fù)潢P(guān)系不一致問題進(jìn)行的拓?fù)涮幚?其使得待處理數(shù)據(jù)在容限范圍內(nèi)具有拓?fù)湟恢滦?，從而便于后續(xù)相關(guān)分析功能的進(jìn)行。該文在分析和總結(jié)已有拓?fù)湟恢滦蕴幚硭惴ǖ幕A(chǔ)上，提出了一種更為高效的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，包括弧段間拓?fù)涮幚?、?jié)點與弧段間拓?fù)涮幚?、?jié)點間鄰近搜索等核心過程。對比實驗表明，該算法在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上具有較高的處理性能，是一種實用性較強的拓?fù)湟恢滦蕴幚硭惴ā?/p>
矢量數(shù)據(jù)；疊加分析；均勻格網(wǎng)索引；拓?fù)湟恢滦?/p>
0 引言
GIS中的疊加分析實質(zhì)是地理信息圖層間的空間關(guān)系運算。由于受到數(shù)據(jù)精度的限制，在地理信息圖層疊加分析過程中，不同圖層間對象可能出現(xiàn)邊界線段不一致問題，極易造成疊加結(jié)果產(chǎn)生不符合規(guī)范的細(xì)碎多邊形,如不對其進(jìn)行有效處理，將引起后續(xù)分析計算的異常[1]。因此在進(jìn)行疊加分析計算時引入了容限概念，從而在矢量數(shù)據(jù)幾何計算中修正與維護(hù)數(shù)據(jù)的拓?fù)湟恢滦浴５珕渭兺ㄟ^高精度節(jié)點捕捉低精度節(jié)點的處理方式很難從根本上避免和消除所有的拓?fù)洳灰恢虑闆r，因此一種較為系統(tǒng)的解決方案就顯得尤為重要。
在拓?fù)湟恢滦蕴幚砗童B加分析過程中存在著大量的計算幾何運算，而基于計算幾何的算法實現(xiàn)過程主要面臨兩個挑戰(zhàn)：一是計算機在進(jìn)行數(shù)值計算時不可避免的數(shù)值精度誤差[2]。例如計算幾何中經(jīng)常需要判斷點和線段的空間位置關(guān)系，在通過求算線段方程判斷時，對方程結(jié)果是否為零的判斷極易出現(xiàn)求算結(jié)果略大或略小于零的情況，導(dǎo)致判斷失效。程序計算時的精度損失引起的誤差一般通過兩種方法解決，第一種方法是在中間計算過程中提高表達(dá)精度，進(jìn)行盡可能的“精確”計算[3]，第二種方法是設(shè)定對象間的“容限”使得計算結(jié)果都在容限范圍內(nèi)[2]。另一種挑戰(zhàn)稱之為表達(dá)誤差，由于矢量數(shù)據(jù)的本質(zhì)是真實地物對象的映射和模擬，因此在生產(chǎn)矢量數(shù)據(jù)的過程中不可避免地會引入表達(dá)誤差，即矢量數(shù)據(jù)和真實情況的偏移，或稱之為矢量數(shù)據(jù)的不確定性，這種誤差同樣會導(dǎo)致疊加計算過程出現(xiàn)細(xì)碎多邊形等異常情況?，F(xiàn)有算法中主要通過一種稱為“epsilon geometry/tolerance”[4,5]的方法來處理表達(dá)誤差，即主要通過對待處理數(shù)據(jù)的規(guī)范化來避免誤差，且通過“epsilon geometry/tolerance”這一框架，可同時處理數(shù)值精度誤差和表達(dá)誤差問題[6,7]。
Milenkovic針對以上問題提出了數(shù)據(jù)規(guī)范化(data normalization)[8]，其解決思路是在計算分析之前對數(shù)據(jù)進(jìn)行預(yù)處理，用以糾正所存在的拓?fù)洳灰恢聠栴}。Pullar提出了一種效果較好的解決方案[9]，稱之為地圖調(diào)整(map accommodation)過程,該方法基于Milenkovic算法的思路進(jìn)行數(shù)據(jù)調(diào)整，但為了避免Milenkovic算法存在的問題，在節(jié)點捕捉過程中引入聚類分析的概念。通過對待捕捉的節(jié)點進(jìn)行整體的聚類分析達(dá)到改進(jìn)拓?fù)湟恢滦圆蹲叫Ч哪康模瑫r也可以通過在聚類分析中增加限制條件，解決多次移動導(dǎo)致的節(jié)點偏移過大問題。Harvey等提出了一種控制更加嚴(yán)格的以節(jié)點移動為主要方法的拓?fù)湟恢滦蕴幚硭惴╗10]，該算法主要基于聚類分析實現(xiàn)，通過近似的啟發(fā)式算法選擇節(jié)點，要求用戶先選擇一個數(shù)據(jù)集中的節(jié)點，而后自動調(diào)整另一個數(shù)據(jù)集中的節(jié)點與之匹配。ArcGIS的處理模式[11]整體上和Pullar算法接近，且Pullar算法中提及的需要迭代多次操作的情況在ArcGIS中也有體現(xiàn)。
1 拓?fù)湟恢滦蕴幚砀倪M(jìn)算法
針對已有的拓?fù)湟恢滦蕴幚硭惴ù嬖诘牟蛔?，本文提出一種性能較優(yōu)的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并對算法核心數(shù)據(jù)結(jié)構(gòu)以及弧段間拓?fù)涮幚?、?jié)點與弧段間拓?fù)涮幚?、?jié)點間鄰近搜索3個核心處理過程進(jìn)行詳細(xì)闡述。
1.1 核心數(shù)據(jù)結(jié)構(gòu)
(1)均勻格網(wǎng)索引信息結(jié)構(gòu)。在對待處理數(shù)據(jù)中需進(jìn)行拓?fù)湟恢滦蕴幚淼母鞣N情況進(jìn)行搜索查詢時，由于均勻格網(wǎng)索引結(jié)構(gòu)實現(xiàn)簡單且能有效提升查詢性能[12]，因此，本文使用均勻格網(wǎng)索引結(jié)構(gòu)建立空間數(shù)據(jù)索引，其核心數(shù)據(jù)結(jié)構(gòu)主要包括以下3個組成部分：
structTopoGridInfo
{
IntnSegmentCount;
TSegmentInfo*pSegmentUnit;
};
structTSegmentInfo
{
IntnDTIndex;
IntnObjIndex;
IntnPntIndex;
IntnPntPos;
};
ArrayPnts
其中：TopoGridInfo為基礎(chǔ)的均勻網(wǎng)格索引結(jié)構(gòu)單元結(jié)構(gòu)體，整數(shù)類型nSegmentCount記錄此網(wǎng)格索引單元中索引的節(jié)點(或弧段)數(shù)目；TSegmentInfo為基本索引信息結(jié)構(gòu)，其由4個Int型整數(shù)構(gòu)成，其中nDTIndex記錄圖層索引值，nObjIndex記錄該圖層中的對象索引值，nPntIndex記錄該對象中的節(jié)點索引值(當(dāng)針對弧段建立索引時，即記錄弧段的起始節(jié)點索引值)，nPntPos記錄該節(jié)點的索引節(jié)點數(shù)組Pnts中的位置，數(shù)組長度為nPntCount；pSegmentUnit是一個TSegmentInfo類型的指針數(shù)組，該指針指向網(wǎng)格索引單元中具體索引的空間數(shù)據(jù)信息。經(jīng)過均勻格網(wǎng)索引建立過程后，空間數(shù)據(jù)中的節(jié)點都存儲在索引節(jié)點數(shù)組Pnts中，同時被均勻格網(wǎng)索引單元結(jié)構(gòu)TopoGridInfo管理；而整體的索引結(jié)構(gòu)為單元結(jié)構(gòu)的數(shù)組，數(shù)組數(shù)目即格網(wǎng)索引行數(shù)和列數(shù)的乘積：
TopoGridInfo*pTopoGridInfo=
newTopoGridInfo[nGridRows*nGridCols]
其中:nGridRows為格網(wǎng)索引行數(shù)目，nGridCols為格網(wǎng)索引列數(shù)目，行列數(shù)目根據(jù)待處理數(shù)據(jù)規(guī)模確定。整體索引結(jié)構(gòu)如圖1所示。
圖1 索引核心結(jié)構(gòu)示意
Fig.1Indexcorestructurediagram
(2)數(shù)據(jù)調(diào)整信息數(shù)據(jù)結(jié)構(gòu)。為支持多圖層間的拓?fù)湟恢滦蕴幚恚疚脑O(shè)計了一種較為簡潔統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來存儲各圖層中數(shù)據(jù)對象需要進(jìn)行調(diào)整的信息，核心數(shù)據(jù)結(jié)構(gòu)為一個結(jié)構(gòu)體和節(jié)點數(shù)組：
struct TopoUnitNodeInfo
{
Array nIntersetPntIndex;
Array nIntersetPntPos;
};
ArrayIntersetPnts
每個結(jié)構(gòu)體TopoUnitNodeInfo對應(yīng)一個待調(diào)整的空間對象，nIntersetPntIndex記錄該對象需要調(diào)整的節(jié)點索引(或需要進(jìn)行節(jié)點插入的弧段起始節(jié)點索引)，nIntersetPntIndex記錄該節(jié)點所需調(diào)整的坐標(biāo)在節(jié)點數(shù)組中的位置，即IntersetPnts中記錄的調(diào)整結(jié)果節(jié)點數(shù)組的索引。由于拓?fù)湟恢滦蕴幚矸椒ㄐ柚С侄鄨D層多對象的處理，因此算法中使用的結(jié)構(gòu)為：
VectorparrTopoUnitNodes
parrTopoUnitNodes長度為所需處理的圖層數(shù)目，每個圖層需要根據(jù)其對象數(shù)目nObjCount申請所需的內(nèi)存。
TopoUnitNodeInfo*pTopoUnitNodeInfo=new TopoUnitNodeInfo[nObjCount]
1.2 弧段間拓?fù)涮幚?/p>
弧段間拓?fù)涮幚磉^程主要是進(jìn)行弧段與弧段拓?fù)潢P(guān)系的判別，以及對不滿足弧段與弧段間拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)。當(dāng)兩弧段位置關(guān)系出現(xiàn)類似“十字”形的相交情況時，需在兩弧段的相交處各插入一個節(jié)點，即弧段間的相交情況只允許出現(xiàn)在弧段的起始或終止端點處。此過程基本對應(yīng)于Pullar算法中的弧段相交情況，但由于Pullar算法中弧段相交過程新增的節(jié)點有可能存在和其它弧段造成的二次修正情況，因此把該過程放在第一個流程進(jìn)行處理，使得新增節(jié)點可能導(dǎo)致的和其它弧段或者節(jié)點距離小于容限的情況在后續(xù)過程中依次進(jìn)行修正，避免了多次迭代修正的問題。
整體處理過程可以劃分為檢測和修復(fù)兩大過程，在檢測過程中則對拓?fù)涮幚淼母鲌D層數(shù)據(jù)進(jìn)行遍歷查詢。通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升弧段間關(guān)系判定效率，在建立索引后，依次遍歷所有格網(wǎng)索引結(jié)構(gòu)，在一個或周邊多個格網(wǎng)范圍內(nèi)進(jìn)行弧段間相交情況的判定。應(yīng)注意：當(dāng)出現(xiàn)兩弧段交點距某一弧段起始或終止節(jié)點距離在容限范圍內(nèi)的情況時，則此節(jié)點不需要插入到兩弧段中，而是在后續(xù)的節(jié)點與弧段拓?fù)涮幚磉^程中進(jìn)行處理。
如圖2所示，弧段L1L2和L3L4相交于點P，但由于點P距離節(jié)點L3小于節(jié)點容限，因此此時點P不被插入到弧段L1L2和L3L4當(dāng)中，而將此情況在后面的節(jié)點與弧段間拓?fù)涮幚磉^程進(jìn)行處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個對象，根據(jù)對象每條弧段位置建立網(wǎng)格索引，索引中記錄弧段所屬的數(shù)據(jù)集ID、對象ID、節(jié)點索引值等信息，并將所有弧段中節(jié)點統(tǒng)一存儲到一個節(jié)點數(shù)組中(相鄰兩弧段共用的起始終止節(jié)點只需存儲一次)。2) 索引建立后，遍歷所有索引格網(wǎng)，依次取出每個單元格內(nèi)的弧段，并將此弧段和格網(wǎng)內(nèi)其它弧段進(jìn)行相交計算。需注意：如果兩弧段交點不在此網(wǎng)格內(nèi)，則不記錄，將此情況交由交點所在網(wǎng)格處理，防止重復(fù)記錄插入交點。3) 相交計算結(jié)束后，按照相交計算記錄的交點信息，進(jìn)行交點插入處理。需注意：當(dāng)對象某一弧段需添加多個節(jié)點時，對新添加的節(jié)點排序，根據(jù)排序后的順序添加交點。
圖2 弧段間拓?fù)涮幚硖厥馇闆r
Fig.2Specialcasesofarcstopologyconsistencyprocess
1.3 節(jié)點與弧段間拓?fù)涮幚?/p>
在節(jié)點與弧段間拓?fù)涮幚磉^程中主要是判別節(jié)點與弧段的拓?fù)潢P(guān)系，以及對于不滿足節(jié)點與弧段拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)，即當(dāng)節(jié)點距某弧段距離小于容限時，需在弧段上添加此節(jié)點的垂足。此過程基本對應(yīng)于Pullar算法中的弧段插點過程，但由于Pullar算法流程中弧段插點過程理論上存在和其它弧段造成的二次修正情況，因此把該過程放在第二流程進(jìn)行處理，修正過程由第三過程完成。
整體處理過程同樣可以劃分為檢測和修復(fù)兩大過程，在檢測過程中遍歷數(shù)據(jù)，通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升后續(xù)判定速度，在索引建立后，則依次遍歷所有格網(wǎng)，在一個或周邊多個格網(wǎng)范圍內(nèi)判定節(jié)點和鄰近弧段的距離。需注意：當(dāng)出現(xiàn)節(jié)點到弧段端點距離小于容限情況時，則無論節(jié)點與弧段的距離為多少都不進(jìn)行插入，而當(dāng)出現(xiàn)節(jié)點到弧段端點距離大于容限，但節(jié)點的垂足到弧段端點距離小于容限的情況時，則此垂足點也需插入到弧段中，此情況會在后續(xù)的節(jié)點間鄰近搜索過程中進(jìn)行處理。
如圖3所示，以弧段v1v2為例進(jìn)行節(jié)點與弧段拓?fù)涮幚淼恼f明，當(dāng)節(jié)點v距弧段左右兩端點v1或v2的距離小于容限，即位于圖3中左右端A區(qū)域時，無需進(jìn)行處理，此情況會在后續(xù)的節(jié)點間鄰近搜索中處理。當(dāng)節(jié)點v距弧段端點距離大于容限，但距弧段距離小于容限，即位于圖3中C區(qū)域時，需要計算節(jié)點v到弧段的垂足點，并將此垂足點插入弧段中。有一種特殊情況需要注意：當(dāng)節(jié)點v距弧段端點距離大于容限，但垂足點到弧段端點距離小于容限時，即圖3中4個B區(qū)域，此時仍需將垂足點插入到弧段中，且后續(xù)節(jié)點間鄰近搜索會處理此特殊情況。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)集圖層，取出每個對象，將其節(jié)點和線段建立網(wǎng)格索引，并將所有節(jié)點存儲到一個節(jié)點數(shù)組中。使用兩個網(wǎng)格索引結(jié)構(gòu)分別存儲所有的節(jié)點信息和所有的弧段信息。需注意：節(jié)點索引中只需記錄節(jié)點的坐標(biāo)信息，無需記錄其所屬的數(shù)據(jù)圖層、對象、點串索引等信息。弧段存入弧段網(wǎng)格索引結(jié)構(gòu)中，索引結(jié)構(gòu)中需要同步記錄該弧段所屬的數(shù)據(jù)圖層、對象、點串索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個索引網(wǎng)格內(nèi)的節(jié)點v，以v為中心點，擴散一個容限的距離，查詢是否符合節(jié)點插入條件。需注意：如果計算出的垂足點不在當(dāng)前處理網(wǎng)格內(nèi)，則不記錄，將此情況交由垂足點所在網(wǎng)格處理，防止重復(fù)記錄所需的插入節(jié)點。3) 節(jié)點與弧段位置計算結(jié)束后，按照記錄的節(jié)點插入信息，進(jìn)行數(shù)據(jù)調(diào)整。
圖3 節(jié)點與弧段間拓?fù)涮幚硖厥馇闆r
Fig.3Specialcasesofvertexandarctopologyconsistencyprocess
1.4 節(jié)點間鄰近搜索
在經(jīng)過弧段間拓?fù)涮幚砗凸?jié)點與弧段間拓?fù)涮幚韮蓚€過程后，已對數(shù)據(jù)中的弧段相交情況進(jìn)行了節(jié)點插入，并將數(shù)據(jù)中存在的節(jié)點與弧段距離小于容限的情況通過插入垂足節(jié)點的方式轉(zhuǎn)化為距離在容限范圍內(nèi)的節(jié)點問題，此時需要通過節(jié)點間鄰近搜索過程對這些距離在容限范圍內(nèi)的節(jié)點情況進(jìn)行搜索和處理。不同于Pullar算法中的聚類過程，本文采用節(jié)點間鄰近搜索的策略將這些通過容限相關(guān)的節(jié)點搜索出來，而后統(tǒng)一調(diào)整為同一坐標(biāo)。
如圖4所示，通過節(jié)點v1進(jìn)行鄰近點搜索時可將距離v1在容限范圍內(nèi)的節(jié)點v2搜索出來，而繼續(xù)通過v2進(jìn)行鄰近點搜索時可將距離v2在容限范圍內(nèi)的節(jié)點v3搜索出來，直到通過v3進(jìn)行鄰近點搜索時不再發(fā)現(xiàn)容限范圍內(nèi)的節(jié)點為止。找到的v1、v2、v33個節(jié)點被稱為鄰近點簇，如果鄰近點簇中節(jié)點數(shù)目小于用戶設(shè)置的閾值則直接將這些點調(diào)整為與v1點坐標(biāo)一致，如數(shù)目大于用戶設(shè)置的閾值則將這些點的坐標(biāo)位置記錄下來并反饋給用戶進(jìn)行手動編輯處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個對象，對其節(jié)點建立網(wǎng)格索引，并將所有節(jié)點存儲到一個節(jié)點數(shù)組中。索引結(jié)構(gòu)中需要同步記錄該節(jié)點所屬的數(shù)據(jù)圖層、對象、點數(shù)組索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個索引網(wǎng)格內(nèi)的節(jié)點v，以v為中心點，擴散一個容限的距
圖4 節(jié)點間鄰近搜索
Fig.4Vertexneighboringsearch
離，如找到距離節(jié)點v在容限范圍內(nèi)的節(jié)點，則以此節(jié)點為當(dāng)前節(jié)點繼續(xù)進(jìn)行鄰近搜索，直到找不到容限范圍內(nèi)的節(jié)點為止，而后計算找到的鄰近點簇需調(diào)整到的節(jié)點v1位置。3) 節(jié)點間鄰近搜索結(jié)束后，按照記錄的節(jié)點調(diào)整信息并調(diào)整數(shù)據(jù)。
2 實驗與分析
為驗證本文算法的有效性，使用C語言實現(xiàn)了上文描述的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并與ArcGIS桌面軟件拓?fù)湟恢滦蕴幚淼南嚓P(guān)功能進(jìn)行測試比較。實驗環(huán)境為一臺主頻2.6GHz的雙核處理器PC機，內(nèi)存為2GB。由于疊加分析操作是對矢量數(shù)據(jù)質(zhì)量要求較高的分析操作，且在疊加分析操作中涉及大量的節(jié)點間匹配計算、弧段間相交計算、多邊形生成計算等復(fù)雜處理，因此選用疊加分析操作作為拓?fù)湟恢滦蕴幚硇Ч尿炞C手段，即在拓?fù)湟恢滦蕴幚砗笫褂茂B加分析操作驗證拓?fù)湟恢滦蕴幚淼挠行浴Ｊ紫冗x取兩個面數(shù)據(jù)，分別在ArcGIS和改進(jìn)算法中進(jìn)行拓?fù)湟恢滦蕴幚砗秃罄m(xù)疊加分析處理，而后對兩種處理結(jié)果進(jìn)行比較分析。為了保證測試驗證的有效性，針對該數(shù)據(jù)分別使用“相交”和“對稱差”兩種疊加模式，且每種模式下都使用大小不等的兩種處理容限進(jìn)行測試。如表1所示，ArcGIS的拓?fù)湟恢滦蕴幚砗童B加分析操作在同樣的疊加模式下對于容限的改變較不敏感，而改進(jìn)算法中結(jié)果對于容限的改變較為敏感。在4組實驗中，結(jié)果數(shù)據(jù)集總面積一項中表現(xiàn)出和ArcGIS較好的一致性，ArcGIS處理結(jié)果和改進(jìn)算法處理結(jié)果總面積偏差都在十萬分之一以下，且有一組測試數(shù)據(jù)的總面積偏差在百萬分之一以下，即經(jīng)過拓?fù)湟恢滦愿倪M(jìn)算法處理后的數(shù)據(jù)在疊加分析操作過程中表現(xiàn)出較好的數(shù)據(jù)質(zhì)量和處理效果。
表1 改進(jìn)算法和ArcGIS對比測試結(jié)果
Table 1 The result comparison of improved algorithm and ArcGIS
序號疊加方式疊加容限ArcGIS總面積(m2)改進(jìn)算法總面積(m2)面積偏差(m2)1相交5．25461348429912294．371348429614234．562．21042E-072相交0．00011348429912294．371348424580959．503．95374E-063對稱差5．25468183976303662．088183956850405．882．37699E-064對稱差0．00018183976303662．088183961789600．571．77347E-06
在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上，針對該改進(jìn)算法的性能與ArcGIS進(jìn)行進(jìn)一步的對比測試，為了保證測試的有效性，分別針對常用的線數(shù)據(jù)類型和面數(shù)據(jù)類型，選用了多組規(guī)模不等的空間數(shù)據(jù)進(jìn)行對比測試(表2)。由表2可知，無論是在線數(shù)據(jù)類型還是在面數(shù)據(jù)類型對比測試中，在多種數(shù)據(jù)規(guī)模下的改進(jìn)算法性能都優(yōu)于ArcGIS中的拓?fù)湟恢滦蕴幚矸椒ǎ渲性诰€數(shù)據(jù)類型中平均性能提升約為41.75%(圖5)，在面數(shù)據(jù)類型中平均性能提升約為36.94%(圖6)。改進(jìn)算法在保證處理結(jié)果有效性的基礎(chǔ)上具有較優(yōu)的處理性能，是一種實用性較強的處理方法。
表2 線和面數(shù)據(jù)類型性能對比測試結(jié)果
Table 2 The comparison of line and polygon dataset performance
序號線數(shù)據(jù)類型面數(shù)據(jù)類型對象數(shù)目ArcGIS(s)改進(jìn)算法(s)性能提升(%)對象數(shù)目ArcGIS(s)改進(jìn)算法(s)性能提升(%)1105903．412．7120．531055327．2115．6142．632209797．273．9445．802037842．9327．1136．8533103110．135．5245．513065175．6743．5542．4544148113．568．2539．1639208110．1463．5642．2955152918．219．8445．9650550147．7365．1455．9166158221．3411．5545．8860549171．12119．7630．0177096425．7113．2548．4670618195．26139．1428．7487861526．3414．6444．4280248234．31166．5528．9298998129．1716．3443．9891674261．41185．2329．141010346733．5620．8637．84105555298．07201．4632．41
圖5 線數(shù)據(jù)集性能對比測試 圖6 面數(shù)據(jù)類型性能對比測試
Fig.5 Comparison of the line dataset performance Fig.6 Comparison of the polygon dataset performance
3 結(jié)語
在GIS矢量數(shù)據(jù)相關(guān)的各種空間分析中，拓?fù)湟恢滦缘奶幚硇Чc處理性能對于后續(xù)包括疊加分析、緩沖區(qū)分析、空間查詢等各種空間分析效果有較大的影響。本文首先針對已有的較為典型的拓?fù)湟恢滦蕴幚硭惴ㄟM(jìn)行了闡述和分析，主要包括Milenkovic算法、Pullar算法、Harvey&Vauglin算法以及ArcGIS的處理方式，重點針對各算法的使用情況以及局限性進(jìn)行了分析。在此基礎(chǔ)上提出了一種性能較優(yōu)的改進(jìn)算法，主要包括弧段間拓?fù)涮幚?、?jié)點與弧段間拓?fù)涮幚怼⒐?jié)點間鄰近搜索3個核心過程，并重點針對處理過程中容限的設(shè)置與處理、算法的核心數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行了詳細(xì)闡述。通過3組實驗對該改進(jìn)算法的處理效果和處理性能進(jìn)行了對比驗證與分析，實驗結(jié)果表明，本文所描述的改進(jìn)算法在保證處理效果有效的前提下具有較高的分析處理性能，是一種實用性較強的拓?fù)湟恢滦蕴幚硭惴ā?/p>
[1] GOODCHILD M F.Statistical aspects of the polygon overlay problem[J].Harvard Papers on Geographic Information Systems,1978,6:1-22.
[2] HOFFMANN C M.Geometric and Solid Modeling[M].New York:Morgan Kaufmann,1989.
[3] OTTMANN T,THEIMT G,ULLRICH C.Numerical stability of geometric algorithms[A].Proceedings of the Third Annual Symposium on Computational Geometry[C].ACM,1987.119-125.
[4] BLAKEMORE M.Generalization and error in spatial databases[J].Cartographica,1984,21:131-139.
[5] SALESIN D,STOLFI J,GUIBAS L.Epsilon geometry:Building robust algorithms from imprecise computations[A].Proceedings of the Fifth Annual Symposium on Computational Geometry[C].ACM,1989.208-217.
[6] DOUGENIK J.WHIRLPOOL:A geometric processor for polygon coverage data[A].Proceedings of Auto-Carto 4[C].1980,2:304-311.
[7] CHRISMAN N R.Epsilon filtering:A technique for automated scale changing[A].Technical Papers of the 43rd Annual Meeting of the American Congress on Surveying and Mapping[C].Washington DC,1983.322-331.
[8] MILENKOVIC V J.Verifiable implementations of geometric algorithms using finite precision arithmetic[J].Artificial Intelligence,1988,37(1):377-401.
[9] PULLAR D V.Spatial overlay with inexact numerical data[A].Proceedings Auto-Carto 10[C].Baltimore,1991.313-329.
[10] HARVEY F,VAUGLIN F.No fuzzy creep! A clustering algorithm for controlling arbitrary node movement[A].Proceedings Auto-Carto 13[C].Seattle,ASPRS/ASCM,1997.
[11] ArcGIS 9.3 Help,2009,URL:http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm?TopicName=welcome.2009-12-30.
[12] 王少華,鐘耳順,盧浩,等.基于非均勻多級網(wǎng)格索引的矢量地圖疊加分析算法[J].地理與地理信息科學(xué),2013,29(3):17-20.
Study on Topology Consistency Processes for Vector Data Overlay Analysis
WANG Shao-hua1,2,ZHONG Er-shun1,LI Shao-jun1,2,3,LU Hao2
(1.InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,Beijing100101;2.SuperMapSoftwareCo.Ltd.,Beijing100015;3.UniversityofChineseAcademyofSciences,Beijing100039,China)
Topology consistency issues of vector data need to be faced with primary,which in various vector data analysis processes including overlay analysis,buffer analysis and topological analysis.The topology consistency process is handling with inconsistencies of spatial data topological relations,which generated by acquisition,storage,compression and conversion of GIS vector data.It allows data to keep topology consistency within the tolerance range,so as to facilitate subsequent analysis functions.In this paper,a more efficient topology consistency processing improved algorithm is proposed,which is based on analyzing and summarizing the existing topology consistency processing algorithms.The algorithm contains three core processes,including arcs topology processing,vertexes and arcs topology processing and vertexes proximity searching.The comparison experiments show that the algorithm processing performance is improved and can ensure the processing results are correct,and it is a practical topology consistency processing algorithm
vector data;overlay analysis;uniform grid index;topology consistency
2014-01-28；
2014-04-17
交通運輸部科技項目(2012-364-X04-102);中國科學(xué)院重點部署項目(KZZD-EW-07-01-001);國家科技支撐計劃項目(2011BAH06B03);資源與環(huán)境信息系統(tǒng)國家重點實驗室自主研究項目(088RAC00YA);中國科學(xué)院國防科技創(chuàng)新基金項目(CXJJ-14-M13);北京市科技專項(Z141101004414011)
王少華(1983-)，男，博士，主要研究方向為GIS軟件技術(shù)。*通訊作者E-mail:luhao@supermap.com
10.3969/j.issn.1672-0504.2015.01.003
P208
A
1672-0504(2015)01-0012-05
猜你喜歡
一種航天測控冗余跟蹤弧段處理方法上海航天(2024年1期)2024-03-08 02:52:28 基于改進(jìn)弧段切點弦的多橢圓檢測電子設(shè)計工程(2022年24期)2022-12-23 12:03:28 面向工業(yè)復(fù)雜場景的合作靶標(biāo)橢圓特征快速魯棒檢測光學(xué)精密工程(2021年8期)2021-10-04 11:46:28 實時電離層格網(wǎng)數(shù)據(jù)精度評估空間科學(xué)學(xué)報(2020年6期)2020-07-21 05:36:46 巧用混合圖層 制作抽象動感森林攝影之友(影像視覺)(2017年8期)2017-11-27 02:08:42 圖層法在地理區(qū)域圖讀圖中的應(yīng)用地理教學(xué)(2015年18期)2016-01-06 12:00:38 基于空間信息格網(wǎng)與BP神經(jīng)網(wǎng)絡(luò)的災(zāi)損快速評估系統(tǒng)江西理工大學(xué)學(xué)報(2015年3期)2015-12-22 05:26:18 淺談如何將多段線中的弧線段折線化四川建筑(2015年4期)2015-06-24 14:08:40 淺析“遞層優(yōu)化法”在礦井制圖中的應(yīng)用河南科技(2014年6期)2014-04-04 08:00:42 平均Helmert空間重力異常格網(wǎng)構(gòu)制方法測繪科學(xué)與工程(2014年4期)2014-02-27 07:06:03
王 少 華,鐘 耳 順,李 紹 俊,3,盧 浩
(1.中國科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國科學(xué)院大學(xué)，北京 100039)
?
面向矢量數(shù)據(jù)疊加分析的拓?fù)湟恢滦蕴幚硌芯?/p>
王 少 華1,2,鐘 耳 順1,李 紹 俊1,2,3,盧 浩2*
(1.中國科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國科學(xué)院大學(xué)，北京 100039)
在疊加分析、緩沖區(qū)分析、拓?fù)浞治龅雀鞣N矢量數(shù)據(jù)分析過程中，首要面對的便是矢量數(shù)據(jù)拓?fù)湟恢滦詥栴}。拓?fù)湟恢滦蕴幚硎菍IS矢量數(shù)據(jù)中由于采集、存儲、壓縮、轉(zhuǎn)換導(dǎo)致的空間拓?fù)潢P(guān)系不一致問題進(jìn)行的拓?fù)涮幚?其使得待處理數(shù)據(jù)在容限范圍內(nèi)具有拓?fù)湟恢滦?，從而便于后續(xù)相關(guān)分析功能的進(jìn)行。該文在分析和總結(jié)已有拓?fù)湟恢滦蕴幚硭惴ǖ幕A(chǔ)上，提出了一種更為高效的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，包括弧段間拓?fù)涮幚?、?jié)點與弧段間拓?fù)涮幚?、?jié)點間鄰近搜索等核心過程。對比實驗表明，該算法在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上具有較高的處理性能，是一種實用性較強的拓?fù)湟恢滦蕴幚硭惴ā?/p>
矢量數(shù)據(jù)；疊加分析；均勻格網(wǎng)索引；拓?fù)湟恢滦?/p>
0 引言
GIS中的疊加分析實質(zhì)是地理信息圖層間的空間關(guān)系運算。由于受到數(shù)據(jù)精度的限制，在地理信息圖層疊加分析過程中，不同圖層間對象可能出現(xiàn)邊界線段不一致問題，極易造成疊加結(jié)果產(chǎn)生不符合規(guī)范的細(xì)碎多邊形,如不對其進(jìn)行有效處理，將引起后續(xù)分析計算的異常[1]。因此在進(jìn)行疊加分析計算時引入了容限概念，從而在矢量數(shù)據(jù)幾何計算中修正與維護(hù)數(shù)據(jù)的拓?fù)湟恢滦浴５珕渭兺ㄟ^高精度節(jié)點捕捉低精度節(jié)點的處理方式很難從根本上避免和消除所有的拓?fù)洳灰恢虑闆r，因此一種較為系統(tǒng)的解決方案就顯得尤為重要。
在拓?fù)湟恢滦蕴幚砗童B加分析過程中存在著大量的計算幾何運算，而基于計算幾何的算法實現(xiàn)過程主要面臨兩個挑戰(zhàn)：一是計算機在進(jìn)行數(shù)值計算時不可避免的數(shù)值精度誤差[2]。例如計算幾何中經(jīng)常需要判斷點和線段的空間位置關(guān)系，在通過求算線段方程判斷時，對方程結(jié)果是否為零的判斷極易出現(xiàn)求算結(jié)果略大或略小于零的情況，導(dǎo)致判斷失效。程序計算時的精度損失引起的誤差一般通過兩種方法解決，第一種方法是在中間計算過程中提高表達(dá)精度，進(jìn)行盡可能的“精確”計算[3]，第二種方法是設(shè)定對象間的“容限”使得計算結(jié)果都在容限范圍內(nèi)[2]。另一種挑戰(zhàn)稱之為表達(dá)誤差，由于矢量數(shù)據(jù)的本質(zhì)是真實地物對象的映射和模擬，因此在生產(chǎn)矢量數(shù)據(jù)的過程中不可避免地會引入表達(dá)誤差，即矢量數(shù)據(jù)和真實情況的偏移，或稱之為矢量數(shù)據(jù)的不確定性，這種誤差同樣會導(dǎo)致疊加計算過程出現(xiàn)細(xì)碎多邊形等異常情況?，F(xiàn)有算法中主要通過一種稱為“epsilon geometry/tolerance”[4,5]的方法來處理表達(dá)誤差，即主要通過對待處理數(shù)據(jù)的規(guī)范化來避免誤差，且通過“epsilon geometry/tolerance”這一框架，可同時處理數(shù)值精度誤差和表達(dá)誤差問題[6,7]。
Milenkovic針對以上問題提出了數(shù)據(jù)規(guī)范化(data normalization)[8]，其解決思路是在計算分析之前對數(shù)據(jù)進(jìn)行預(yù)處理，用以糾正所存在的拓?fù)洳灰恢聠栴}。Pullar提出了一種效果較好的解決方案[9]，稱之為地圖調(diào)整(map accommodation)過程,該方法基于Milenkovic算法的思路進(jìn)行數(shù)據(jù)調(diào)整，但為了避免Milenkovic算法存在的問題，在節(jié)點捕捉過程中引入聚類分析的概念。通過對待捕捉的節(jié)點進(jìn)行整體的聚類分析達(dá)到改進(jìn)拓?fù)湟恢滦圆蹲叫Ч哪康模瑫r也可以通過在聚類分析中增加限制條件，解決多次移動導(dǎo)致的節(jié)點偏移過大問題。Harvey等提出了一種控制更加嚴(yán)格的以節(jié)點移動為主要方法的拓?fù)湟恢滦蕴幚硭惴╗10]，該算法主要基于聚類分析實現(xiàn)，通過近似的啟發(fā)式算法選擇節(jié)點，要求用戶先選擇一個數(shù)據(jù)集中的節(jié)點，而后自動調(diào)整另一個數(shù)據(jù)集中的節(jié)點與之匹配。ArcGIS的處理模式[11]整體上和Pullar算法接近，且Pullar算法中提及的需要迭代多次操作的情況在ArcGIS中也有體現(xiàn)。
1 拓?fù)湟恢滦蕴幚砀倪M(jìn)算法
針對已有的拓?fù)湟恢滦蕴幚硭惴ù嬖诘牟蛔?，本文提出一種性能較優(yōu)的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并對算法核心數(shù)據(jù)結(jié)構(gòu)以及弧段間拓?fù)涮幚?、?jié)點與弧段間拓?fù)涮幚?、?jié)點間鄰近搜索3個核心處理過程進(jìn)行詳細(xì)闡述。
1.1 核心數(shù)據(jù)結(jié)構(gòu)
(1)均勻格網(wǎng)索引信息結(jié)構(gòu)。在對待處理數(shù)據(jù)中需進(jìn)行拓?fù)湟恢滦蕴幚淼母鞣N情況進(jìn)行搜索查詢時，由于均勻格網(wǎng)索引結(jié)構(gòu)實現(xiàn)簡單且能有效提升查詢性能[12]，因此，本文使用均勻格網(wǎng)索引結(jié)構(gòu)建立空間數(shù)據(jù)索引，其核心數(shù)據(jù)結(jié)構(gòu)主要包括以下3個組成部分：
structTopoGridInfo
{
IntnSegmentCount;
TSegmentInfo*pSegmentUnit;
};
structTSegmentInfo
{
IntnDTIndex;
IntnObjIndex;
IntnPntIndex;
IntnPntPos;
};
Array
其中：TopoGridInfo為基礎(chǔ)的均勻網(wǎng)格索引結(jié)構(gòu)單元結(jié)構(gòu)體，整數(shù)類型nSegmentCount記錄此網(wǎng)格索引單元中索引的節(jié)點(或弧段)數(shù)目；TSegmentInfo為基本索引信息結(jié)構(gòu)，其由4個Int型整數(shù)構(gòu)成，其中nDTIndex記錄圖層索引值，nObjIndex記錄該圖層中的對象索引值，nPntIndex記錄該對象中的節(jié)點索引值(當(dāng)針對弧段建立索引時，即記錄弧段的起始節(jié)點索引值)，nPntPos記錄該節(jié)點的索引節(jié)點數(shù)組Pnts中的位置，數(shù)組長度為nPntCount；pSegmentUnit是一個TSegmentInfo類型的指針數(shù)組，該指針指向網(wǎng)格索引單元中具體索引的空間數(shù)據(jù)信息。經(jīng)過均勻格網(wǎng)索引建立過程后，空間數(shù)據(jù)中的節(jié)點都存儲在索引節(jié)點數(shù)組Pnts中，同時被均勻格網(wǎng)索引單元結(jié)構(gòu)TopoGridInfo管理；而整體的索引結(jié)構(gòu)為單元結(jié)構(gòu)的數(shù)組，數(shù)組數(shù)目即格網(wǎng)索引行數(shù)和列數(shù)的乘積：
TopoGridInfo*pTopoGridInfo=
newTopoGridInfo[nGridRows*nGridCols]
其中:nGridRows為格網(wǎng)索引行數(shù)目，nGridCols為格網(wǎng)索引列數(shù)目，行列數(shù)目根據(jù)待處理數(shù)據(jù)規(guī)模確定。整體索引結(jié)構(gòu)如圖1所示。
圖1 索引核心結(jié)構(gòu)示意
Fig.1Indexcorestructurediagram
(2)數(shù)據(jù)調(diào)整信息數(shù)據(jù)結(jié)構(gòu)。為支持多圖層間的拓?fù)湟恢滦蕴幚恚疚脑O(shè)計了一種較為簡潔統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來存儲各圖層中數(shù)據(jù)對象需要進(jìn)行調(diào)整的信息，核心數(shù)據(jù)結(jié)構(gòu)為一個結(jié)構(gòu)體和節(jié)點數(shù)組：
struct TopoUnitNodeInfo
{
Array
Array
};
Array
每個結(jié)構(gòu)體TopoUnitNodeInfo對應(yīng)一個待調(diào)整的空間對象，nIntersetPntIndex記錄該對象需要調(diào)整的節(jié)點索引(或需要進(jìn)行節(jié)點插入的弧段起始節(jié)點索引)，nIntersetPntIndex記錄該節(jié)點所需調(diào)整的坐標(biāo)在節(jié)點數(shù)組中的位置，即IntersetPnts中記錄的調(diào)整結(jié)果節(jié)點數(shù)組的索引。由于拓?fù)湟恢滦蕴幚矸椒ㄐ柚С侄鄨D層多對象的處理，因此算法中使用的結(jié)構(gòu)為：
Vector
parrTopoUnitNodes長度為所需處理的圖層數(shù)目，每個圖層需要根據(jù)其對象數(shù)目nObjCount申請所需的內(nèi)存。
TopoUnitNodeInfo*pTopoUnitNodeInfo=new TopoUnitNodeInfo[nObjCount]
1.2 弧段間拓?fù)涮幚?/p>
弧段間拓?fù)涮幚磉^程主要是進(jìn)行弧段與弧段拓?fù)潢P(guān)系的判別，以及對不滿足弧段與弧段間拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)。當(dāng)兩弧段位置關(guān)系出現(xiàn)類似“十字”形的相交情況時，需在兩弧段的相交處各插入一個節(jié)點，即弧段間的相交情況只允許出現(xiàn)在弧段的起始或終止端點處。此過程基本對應(yīng)于Pullar算法中的弧段相交情況，但由于Pullar算法中弧段相交過程新增的節(jié)點有可能存在和其它弧段造成的二次修正情況，因此把該過程放在第一個流程進(jìn)行處理，使得新增節(jié)點可能導(dǎo)致的和其它弧段或者節(jié)點距離小于容限的情況在后續(xù)過程中依次進(jìn)行修正，避免了多次迭代修正的問題。
整體處理過程可以劃分為檢測和修復(fù)兩大過程，在檢測過程中則對拓?fù)涮幚淼母鲌D層數(shù)據(jù)進(jìn)行遍歷查詢。通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升弧段間關(guān)系判定效率，在建立索引后，依次遍歷所有格網(wǎng)索引結(jié)構(gòu)，在一個或周邊多個格網(wǎng)范圍內(nèi)進(jìn)行弧段間相交情況的判定。應(yīng)注意：當(dāng)出現(xiàn)兩弧段交點距某一弧段起始或終止節(jié)點距離在容限范圍內(nèi)的情況時，則此節(jié)點不需要插入到兩弧段中，而是在后續(xù)的節(jié)點與弧段拓?fù)涮幚磉^程中進(jìn)行處理。
如圖2所示，弧段L1L2和L3L4相交于點P，但由于點P距離節(jié)點L3小于節(jié)點容限，因此此時點P不被插入到弧段L1L2和L3L4當(dāng)中，而將此情況在后面的節(jié)點與弧段間拓?fù)涮幚磉^程進(jìn)行處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個對象，根據(jù)對象每條弧段位置建立網(wǎng)格索引，索引中記錄弧段所屬的數(shù)據(jù)集ID、對象ID、節(jié)點索引值等信息，并將所有弧段中節(jié)點統(tǒng)一存儲到一個節(jié)點數(shù)組中(相鄰兩弧段共用的起始終止節(jié)點只需存儲一次)。2) 索引建立后，遍歷所有索引格網(wǎng)，依次取出每個單元格內(nèi)的弧段，并將此弧段和格網(wǎng)內(nèi)其它弧段進(jìn)行相交計算。需注意：如果兩弧段交點不在此網(wǎng)格內(nèi)，則不記錄，將此情況交由交點所在網(wǎng)格處理，防止重復(fù)記錄插入交點。3) 相交計算結(jié)束后，按照相交計算記錄的交點信息，進(jìn)行交點插入處理。需注意：當(dāng)對象某一弧段需添加多個節(jié)點時，對新添加的節(jié)點排序，根據(jù)排序后的順序添加交點。
圖2 弧段間拓?fù)涮幚硖厥馇闆r
Fig.2Specialcasesofarcstopologyconsistencyprocess
1.3 節(jié)點與弧段間拓?fù)涮幚?/p>
在節(jié)點與弧段間拓?fù)涮幚磉^程中主要是判別節(jié)點與弧段的拓?fù)潢P(guān)系，以及對于不滿足節(jié)點與弧段拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)，即當(dāng)節(jié)點距某弧段距離小于容限時，需在弧段上添加此節(jié)點的垂足。此過程基本對應(yīng)于Pullar算法中的弧段插點過程，但由于Pullar算法流程中弧段插點過程理論上存在和其它弧段造成的二次修正情況，因此把該過程放在第二流程進(jìn)行處理，修正過程由第三過程完成。
整體處理過程同樣可以劃分為檢測和修復(fù)兩大過程，在檢測過程中遍歷數(shù)據(jù)，通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升后續(xù)判定速度，在索引建立后，則依次遍歷所有格網(wǎng)，在一個或周邊多個格網(wǎng)范圍內(nèi)判定節(jié)點和鄰近弧段的距離。需注意：當(dāng)出現(xiàn)節(jié)點到弧段端點距離小于容限情況時，則無論節(jié)點與弧段的距離為多少都不進(jìn)行插入，而當(dāng)出現(xiàn)節(jié)點到弧段端點距離大于容限，但節(jié)點的垂足到弧段端點距離小于容限的情況時，則此垂足點也需插入到弧段中，此情況會在后續(xù)的節(jié)點間鄰近搜索過程中進(jìn)行處理。
如圖3所示，以弧段v1v2為例進(jìn)行節(jié)點與弧段拓?fù)涮幚淼恼f明，當(dāng)節(jié)點v距弧段左右兩端點v1或v2的距離小于容限，即位于圖3中左右端A區(qū)域時，無需進(jìn)行處理，此情況會在后續(xù)的節(jié)點間鄰近搜索中處理。當(dāng)節(jié)點v距弧段端點距離大于容限，但距弧段距離小于容限，即位于圖3中C區(qū)域時，需要計算節(jié)點v到弧段的垂足點，并將此垂足點插入弧段中。有一種特殊情況需要注意：當(dāng)節(jié)點v距弧段端點距離大于容限，但垂足點到弧段端點距離小于容限時，即圖3中4個B區(qū)域，此時仍需將垂足點插入到弧段中，且后續(xù)節(jié)點間鄰近搜索會處理此特殊情況。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)集圖層，取出每個對象，將其節(jié)點和線段建立網(wǎng)格索引，并將所有節(jié)點存儲到一個節(jié)點數(shù)組中。使用兩個網(wǎng)格索引結(jié)構(gòu)分別存儲所有的節(jié)點信息和所有的弧段信息。需注意：節(jié)點索引中只需記錄節(jié)點的坐標(biāo)信息，無需記錄其所屬的數(shù)據(jù)圖層、對象、點串索引等信息。弧段存入弧段網(wǎng)格索引結(jié)構(gòu)中，索引結(jié)構(gòu)中需要同步記錄該弧段所屬的數(shù)據(jù)圖層、對象、點串索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個索引網(wǎng)格內(nèi)的節(jié)點v，以v為中心點，擴散一個容限的距離，查詢是否符合節(jié)點插入條件。需注意：如果計算出的垂足點不在當(dāng)前處理網(wǎng)格內(nèi)，則不記錄，將此情況交由垂足點所在網(wǎng)格處理，防止重復(fù)記錄所需的插入節(jié)點。3) 節(jié)點與弧段位置計算結(jié)束后，按照記錄的節(jié)點插入信息，進(jìn)行數(shù)據(jù)調(diào)整。
圖3 節(jié)點與弧段間拓?fù)涮幚硖厥馇闆r
Fig.3Specialcasesofvertexandarctopologyconsistencyprocess
1.4 節(jié)點間鄰近搜索
在經(jīng)過弧段間拓?fù)涮幚砗凸?jié)點與弧段間拓?fù)涮幚韮蓚€過程后，已對數(shù)據(jù)中的弧段相交情況進(jìn)行了節(jié)點插入，并將數(shù)據(jù)中存在的節(jié)點與弧段距離小于容限的情況通過插入垂足節(jié)點的方式轉(zhuǎn)化為距離在容限范圍內(nèi)的節(jié)點問題，此時需要通過節(jié)點間鄰近搜索過程對這些距離在容限范圍內(nèi)的節(jié)點情況進(jìn)行搜索和處理。不同于Pullar算法中的聚類過程，本文采用節(jié)點間鄰近搜索的策略將這些通過容限相關(guān)的節(jié)點搜索出來，而后統(tǒng)一調(diào)整為同一坐標(biāo)。
如圖4所示，通過節(jié)點v1進(jìn)行鄰近點搜索時可將距離v1在容限范圍內(nèi)的節(jié)點v2搜索出來，而繼續(xù)通過v2進(jìn)行鄰近點搜索時可將距離v2在容限范圍內(nèi)的節(jié)點v3搜索出來，直到通過v3進(jìn)行鄰近點搜索時不再發(fā)現(xiàn)容限范圍內(nèi)的節(jié)點為止。找到的v1、v2、v33個節(jié)點被稱為鄰近點簇，如果鄰近點簇中節(jié)點數(shù)目小于用戶設(shè)置的閾值則直接將這些點調(diào)整為與v1點坐標(biāo)一致，如數(shù)目大于用戶設(shè)置的閾值則將這些點的坐標(biāo)位置記錄下來并反饋給用戶進(jìn)行手動編輯處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個對象，對其節(jié)點建立網(wǎng)格索引，并將所有節(jié)點存儲到一個節(jié)點數(shù)組中。索引結(jié)構(gòu)中需要同步記錄該節(jié)點所屬的數(shù)據(jù)圖層、對象、點數(shù)組索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個索引網(wǎng)格內(nèi)的節(jié)點v，以v為中心點，擴散一個容限的距
圖4 節(jié)點間鄰近搜索
Fig.4Vertexneighboringsearch
離，如找到距離節(jié)點v在容限范圍內(nèi)的節(jié)點，則以此節(jié)點為當(dāng)前節(jié)點繼續(xù)進(jìn)行鄰近搜索，直到找不到容限范圍內(nèi)的節(jié)點為止，而后計算找到的鄰近點簇需調(diào)整到的節(jié)點v1位置。3) 節(jié)點間鄰近搜索結(jié)束后，按照記錄的節(jié)點調(diào)整信息并調(diào)整數(shù)據(jù)。
2 實驗與分析
為驗證本文算法的有效性，使用C語言實現(xiàn)了上文描述的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并與ArcGIS桌面軟件拓?fù)湟恢滦蕴幚淼南嚓P(guān)功能進(jìn)行測試比較。實驗環(huán)境為一臺主頻2.6GHz的雙核處理器PC機，內(nèi)存為2GB。由于疊加分析操作是對矢量數(shù)據(jù)質(zhì)量要求較高的分析操作，且在疊加分析操作中涉及大量的節(jié)點間匹配計算、弧段間相交計算、多邊形生成計算等復(fù)雜處理，因此選用疊加分析操作作為拓?fù)湟恢滦蕴幚硇Ч尿炞C手段，即在拓?fù)湟恢滦蕴幚砗笫褂茂B加分析操作驗證拓?fù)湟恢滦蕴幚淼挠行浴Ｊ紫冗x取兩個面數(shù)據(jù)，分別在ArcGIS和改進(jìn)算法中進(jìn)行拓?fù)湟恢滦蕴幚砗秃罄m(xù)疊加分析處理，而后對兩種處理結(jié)果進(jìn)行比較分析。為了保證測試驗證的有效性，針對該數(shù)據(jù)分別使用“相交”和“對稱差”兩種疊加模式，且每種模式下都使用大小不等的兩種處理容限進(jìn)行測試。如表1所示，ArcGIS的拓?fù)湟恢滦蕴幚砗童B加分析操作在同樣的疊加模式下對于容限的改變較不敏感，而改進(jìn)算法中結(jié)果對于容限的改變較為敏感。在4組實驗中，結(jié)果數(shù)據(jù)集總面積一項中表現(xiàn)出和ArcGIS較好的一致性，ArcGIS處理結(jié)果和改進(jìn)算法處理結(jié)果總面積偏差都在十萬分之一以下，且有一組測試數(shù)據(jù)的總面積偏差在百萬分之一以下，即經(jīng)過拓?fù)湟恢滦愿倪M(jìn)算法處理后的數(shù)據(jù)在疊加分析操作過程中表現(xiàn)出較好的數(shù)據(jù)質(zhì)量和處理效果。
表1 改進(jìn)算法和ArcGIS對比測試結(jié)果
Table 1 The result comparison of improved algorithm and ArcGIS
序號疊加方式疊加容限ArcGIS總面積(m2)改進(jìn)算法總面積(m2)面積偏差(m2)1相交5．25461348429912294．371348429614234．562．21042E-072相交0．00011348429912294．371348424580959．503．95374E-063對稱差5．25468183976303662．088183956850405．882．37699E-064對稱差0．00018183976303662．088183961789600．571．77347E-06
在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上，針對該改進(jìn)算法的性能與ArcGIS進(jìn)行進(jìn)一步的對比測試，為了保證測試的有效性，分別針對常用的線數(shù)據(jù)類型和面數(shù)據(jù)類型，選用了多組規(guī)模不等的空間數(shù)據(jù)進(jìn)行對比測試(表2)。由表2可知，無論是在線數(shù)據(jù)類型還是在面數(shù)據(jù)類型對比測試中，在多種數(shù)據(jù)規(guī)模下的改進(jìn)算法性能都優(yōu)于ArcGIS中的拓?fù)湟恢滦蕴幚矸椒ǎ渲性诰€數(shù)據(jù)類型中平均性能提升約為41.75%(圖5)，在面數(shù)據(jù)類型中平均性能提升約為36.94%(圖6)。改進(jìn)算法在保證處理結(jié)果有效性的基礎(chǔ)上具有較優(yōu)的處理性能，是一種實用性較強的處理方法。
表2 線和面數(shù)據(jù)類型性能對比測試結(jié)果
Table 2 The comparison of line and polygon dataset performance
序號線數(shù)據(jù)類型面數(shù)據(jù)類型對象數(shù)目ArcGIS(s)改進(jìn)算法(s)性能提升(%)對象數(shù)目ArcGIS(s)改進(jìn)算法(s)性能提升(%)1105903．412．7120．531055327．2115．6142．632209797．273．9445．802037842．9327．1136．8533103110．135．5245．513065175．6743．5542．4544148113．568．2539．1639208110．1463．5642．2955152918．219．8445．9650550147．7365．1455．9166158221．3411．5545．8860549171．12119．7630．0177096425．7113．2548．4670618195．26139．1428．7487861526．3414．6444．4280248234．31166．5528．9298998129．1716．3443．9891674261．41185．2329．141010346733．5620．8637．84105555298．07201．4632．41
圖5 線數(shù)據(jù)集性能對比測試 圖6 面數(shù)據(jù)類型性能對比測試
Fig.5 Comparison of the line dataset performance Fig.6 Comparison of the polygon dataset performance
3 結(jié)語
在GIS矢量數(shù)據(jù)相關(guān)的各種空間分析中，拓?fù)湟恢滦缘奶幚硇Чc處理性能對于后續(xù)包括疊加分析、緩沖區(qū)分析、空間查詢等各種空間分析效果有較大的影響。本文首先針對已有的較為典型的拓?fù)湟恢滦蕴幚硭惴ㄟM(jìn)行了闡述和分析，主要包括Milenkovic算法、Pullar算法、Harvey&Vauglin算法以及ArcGIS的處理方式，重點針對各算法的使用情況以及局限性進(jìn)行了分析。在此基礎(chǔ)上提出了一種性能較優(yōu)的改進(jìn)算法，主要包括弧段間拓?fù)涮幚?、?jié)點與弧段間拓?fù)涮幚怼⒐?jié)點間鄰近搜索3個核心過程，并重點針對處理過程中容限的設(shè)置與處理、算法的核心數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行了詳細(xì)闡述。通過3組實驗對該改進(jìn)算法的處理效果和處理性能進(jìn)行了對比驗證與分析，實驗結(jié)果表明，本文所描述的改進(jìn)算法在保證處理效果有效的前提下具有較高的分析處理性能，是一種實用性較強的拓?fù)湟恢滦蕴幚硭惴ā?/p>
[1] GOODCHILD M F.Statistical aspects of the polygon overlay problem[J].Harvard Papers on Geographic Information Systems,1978,6:1-22.
[2] HOFFMANN C M.Geometric and Solid Modeling[M].New York:Morgan Kaufmann,1989.
[3] OTTMANN T,THEIMT G,ULLRICH C.Numerical stability of geometric algorithms[A].Proceedings of the Third Annual Symposium on Computational Geometry[C].ACM,1987.119-125.
[4] BLAKEMORE M.Generalization and error in spatial databases[J].Cartographica,1984,21:131-139.
[5] SALESIN D,STOLFI J,GUIBAS L.Epsilon geometry:Building robust algorithms from imprecise computations[A].Proceedings of the Fifth Annual Symposium on Computational Geometry[C].ACM,1989.208-217.
[6] DOUGENIK J.WHIRLPOOL:A geometric processor for polygon coverage data[A].Proceedings of Auto-Carto 4[C].1980,2:304-311.
[7] CHRISMAN N R.Epsilon filtering:A technique for automated scale changing[A].Technical Papers of the 43rd Annual Meeting of the American Congress on Surveying and Mapping[C].Washington DC,1983.322-331.
[8] MILENKOVIC V J.Verifiable implementations of geometric algorithms using finite precision arithmetic[J].Artificial Intelligence,1988,37(1):377-401.
[9] PULLAR D V.Spatial overlay with inexact numerical data[A].Proceedings Auto-Carto 10[C].Baltimore,1991.313-329.
[10] HARVEY F,VAUGLIN F.No fuzzy creep! A clustering algorithm for controlling arbitrary node movement[A].Proceedings Auto-Carto 13[C].Seattle,ASPRS/ASCM,1997.
[11] ArcGIS 9.3 Help,2009,URL:http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm?TopicName=welcome.2009-12-30.
[12] 王少華,鐘耳順,盧浩,等.基于非均勻多級網(wǎng)格索引的矢量地圖疊加分析算法[J].地理與地理信息科學(xué),2013,29(3):17-20.
Study on Topology Consistency Processes for Vector Data Overlay Analysis
WANG Shao-hua1,2,ZHONG Er-shun1,LI Shao-jun1,2,3,LU Hao2
(1.InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,Beijing100101;2.SuperMapSoftwareCo.Ltd.,Beijing100015;3.UniversityofChineseAcademyofSciences,Beijing100039,China)
Topology consistency issues of vector data need to be faced with primary,which in various vector data analysis processes including overlay analysis,buffer analysis and topological analysis.The topology consistency process is handling with inconsistencies of spatial data topological relations,which generated by acquisition,storage,compression and conversion of GIS vector data.It allows data to keep topology consistency within the tolerance range,so as to facilitate subsequent analysis functions.In this paper,a more efficient topology consistency processing improved algorithm is proposed,which is based on analyzing and summarizing the existing topology consistency processing algorithms.The algorithm contains three core processes,including arcs topology processing,vertexes and arcs topology processing and vertexes proximity searching.The comparison experiments show that the algorithm processing performance is improved and can ensure the processing results are correct,and it is a practical topology consistency processing algorithm
vector data;overlay analysis;uniform grid index;topology consistency
2014-01-28；
2014-04-17
交通運輸部科技項目(2012-364-X04-102);中國科學(xué)院重點部署項目(KZZD-EW-07-01-001);國家科技支撐計劃項目(2011BAH06B03);資源與環(huán)境信息系統(tǒng)國家重點實驗室自主研究項目(088RAC00YA);中國科學(xué)院國防科技創(chuàng)新基金項目(CXJJ-14-M13);北京市科技專項(Z141101004414011)
王少華(1983-)，男，博士，主要研究方向為GIS軟件技術(shù)。*通訊作者E-mail:luhao@supermap.com
10.3969/j.issn.1672-0504.2015.01.003
P208
A
1672-0504(2015)01-0012-05
猜你喜歡
上海航天(2024年1期)2024-03-08 02:52:28
電子設(shè)計工程(2022年24期)2022-12-23 12:03:28
光學(xué)精密工程(2021年8期)2021-10-04 11:46:28
空間科學(xué)學(xué)報(2020年6期)2020-07-21 05:36:46
攝影之友(影像視覺)(2017年8期)2017-11-27 02:08:42
地理教學(xué)(2015年18期)2016-01-06 12:00:38
江西理工大學(xué)學(xué)報(2015年3期)2015-12-22 05:26:18
四川建筑(2015年4期)2015-06-24 14:08:40
河南科技(2014年6期)2014-04-04 08:00:42
測繪科學(xué)與工程(2014年4期)2014-02-27 07:06:03
