面向矢量數(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é)點(diǎn)與弧段間拓?fù)涮幚?、?jié)點(diǎn)間鄰近搜索等核心過程。對比實(shí)驗(yàn)表明，該算法在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上具有較高的處理性能，是一種實(shí)用性較強(qiáng)的拓?fù)湟恢滦蕴幚硭惴ā?/p>
矢量數(shù)據(jù)；疊加分析；均勻格網(wǎng)索引；拓?fù)湟恢滦?/p>
0 引言
GIS中的疊加分析實(shí)質(zhì)是地理信息圖層間的空間關(guān)系運(yùn)算。由于受到數(shù)據(jù)精度的限制，在地理信息圖層疊加分析過程中，不同圖層間對象可能出現(xiàn)邊界線段不一致問題，極易造成疊加結(jié)果產(chǎn)生不符合規(guī)范的細(xì)碎多邊形,如不對其進(jìn)行有效處理，將引起后續(xù)分析計(jì)算的異常[1]。因此在進(jìn)行疊加分析計(jì)算時(shí)引入了容限概念，從而在矢量數(shù)據(jù)幾何計(jì)算中修正與維護(hù)數(shù)據(jù)的拓?fù)湟恢滦?。但單純通過高精度節(jié)點(diǎn)捕捉低精度節(jié)點(diǎn)的處理方式很難從根本上避免和消除所有的拓?fù)洳灰恢虑闆r，因此一種較為系統(tǒng)的解決方案就顯得尤為重要。
在拓?fù)湟恢滦蕴幚砗童B加分析過程中存在著大量的計(jì)算幾何運(yùn)算，而基于計(jì)算幾何的算法實(shí)現(xiàn)過程主要面臨兩個(gè)挑戰(zhàn)：一是計(jì)算機(jī)在進(jìn)行數(shù)值計(jì)算時(shí)不可避免的數(shù)值精度誤差[2]。例如計(jì)算幾何中經(jīng)常需要判斷點(diǎn)和線段的空間位置關(guān)系，在通過求算線段方程判斷時(shí)，對方程結(jié)果是否為零的判斷極易出現(xiàn)求算結(jié)果略大或略小于零的情況，導(dǎo)致判斷失效。程序計(jì)算時(shí)的精度損失引起的誤差一般通過兩種方法解決，第一種方法是在中間計(jì)算過程中提高表達(dá)精度，進(jìn)行盡可能的“精確”計(jì)算[3]，第二種方法是設(shè)定對象間的“容限”使得計(jì)算結(jié)果都在容限范圍內(nèi)[2]。另一種挑戰(zhàn)稱之為表達(dá)誤差，由于矢量數(shù)據(jù)的本質(zhì)是真實(shí)地物對象的映射和模擬，因此在生產(chǎn)矢量數(shù)據(jù)的過程中不可避免地會引入表達(dá)誤差，即矢量數(shù)據(jù)和真實(shí)情況的偏移，或稱之為矢量數(shù)據(jù)的不確定性，這種誤差同樣會導(dǎo)致疊加計(jì)算過程出現(xiàn)細(xì)碎多邊形等異常情況?，F(xiàn)有算法中主要通過一種稱為“epsilon geometry/tolerance”[4,5]的方法來處理表達(dá)誤差，即主要通過對待處理數(shù)據(jù)的規(guī)范化來避免誤差，且通過“epsilon geometry/tolerance”這一框架，可同時(shí)處理數(shù)值精度誤差和表達(dá)誤差問題[6,7]。
Milenkovic針對以上問題提出了數(shù)據(jù)規(guī)范化(data normalization)[8]，其解決思路是在計(jì)算分析之前對數(shù)據(jù)進(jìn)行預(yù)處理，用以糾正所存在的拓?fù)洳灰恢聠栴}。Pullar提出了一種效果較好的解決方案[9]，稱之為地圖調(diào)整(map accommodation)過程,該方法基于Milenkovic算法的思路進(jìn)行數(shù)據(jù)調(diào)整，但為了避免Milenkovic算法存在的問題，在節(jié)點(diǎn)捕捉過程中引入聚類分析的概念。通過對待捕捉的節(jié)點(diǎn)進(jìn)行整體的聚類分析達(dá)到改進(jìn)拓?fù)湟恢滦圆蹲叫Ч哪康?，同時(shí)也可以通過在聚類分析中增加限制條件，解決多次移動導(dǎo)致的節(jié)點(diǎn)偏移過大問題。Harvey等提出了一種控制更加嚴(yán)格的以節(jié)點(diǎn)移動為主要方法的拓?fù)湟恢滦蕴幚硭惴╗10]，該算法主要基于聚類分析實(shí)現(xiàn)，通過近似的啟發(fā)式算法選擇節(jié)點(diǎn)，要求用戶先選擇一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)，而后自動調(diào)整另一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)與之匹配。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é)點(diǎn)與弧段間拓?fù)涮幚怼⒐?jié)點(diǎn)間鄰近搜索3個(gè)核心處理過程進(jìn)行詳細(xì)闡述。
1.1 核心數(shù)據(jù)結(jié)構(gòu)
(1)均勻格網(wǎng)索引信息結(jié)構(gòu)。在對待處理數(shù)據(jù)中需進(jìn)行拓?fù)湟恢滦蕴幚淼母鞣N情況進(jìn)行搜索查詢時(shí)，由于均勻格網(wǎng)索引結(jié)構(gòu)實(shí)現(xiàn)簡單且能有效提升查詢性能[12]，因此，本文使用均勻格網(wǎng)索引結(jié)構(gòu)建立空間數(shù)據(jù)索引，其核心數(shù)據(jù)結(jié)構(gòu)主要包括以下3個(gè)組成部分：
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é)點(diǎn)(或弧段)數(shù)目；TSegmentInfo為基本索引信息結(jié)構(gòu)，其由4個(gè)Int型整數(shù)構(gòu)成，其中nDTIndex記錄圖層索引值，nObjIndex記錄該圖層中的對象索引值，nPntIndex記錄該對象中的節(jié)點(diǎn)索引值(當(dāng)針對弧段建立索引時(shí)，即記錄弧段的起始節(jié)點(diǎn)索引值)，nPntPos記錄該節(jié)點(diǎn)的索引節(jié)點(diǎn)數(shù)組Pnts中的位置，數(shù)組長度為nPntCount；pSegmentUnit是一個(gè)TSegmentInfo類型的指針數(shù)組，該指針指向網(wǎng)格索引單元中具體索引的空間數(shù)據(jù)信息。經(jīng)過均勻格網(wǎng)索引建立過程后，空間數(shù)據(jù)中的節(jié)點(diǎn)都存儲在索引節(jié)點(diǎn)數(shù)組Pnts中，同時(shí)被均勻格網(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ù)湟恢滦蕴幚?，本文設(shè)計(jì)了一種較為簡潔統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來存儲各圖層中數(shù)據(jù)對象需要進(jìn)行調(diào)整的信息，核心數(shù)據(jù)結(jié)構(gòu)為一個(gè)結(jié)構(gòu)體和節(jié)點(diǎn)數(shù)組：
struct TopoUnitNodeInfo
{
Array nIntersetPntIndex;
Array nIntersetPntPos;
};
ArrayIntersetPnts
每個(gè)結(jié)構(gòu)體TopoUnitNodeInfo對應(yīng)一個(gè)待調(diào)整的空間對象，nIntersetPntIndex記錄該對象需要調(diào)整的節(jié)點(diǎn)索引(或需要進(jìn)行節(jié)點(diǎn)插入的弧段起始節(jié)點(diǎn)索引)，nIntersetPntIndex記錄該節(jié)點(diǎn)所需調(diào)整的坐標(biāo)在節(jié)點(diǎn)數(shù)組中的位置，即IntersetPnts中記錄的調(diào)整結(jié)果節(jié)點(diǎn)數(shù)組的索引。由于拓?fù)湟恢滦蕴幚矸椒ㄐ柚С侄鄨D層多對象的處理，因此算法中使用的結(jié)構(gòu)為：
VectorparrTopoUnitNodes
parrTopoUnitNodes長度為所需處理的圖層數(shù)目，每個(gè)圖層需要根據(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)類似“十字”形的相交情況時(shí)，需在兩弧段的相交處各插入一個(gè)節(jié)點(diǎn)，即弧段間的相交情況只允許出現(xiàn)在弧段的起始或終止端點(diǎn)處。此過程基本對應(yīng)于Pullar算法中的弧段相交情況，但由于Pullar算法中弧段相交過程新增的節(jié)點(diǎn)有可能存在和其它弧段造成的二次修正情況，因此把該過程放在第一個(gè)流程進(jìn)行處理，使得新增節(jié)點(diǎn)可能導(dǎo)致的和其它弧段或者節(jié)點(diǎn)距離小于容限的情況在后續(xù)過程中依次進(jìn)行修正，避免了多次迭代修正的問題。
整體處理過程可以劃分為檢測和修復(fù)兩大過程，在檢測過程中則對拓?fù)涮幚淼母鲌D層數(shù)據(jù)進(jìn)行遍歷查詢。通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升弧段間關(guān)系判定效率，在建立索引后，依次遍歷所有格網(wǎng)索引結(jié)構(gòu)，在一個(gè)或周邊多個(gè)格網(wǎng)范圍內(nèi)進(jìn)行弧段間相交情況的判定。應(yīng)注意：當(dāng)出現(xiàn)兩弧段交點(diǎn)距某一弧段起始或終止節(jié)點(diǎn)距離在容限范圍內(nèi)的情況時(shí)，則此節(jié)點(diǎn)不需要插入到兩弧段中，而是在后續(xù)的節(jié)點(diǎn)與弧段拓?fù)涮幚磉^程中進(jìn)行處理。
如圖2所示，弧段L1L2和L3L4相交于點(diǎn)P，但由于點(diǎn)P距離節(jié)點(diǎn)L3小于節(jié)點(diǎn)容限，因此此時(shí)點(diǎn)P不被插入到弧段L1L2和L3L4當(dāng)中，而將此情況在后面的節(jié)點(diǎn)與弧段間拓?fù)涮幚磉^程進(jìn)行處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對象，根據(jù)對象每條弧段位置建立網(wǎng)格索引，索引中記錄弧段所屬的數(shù)據(jù)集ID、對象ID、節(jié)點(diǎn)索引值等信息，并將所有弧段中節(jié)點(diǎn)統(tǒng)一存儲到一個(gè)節(jié)點(diǎn)數(shù)組中(相鄰兩弧段共用的起始終止節(jié)點(diǎn)只需存儲一次)。2) 索引建立后，遍歷所有索引格網(wǎng)，依次取出每個(gè)單元格內(nèi)的弧段，并將此弧段和格網(wǎng)內(nèi)其它弧段進(jìn)行相交計(jì)算。需注意：如果兩弧段交點(diǎn)不在此網(wǎng)格內(nèi)，則不記錄，將此情況交由交點(diǎn)所在網(wǎng)格處理，防止重復(fù)記錄插入交點(diǎn)。3) 相交計(jì)算結(jié)束后，按照相交計(jì)算記錄的交點(diǎn)信息，進(jìn)行交點(diǎn)插入處理。需注意：當(dāng)對象某一弧段需添加多個(gè)節(jié)點(diǎn)時(shí)，對新添加的節(jié)點(diǎn)排序，根據(jù)排序后的順序添加交點(diǎn)。
圖2 弧段間拓?fù)涮幚硖厥馇闆r
Fig.2Specialcasesofarcstopologyconsistencyprocess
1.3 節(jié)點(diǎn)與弧段間拓?fù)涮幚?/p>
在節(jié)點(diǎn)與弧段間拓?fù)涮幚磉^程中主要是判別節(jié)點(diǎn)與弧段的拓?fù)潢P(guān)系，以及對于不滿足節(jié)點(diǎn)與弧段拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)，即當(dāng)節(jié)點(diǎn)距某弧段距離小于容限時(shí)，需在弧段上添加此節(jié)點(diǎn)的垂足。此過程基本對應(yīng)于Pullar算法中的弧段插點(diǎn)過程，但由于Pullar算法流程中弧段插點(diǎn)過程理論上存在和其它弧段造成的二次修正情況，因此把該過程放在第二流程進(jìn)行處理，修正過程由第三過程完成。
整體處理過程同樣可以劃分為檢測和修復(fù)兩大過程，在檢測過程中遍歷數(shù)據(jù)，通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升后續(xù)判定速度，在索引建立后，則依次遍歷所有格網(wǎng)，在一個(gè)或周邊多個(gè)格網(wǎng)范圍內(nèi)判定節(jié)點(diǎn)和鄰近弧段的距離。需注意：當(dāng)出現(xiàn)節(jié)點(diǎn)到弧段端點(diǎn)距離小于容限情況時(shí)，則無論節(jié)點(diǎn)與弧段的距離為多少都不進(jìn)行插入，而當(dāng)出現(xiàn)節(jié)點(diǎn)到弧段端點(diǎn)距離大于容限，但節(jié)點(diǎn)的垂足到弧段端點(diǎn)距離小于容限的情況時(shí)，則此垂足點(diǎn)也需插入到弧段中，此情況會在后續(xù)的節(jié)點(diǎn)間鄰近搜索過程中進(jìn)行處理。
如圖3所示，以弧段v1v2為例進(jìn)行節(jié)點(diǎn)與弧段拓?fù)涮幚淼恼f明，當(dāng)節(jié)點(diǎn)v距弧段左右兩端點(diǎn)v1或v2的距離小于容限，即位于圖3中左右端A區(qū)域時(shí)，無需進(jìn)行處理，此情況會在后續(xù)的節(jié)點(diǎn)間鄰近搜索中處理。當(dāng)節(jié)點(diǎn)v距弧段端點(diǎn)距離大于容限，但距弧段距離小于容限，即位于圖3中C區(qū)域時(shí)，需要計(jì)算節(jié)點(diǎn)v到弧段的垂足點(diǎn)，并將此垂足點(diǎn)插入弧段中。有一種特殊情況需要注意：當(dāng)節(jié)點(diǎn)v距弧段端點(diǎn)距離大于容限，但垂足點(diǎn)到弧段端點(diǎn)距離小于容限時(shí)，即圖3中4個(gè)B區(qū)域，此時(shí)仍需將垂足點(diǎn)插入到弧段中，且后續(xù)節(jié)點(diǎn)間鄰近搜索會處理此特殊情況。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)集圖層，取出每個(gè)對象，將其節(jié)點(diǎn)和線段建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲到一個(gè)節(jié)點(diǎn)數(shù)組中。使用兩個(gè)網(wǎng)格索引結(jié)構(gòu)分別存儲所有的節(jié)點(diǎn)信息和所有的弧段信息。需注意：節(jié)點(diǎn)索引中只需記錄節(jié)點(diǎn)的坐標(biāo)信息，無需記錄其所屬的數(shù)據(jù)圖層、對象、點(diǎn)串索引等信息。弧段存入弧段網(wǎng)格索引結(jié)構(gòu)中，索引結(jié)構(gòu)中需要同步記錄該弧段所屬的數(shù)據(jù)圖層、對象、點(diǎn)串索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個(gè)索引網(wǎng)格內(nèi)的節(jié)點(diǎn)v，以v為中心點(diǎn)，擴(kuò)散一個(gè)容限的距離，查詢是否符合節(jié)點(diǎn)插入條件。需注意：如果計(jì)算出的垂足點(diǎn)不在當(dāng)前處理網(wǎng)格內(nèi)，則不記錄，將此情況交由垂足點(diǎn)所在網(wǎng)格處理，防止重復(fù)記錄所需的插入節(jié)點(diǎn)。3) 節(jié)點(diǎn)與弧段位置計(jì)算結(jié)束后，按照記錄的節(jié)點(diǎn)插入信息，進(jìn)行數(shù)據(jù)調(diào)整。
圖3 節(jié)點(diǎn)與弧段間拓?fù)涮幚硖厥馇闆r
Fig.3Specialcasesofvertexandarctopologyconsistencyprocess
1.4 節(jié)點(diǎn)間鄰近搜索
在經(jīng)過弧段間拓?fù)涮幚砗凸?jié)點(diǎn)與弧段間拓?fù)涮幚韮蓚€(gè)過程后，已對數(shù)據(jù)中的弧段相交情況進(jìn)行了節(jié)點(diǎn)插入，并將數(shù)據(jù)中存在的節(jié)點(diǎn)與弧段距離小于容限的情況通過插入垂足節(jié)點(diǎn)的方式轉(zhuǎn)化為距離在容限范圍內(nèi)的節(jié)點(diǎn)問題，此時(shí)需要通過節(jié)點(diǎn)間鄰近搜索過程對這些距離在容限范圍內(nèi)的節(jié)點(diǎn)情況進(jìn)行搜索和處理。不同于Pullar算法中的聚類過程，本文采用節(jié)點(diǎn)間鄰近搜索的策略將這些通過容限相關(guān)的節(jié)點(diǎn)搜索出來，而后統(tǒng)一調(diào)整為同一坐標(biāo)。
如圖4所示，通過節(jié)點(diǎn)v1進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v1在容限范圍內(nèi)的節(jié)點(diǎn)v2搜索出來，而繼續(xù)通過v2進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v2在容限范圍內(nèi)的節(jié)點(diǎn)v3搜索出來，直到通過v3進(jìn)行鄰近點(diǎn)搜索時(shí)不再發(fā)現(xiàn)容限范圍內(nèi)的節(jié)點(diǎn)為止。找到的v1、v2、v33個(gè)節(jié)點(diǎn)被稱為鄰近點(diǎn)簇，如果鄰近點(diǎn)簇中節(jié)點(diǎn)數(shù)目小于用戶設(shè)置的閾值則直接將這些點(diǎn)調(diào)整為與v1點(diǎn)坐標(biāo)一致，如數(shù)目大于用戶設(shè)置的閾值則將這些點(diǎn)的坐標(biāo)位置記錄下來并反饋給用戶進(jìn)行手動編輯處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對象，對其節(jié)點(diǎn)建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲到一個(gè)節(jié)點(diǎn)數(shù)組中。索引結(jié)構(gòu)中需要同步記錄該節(jié)點(diǎn)所屬的數(shù)據(jù)圖層、對象、點(diǎn)數(shù)組索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個(gè)索引網(wǎng)格內(nèi)的節(jié)點(diǎn)v，以v為中心點(diǎn)，擴(kuò)散一個(gè)容限的距
圖4 節(jié)點(diǎn)間鄰近搜索
Fig.4Vertexneighboringsearch
離，如找到距離節(jié)點(diǎn)v在容限范圍內(nèi)的節(jié)點(diǎn)，則以此節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)繼續(xù)進(jìn)行鄰近搜索，直到找不到容限范圍內(nèi)的節(jié)點(diǎn)為止，而后計(jì)算找到的鄰近點(diǎn)簇需調(diào)整到的節(jié)點(diǎn)v1位置。3) 節(jié)點(diǎn)間鄰近搜索結(jié)束后，按照記錄的節(jié)點(diǎn)調(diào)整信息并調(diào)整數(shù)據(jù)。
2 實(shí)驗(yàn)與分析
為驗(yàn)證本文算法的有效性，使用C語言實(shí)現(xiàn)了上文描述的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并與ArcGIS桌面軟件拓?fù)湟恢滦蕴幚淼南嚓P(guān)功能進(jìn)行測試比較。實(shí)驗(yàn)環(huán)境為一臺主頻2.6GHz的雙核處理器PC機(jī)，內(nèi)存為2GB。由于疊加分析操作是對矢量數(shù)據(jù)質(zhì)量要求較高的分析操作，且在疊加分析操作中涉及大量的節(jié)點(diǎn)間匹配計(jì)算、弧段間相交計(jì)算、多邊形生成計(jì)算等復(fù)雜處理，因此選用疊加分析操作作為拓?fù)湟恢滦蕴幚硇Ч尿?yàn)證手段，即在拓?fù)湟恢滦蕴幚砗笫褂茂B加分析操作驗(yàn)證拓?fù)湟恢滦蕴幚淼挠行?。首先選取兩個(gè)面數(shù)據(jù)，分別在ArcGIS和改進(jìn)算法中進(jìn)行拓?fù)湟恢滦蕴幚砗秃罄m(xù)疊加分析處理，而后對兩種處理結(jié)果進(jìn)行比較分析。為了保證測試驗(yàn)證的有效性，針對該數(shù)據(jù)分別使用“相交”和“對稱差”兩種疊加模式，且每種模式下都使用大小不等的兩種處理容限進(jìn)行測試。如表1所示，ArcGIS的拓?fù)湟恢滦蕴幚砗童B加分析操作在同樣的疊加模式下對于容限的改變較不敏感，而改進(jìn)算法中結(jié)果對于容限的改變較為敏感。在4組實(shí)驗(yàn)中，結(jié)果數(shù)據(jù)集總面積一項(xiàng)中表現(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)的處理性能，是一種實(shí)用性較強(qiáng)的處理方法。
表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的處理方式，重點(diǎn)針對各算法的使用情況以及局限性進(jìn)行了分析。在此基礎(chǔ)上提出了一種性能較優(yōu)的改進(jìn)算法，主要包括弧段間拓?fù)涮幚?、?jié)點(diǎn)與弧段間拓?fù)涮幚?、?jié)點(diǎn)間鄰近搜索3個(gè)核心過程，并重點(diǎn)針對處理過程中容限的設(shè)置與處理、算法的核心數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行了詳細(xì)闡述。通過3組實(shí)驗(yàn)對該改進(jìn)算法的處理效果和處理性能進(jìn)行了對比驗(yàn)證與分析，實(shí)驗(yàn)結(jié)果表明，本文所描述的改進(jìn)算法在保證處理效果有效的前提下具有較高的分析處理性能，是一種實(shí)用性較強(qiáng)的拓?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
交通運(yùn)輸部科技項(xiàng)目(2012-364-X04-102);中國科學(xué)院重點(diǎn)部署項(xiàng)目(KZZD-EW-07-01-001);國家科技支撐計(jì)劃項(xiàng)目(2011BAH06B03);資源與環(huán)境信息系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室自主研究項(xiàng)目(088RAC00YA);中國科學(xué)院國防科技創(chuàng)新基金項(xiàng)目(CXJJ-14-M13);北京市科技專項(xiàng)(Z141101004414011)
王少華(1983-)，男，博士，主要研究方向?yàn)镚IS軟件技術(shù)。*通訊作者E-mail:luhao@supermap.com
10.3969/j.issn.1672-0504.2015.01.003
P208
A
1672-0504(2015)01-0012-05
猜你喜歡
關(guān)注減污降碳協(xié)同的一致性和整體性公民與法治(2022年5期)2022-07-29 00:47:28 注重教、學(xué)、評一致性 提高一輪復(fù)習(xí)效率教學(xué)考試(高考物理)(2021年5期)2021-11-08 10:31:22 對歷史課堂教、學(xué)、評一體化(一致性)的幾點(diǎn)探討歷史教學(xué)問題(2021年4期)2021-11-05 07:02:34 IOl-master 700和Pentacam測量Kappa角一致性分析中醫(yī)眼耳鼻喉雜志(2021年1期)2021-07-22 07:38:14 隱蔽失效適航要求符合性驗(yàn)證分析民用飛機(jī)設(shè)計(jì)與研究(2020年4期)2021-01-21 09:15:02 電力系統(tǒng)不平衡分析電子制作(2018年18期)2018-11-14 01:48:24 ONVIF的全新主張：一致性及最訪問控制的Profile A中國公共安全(2017年11期)2017-02-06 05:28:08 電力系統(tǒng)及其自動化發(fā)展趨勢分析山東工業(yè)技術(shù)(2016年15期)2016-12-01 05:31:22 基于事件觸發(fā)的多智能體輸入飽和一致性控制燕山大學(xué)學(xué)報(bào)(2015年4期)2015-12-25 02:19:49 中西醫(yī)結(jié)合治療抑郁癥100例分析中國中醫(yī)藥現(xiàn)代遠(yuǎn)程教育(2014年11期)2014-08-08 13:23:44
王 少 華,鐘 耳 順,李 紹 俊,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é)點(diǎn)與弧段間拓?fù)涮幚?、?jié)點(diǎn)間鄰近搜索等核心過程。對比實(shí)驗(yàn)表明，該算法在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上具有較高的處理性能，是一種實(shí)用性較強(qiáng)的拓?fù)湟恢滦蕴幚硭惴ā?/p>
矢量數(shù)據(jù)；疊加分析；均勻格網(wǎng)索引；拓?fù)湟恢滦?/p>
0 引言
GIS中的疊加分析實(shí)質(zhì)是地理信息圖層間的空間關(guān)系運(yùn)算。由于受到數(shù)據(jù)精度的限制，在地理信息圖層疊加分析過程中，不同圖層間對象可能出現(xiàn)邊界線段不一致問題，極易造成疊加結(jié)果產(chǎn)生不符合規(guī)范的細(xì)碎多邊形,如不對其進(jìn)行有效處理，將引起后續(xù)分析計(jì)算的異常[1]。因此在進(jìn)行疊加分析計(jì)算時(shí)引入了容限概念，從而在矢量數(shù)據(jù)幾何計(jì)算中修正與維護(hù)數(shù)據(jù)的拓?fù)湟恢滦?。但單純通過高精度節(jié)點(diǎn)捕捉低精度節(jié)點(diǎn)的處理方式很難從根本上避免和消除所有的拓?fù)洳灰恢虑闆r，因此一種較為系統(tǒng)的解決方案就顯得尤為重要。
在拓?fù)湟恢滦蕴幚砗童B加分析過程中存在著大量的計(jì)算幾何運(yùn)算，而基于計(jì)算幾何的算法實(shí)現(xiàn)過程主要面臨兩個(gè)挑戰(zhàn)：一是計(jì)算機(jī)在進(jìn)行數(shù)值計(jì)算時(shí)不可避免的數(shù)值精度誤差[2]。例如計(jì)算幾何中經(jīng)常需要判斷點(diǎn)和線段的空間位置關(guān)系，在通過求算線段方程判斷時(shí)，對方程結(jié)果是否為零的判斷極易出現(xiàn)求算結(jié)果略大或略小于零的情況，導(dǎo)致判斷失效。程序計(jì)算時(shí)的精度損失引起的誤差一般通過兩種方法解決，第一種方法是在中間計(jì)算過程中提高表達(dá)精度，進(jìn)行盡可能的“精確”計(jì)算[3]，第二種方法是設(shè)定對象間的“容限”使得計(jì)算結(jié)果都在容限范圍內(nèi)[2]。另一種挑戰(zhàn)稱之為表達(dá)誤差，由于矢量數(shù)據(jù)的本質(zhì)是真實(shí)地物對象的映射和模擬，因此在生產(chǎn)矢量數(shù)據(jù)的過程中不可避免地會引入表達(dá)誤差，即矢量數(shù)據(jù)和真實(shí)情況的偏移，或稱之為矢量數(shù)據(jù)的不確定性，這種誤差同樣會導(dǎo)致疊加計(jì)算過程出現(xiàn)細(xì)碎多邊形等異常情況?，F(xiàn)有算法中主要通過一種稱為“epsilon geometry/tolerance”[4,5]的方法來處理表達(dá)誤差，即主要通過對待處理數(shù)據(jù)的規(guī)范化來避免誤差，且通過“epsilon geometry/tolerance”這一框架，可同時(shí)處理數(shù)值精度誤差和表達(dá)誤差問題[6,7]。
Milenkovic針對以上問題提出了數(shù)據(jù)規(guī)范化(data normalization)[8]，其解決思路是在計(jì)算分析之前對數(shù)據(jù)進(jìn)行預(yù)處理，用以糾正所存在的拓?fù)洳灰恢聠栴}。Pullar提出了一種效果較好的解決方案[9]，稱之為地圖調(diào)整(map accommodation)過程,該方法基于Milenkovic算法的思路進(jìn)行數(shù)據(jù)調(diào)整，但為了避免Milenkovic算法存在的問題，在節(jié)點(diǎn)捕捉過程中引入聚類分析的概念。通過對待捕捉的節(jié)點(diǎn)進(jìn)行整體的聚類分析達(dá)到改進(jìn)拓?fù)湟恢滦圆蹲叫Ч哪康?，同時(shí)也可以通過在聚類分析中增加限制條件，解決多次移動導(dǎo)致的節(jié)點(diǎn)偏移過大問題。Harvey等提出了一種控制更加嚴(yán)格的以節(jié)點(diǎn)移動為主要方法的拓?fù)湟恢滦蕴幚硭惴╗10]，該算法主要基于聚類分析實(shí)現(xiàn)，通過近似的啟發(fā)式算法選擇節(jié)點(diǎn)，要求用戶先選擇一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)，而后自動調(diào)整另一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)與之匹配。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é)點(diǎn)與弧段間拓?fù)涮幚怼⒐?jié)點(diǎn)間鄰近搜索3個(gè)核心處理過程進(jìn)行詳細(xì)闡述。
1.1 核心數(shù)據(jù)結(jié)構(gòu)
(1)均勻格網(wǎng)索引信息結(jié)構(gòu)。在對待處理數(shù)據(jù)中需進(jìn)行拓?fù)湟恢滦蕴幚淼母鞣N情況進(jìn)行搜索查詢時(shí)，由于均勻格網(wǎng)索引結(jié)構(gòu)實(shí)現(xiàn)簡單且能有效提升查詢性能[12]，因此，本文使用均勻格網(wǎng)索引結(jié)構(gòu)建立空間數(shù)據(jù)索引，其核心數(shù)據(jù)結(jié)構(gòu)主要包括以下3個(gè)組成部分：
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é)點(diǎn)(或弧段)數(shù)目；TSegmentInfo為基本索引信息結(jié)構(gòu)，其由4個(gè)Int型整數(shù)構(gòu)成，其中nDTIndex記錄圖層索引值，nObjIndex記錄該圖層中的對象索引值，nPntIndex記錄該對象中的節(jié)點(diǎn)索引值(當(dāng)針對弧段建立索引時(shí)，即記錄弧段的起始節(jié)點(diǎn)索引值)，nPntPos記錄該節(jié)點(diǎn)的索引節(jié)點(diǎn)數(shù)組Pnts中的位置，數(shù)組長度為nPntCount；pSegmentUnit是一個(gè)TSegmentInfo類型的指針數(shù)組，該指針指向網(wǎng)格索引單元中具體索引的空間數(shù)據(jù)信息。經(jīng)過均勻格網(wǎng)索引建立過程后，空間數(shù)據(jù)中的節(jié)點(diǎn)都存儲在索引節(jié)點(diǎn)數(shù)組Pnts中，同時(shí)被均勻格網(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ù)湟恢滦蕴幚?，本文設(shè)計(jì)了一種較為簡潔統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來存儲各圖層中數(shù)據(jù)對象需要進(jìn)行調(diào)整的信息，核心數(shù)據(jù)結(jié)構(gòu)為一個(gè)結(jié)構(gòu)體和節(jié)點(diǎn)數(shù)組：
struct TopoUnitNodeInfo
{
Array
Array
};
Array
每個(gè)結(jié)構(gòu)體TopoUnitNodeInfo對應(yīng)一個(gè)待調(diào)整的空間對象，nIntersetPntIndex記錄該對象需要調(diào)整的節(jié)點(diǎn)索引(或需要進(jìn)行節(jié)點(diǎn)插入的弧段起始節(jié)點(diǎn)索引)，nIntersetPntIndex記錄該節(jié)點(diǎn)所需調(diào)整的坐標(biāo)在節(jié)點(diǎn)數(shù)組中的位置，即IntersetPnts中記錄的調(diào)整結(jié)果節(jié)點(diǎn)數(shù)組的索引。由于拓?fù)湟恢滦蕴幚矸椒ㄐ柚С侄鄨D層多對象的處理，因此算法中使用的結(jié)構(gòu)為：
Vector
parrTopoUnitNodes長度為所需處理的圖層數(shù)目，每個(gè)圖層需要根據(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)類似“十字”形的相交情況時(shí)，需在兩弧段的相交處各插入一個(gè)節(jié)點(diǎn)，即弧段間的相交情況只允許出現(xiàn)在弧段的起始或終止端點(diǎn)處。此過程基本對應(yīng)于Pullar算法中的弧段相交情況，但由于Pullar算法中弧段相交過程新增的節(jié)點(diǎn)有可能存在和其它弧段造成的二次修正情況，因此把該過程放在第一個(gè)流程進(jìn)行處理，使得新增節(jié)點(diǎn)可能導(dǎo)致的和其它弧段或者節(jié)點(diǎn)距離小于容限的情況在后續(xù)過程中依次進(jìn)行修正，避免了多次迭代修正的問題。
整體處理過程可以劃分為檢測和修復(fù)兩大過程，在檢測過程中則對拓?fù)涮幚淼母鲌D層數(shù)據(jù)進(jìn)行遍歷查詢。通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升弧段間關(guān)系判定效率，在建立索引后，依次遍歷所有格網(wǎng)索引結(jié)構(gòu)，在一個(gè)或周邊多個(gè)格網(wǎng)范圍內(nèi)進(jìn)行弧段間相交情況的判定。應(yīng)注意：當(dāng)出現(xiàn)兩弧段交點(diǎn)距某一弧段起始或終止節(jié)點(diǎn)距離在容限范圍內(nèi)的情況時(shí)，則此節(jié)點(diǎn)不需要插入到兩弧段中，而是在后續(xù)的節(jié)點(diǎn)與弧段拓?fù)涮幚磉^程中進(jìn)行處理。
如圖2所示，弧段L1L2和L3L4相交于點(diǎn)P，但由于點(diǎn)P距離節(jié)點(diǎn)L3小于節(jié)點(diǎn)容限，因此此時(shí)點(diǎn)P不被插入到弧段L1L2和L3L4當(dāng)中，而將此情況在后面的節(jié)點(diǎn)與弧段間拓?fù)涮幚磉^程進(jìn)行處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對象，根據(jù)對象每條弧段位置建立網(wǎng)格索引，索引中記錄弧段所屬的數(shù)據(jù)集ID、對象ID、節(jié)點(diǎn)索引值等信息，并將所有弧段中節(jié)點(diǎn)統(tǒng)一存儲到一個(gè)節(jié)點(diǎn)數(shù)組中(相鄰兩弧段共用的起始終止節(jié)點(diǎn)只需存儲一次)。2) 索引建立后，遍歷所有索引格網(wǎng)，依次取出每個(gè)單元格內(nèi)的弧段，并將此弧段和格網(wǎng)內(nèi)其它弧段進(jìn)行相交計(jì)算。需注意：如果兩弧段交點(diǎn)不在此網(wǎng)格內(nèi)，則不記錄，將此情況交由交點(diǎn)所在網(wǎng)格處理，防止重復(fù)記錄插入交點(diǎn)。3) 相交計(jì)算結(jié)束后，按照相交計(jì)算記錄的交點(diǎn)信息，進(jìn)行交點(diǎn)插入處理。需注意：當(dāng)對象某一弧段需添加多個(gè)節(jié)點(diǎn)時(shí)，對新添加的節(jié)點(diǎn)排序，根據(jù)排序后的順序添加交點(diǎn)。
圖2 弧段間拓?fù)涮幚硖厥馇闆r
Fig.2Specialcasesofarcstopologyconsistencyprocess
1.3 節(jié)點(diǎn)與弧段間拓?fù)涮幚?/p>
在節(jié)點(diǎn)與弧段間拓?fù)涮幚磉^程中主要是判別節(jié)點(diǎn)與弧段的拓?fù)潢P(guān)系，以及對于不滿足節(jié)點(diǎn)與弧段拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)，即當(dāng)節(jié)點(diǎn)距某弧段距離小于容限時(shí)，需在弧段上添加此節(jié)點(diǎn)的垂足。此過程基本對應(yīng)于Pullar算法中的弧段插點(diǎn)過程，但由于Pullar算法流程中弧段插點(diǎn)過程理論上存在和其它弧段造成的二次修正情況，因此把該過程放在第二流程進(jìn)行處理，修正過程由第三過程完成。
整體處理過程同樣可以劃分為檢測和修復(fù)兩大過程，在檢測過程中遍歷數(shù)據(jù)，通過建立均勻格網(wǎng)索引結(jié)構(gòu)提升后續(xù)判定速度，在索引建立后，則依次遍歷所有格網(wǎng)，在一個(gè)或周邊多個(gè)格網(wǎng)范圍內(nèi)判定節(jié)點(diǎn)和鄰近弧段的距離。需注意：當(dāng)出現(xiàn)節(jié)點(diǎn)到弧段端點(diǎn)距離小于容限情況時(shí)，則無論節(jié)點(diǎn)與弧段的距離為多少都不進(jìn)行插入，而當(dāng)出現(xiàn)節(jié)點(diǎn)到弧段端點(diǎn)距離大于容限，但節(jié)點(diǎn)的垂足到弧段端點(diǎn)距離小于容限的情況時(shí)，則此垂足點(diǎn)也需插入到弧段中，此情況會在后續(xù)的節(jié)點(diǎn)間鄰近搜索過程中進(jìn)行處理。
如圖3所示，以弧段v1v2為例進(jìn)行節(jié)點(diǎn)與弧段拓?fù)涮幚淼恼f明，當(dāng)節(jié)點(diǎn)v距弧段左右兩端點(diǎn)v1或v2的距離小于容限，即位于圖3中左右端A區(qū)域時(shí)，無需進(jìn)行處理，此情況會在后續(xù)的節(jié)點(diǎn)間鄰近搜索中處理。當(dāng)節(jié)點(diǎn)v距弧段端點(diǎn)距離大于容限，但距弧段距離小于容限，即位于圖3中C區(qū)域時(shí)，需要計(jì)算節(jié)點(diǎn)v到弧段的垂足點(diǎn)，并將此垂足點(diǎn)插入弧段中。有一種特殊情況需要注意：當(dāng)節(jié)點(diǎn)v距弧段端點(diǎn)距離大于容限，但垂足點(diǎn)到弧段端點(diǎn)距離小于容限時(shí)，即圖3中4個(gè)B區(qū)域，此時(shí)仍需將垂足點(diǎn)插入到弧段中，且后續(xù)節(jié)點(diǎn)間鄰近搜索會處理此特殊情況。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)集圖層，取出每個(gè)對象，將其節(jié)點(diǎn)和線段建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲到一個(gè)節(jié)點(diǎn)數(shù)組中。使用兩個(gè)網(wǎng)格索引結(jié)構(gòu)分別存儲所有的節(jié)點(diǎn)信息和所有的弧段信息。需注意：節(jié)點(diǎn)索引中只需記錄節(jié)點(diǎn)的坐標(biāo)信息，無需記錄其所屬的數(shù)據(jù)圖層、對象、點(diǎn)串索引等信息。弧段存入弧段網(wǎng)格索引結(jié)構(gòu)中，索引結(jié)構(gòu)中需要同步記錄該弧段所屬的數(shù)據(jù)圖層、對象、點(diǎn)串索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個(gè)索引網(wǎng)格內(nèi)的節(jié)點(diǎn)v，以v為中心點(diǎn)，擴(kuò)散一個(gè)容限的距離，查詢是否符合節(jié)點(diǎn)插入條件。需注意：如果計(jì)算出的垂足點(diǎn)不在當(dāng)前處理網(wǎng)格內(nèi)，則不記錄，將此情況交由垂足點(diǎn)所在網(wǎng)格處理，防止重復(fù)記錄所需的插入節(jié)點(diǎn)。3) 節(jié)點(diǎn)與弧段位置計(jì)算結(jié)束后，按照記錄的節(jié)點(diǎn)插入信息，進(jìn)行數(shù)據(jù)調(diào)整。
圖3 節(jié)點(diǎn)與弧段間拓?fù)涮幚硖厥馇闆r
Fig.3Specialcasesofvertexandarctopologyconsistencyprocess
1.4 節(jié)點(diǎn)間鄰近搜索
在經(jīng)過弧段間拓?fù)涮幚砗凸?jié)點(diǎn)與弧段間拓?fù)涮幚韮蓚€(gè)過程后，已對數(shù)據(jù)中的弧段相交情況進(jìn)行了節(jié)點(diǎn)插入，并將數(shù)據(jù)中存在的節(jié)點(diǎn)與弧段距離小于容限的情況通過插入垂足節(jié)點(diǎn)的方式轉(zhuǎn)化為距離在容限范圍內(nèi)的節(jié)點(diǎn)問題，此時(shí)需要通過節(jié)點(diǎn)間鄰近搜索過程對這些距離在容限范圍內(nèi)的節(jié)點(diǎn)情況進(jìn)行搜索和處理。不同于Pullar算法中的聚類過程，本文采用節(jié)點(diǎn)間鄰近搜索的策略將這些通過容限相關(guān)的節(jié)點(diǎn)搜索出來，而后統(tǒng)一調(diào)整為同一坐標(biāo)。
如圖4所示，通過節(jié)點(diǎn)v1進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v1在容限范圍內(nèi)的節(jié)點(diǎn)v2搜索出來，而繼續(xù)通過v2進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v2在容限范圍內(nèi)的節(jié)點(diǎn)v3搜索出來，直到通過v3進(jìn)行鄰近點(diǎn)搜索時(shí)不再發(fā)現(xiàn)容限范圍內(nèi)的節(jié)點(diǎn)為止。找到的v1、v2、v33個(gè)節(jié)點(diǎn)被稱為鄰近點(diǎn)簇，如果鄰近點(diǎn)簇中節(jié)點(diǎn)數(shù)目小于用戶設(shè)置的閾值則直接將這些點(diǎn)調(diào)整為與v1點(diǎn)坐標(biāo)一致，如數(shù)目大于用戶設(shè)置的閾值則將這些點(diǎn)的坐標(biāo)位置記錄下來并反饋給用戶進(jìn)行手動編輯處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對象，對其節(jié)點(diǎn)建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲到一個(gè)節(jié)點(diǎn)數(shù)組中。索引結(jié)構(gòu)中需要同步記錄該節(jié)點(diǎn)所屬的數(shù)據(jù)圖層、對象、點(diǎn)數(shù)組索引等信息。2) 遍歷所有索引網(wǎng)格，依次取出每個(gè)索引網(wǎng)格內(nèi)的節(jié)點(diǎn)v，以v為中心點(diǎn)，擴(kuò)散一個(gè)容限的距
圖4 節(jié)點(diǎn)間鄰近搜索
Fig.4Vertexneighboringsearch
離，如找到距離節(jié)點(diǎn)v在容限范圍內(nèi)的節(jié)點(diǎn)，則以此節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)繼續(xù)進(jìn)行鄰近搜索，直到找不到容限范圍內(nèi)的節(jié)點(diǎn)為止，而后計(jì)算找到的鄰近點(diǎn)簇需調(diào)整到的節(jié)點(diǎn)v1位置。3) 節(jié)點(diǎn)間鄰近搜索結(jié)束后，按照記錄的節(jié)點(diǎn)調(diào)整信息并調(diào)整數(shù)據(jù)。
2 實(shí)驗(yàn)與分析
為驗(yàn)證本文算法的有效性，使用C語言實(shí)現(xiàn)了上文描述的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并與ArcGIS桌面軟件拓?fù)湟恢滦蕴幚淼南嚓P(guān)功能進(jìn)行測試比較。實(shí)驗(yàn)環(huán)境為一臺主頻2.6GHz的雙核處理器PC機(jī)，內(nèi)存為2GB。由于疊加分析操作是對矢量數(shù)據(jù)質(zhì)量要求較高的分析操作，且在疊加分析操作中涉及大量的節(jié)點(diǎn)間匹配計(jì)算、弧段間相交計(jì)算、多邊形生成計(jì)算等復(fù)雜處理，因此選用疊加分析操作作為拓?fù)湟恢滦蕴幚硇Ч尿?yàn)證手段，即在拓?fù)湟恢滦蕴幚砗笫褂茂B加分析操作驗(yàn)證拓?fù)湟恢滦蕴幚淼挠行?。首先選取兩個(gè)面數(shù)據(jù)，分別在ArcGIS和改進(jìn)算法中進(jìn)行拓?fù)湟恢滦蕴幚砗秃罄m(xù)疊加分析處理，而后對兩種處理結(jié)果進(jìn)行比較分析。為了保證測試驗(yàn)證的有效性，針對該數(shù)據(jù)分別使用“相交”和“對稱差”兩種疊加模式，且每種模式下都使用大小不等的兩種處理容限進(jìn)行測試。如表1所示，ArcGIS的拓?fù)湟恢滦蕴幚砗童B加分析操作在同樣的疊加模式下對于容限的改變較不敏感，而改進(jìn)算法中結(jié)果對于容限的改變較為敏感。在4組實(shí)驗(yàn)中，結(jié)果數(shù)據(jù)集總面積一項(xiàng)中表現(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)的處理性能，是一種實(shí)用性較強(qiáng)的處理方法。
表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的處理方式，重點(diǎn)針對各算法的使用情況以及局限性進(jìn)行了分析。在此基礎(chǔ)上提出了一種性能較優(yōu)的改進(jìn)算法，主要包括弧段間拓?fù)涮幚?、?jié)點(diǎn)與弧段間拓?fù)涮幚?、?jié)點(diǎn)間鄰近搜索3個(gè)核心過程，并重點(diǎn)針對處理過程中容限的設(shè)置與處理、算法的核心數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行了詳細(xì)闡述。通過3組實(shí)驗(yàn)對該改進(jìn)算法的處理效果和處理性能進(jìn)行了對比驗(yàn)證與分析，實(shí)驗(yàn)結(jié)果表明，本文所描述的改進(jìn)算法在保證處理效果有效的前提下具有較高的分析處理性能，是一種實(shí)用性較強(qiáng)的拓?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
交通運(yùn)輸部科技項(xiàng)目(2012-364-X04-102);中國科學(xué)院重點(diǎn)部署項(xiàng)目(KZZD-EW-07-01-001);國家科技支撐計(jì)劃項(xiàng)目(2011BAH06B03);資源與環(huán)境信息系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室自主研究項(xiàng)目(088RAC00YA);中國科學(xué)院國防科技創(chuàng)新基金項(xiàng)目(CXJJ-14-M13);北京市科技專項(xiàng)(Z141101004414011)
王少華(1983-)，男，博士，主要研究方向?yàn)镚IS軟件技術(shù)。*通訊作者E-mail:luhao@supermap.com
10.3969/j.issn.1672-0504.2015.01.003
P208
A
1672-0504(2015)01-0012-05
猜你喜歡
公民與法治(2022年5期)2022-07-29 00:47:28
教學(xué)考試(高考物理)(2021年5期)2021-11-08 10:31:22
歷史教學(xué)問題(2021年4期)2021-11-05 07:02:34
中醫(yī)眼耳鼻喉雜志(2021年1期)2021-07-22 07:38:14
民用飛機(jī)設(shè)計(jì)與研究(2020年4期)2021-01-21 09:15:02
電子制作(2018年18期)2018-11-14 01:48:24
中國公共安全(2017年11期)2017-02-06 05:28:08
山東工業(yè)技術(shù)(2016年15期)2016-12-01 05:31:22
燕山大學(xué)學(xué)報(bào)(2015年4期)2015-12-25 02:19:49
中國中醫(yī)藥現(xiàn)代遠(yuǎn)程教育(2014年11期)2014-08-08 13:23:44
