面向矢量數(shù)據(jù)疊加分析的拓?fù)湟恢滦蕴幚硌芯?/h1>
2015-06-07 11:31王少華,鐘耳順,李紹俊,3,盧浩
地理與地理信息科學(xué) 2015年1期
王 少 華,鐘 耳 順,李 紹 俊,3,盧 浩
(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國(guó)科學(xué)院大學(xué)，北京 100039)
?
面向矢量數(shù)據(jù)疊加分析的拓?fù)湟恢滦蕴幚硌芯?/p>
王 少 華1,2,鐘 耳 順1,李 紹 俊1,2,3,盧 浩2*
(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國(guó)科學(xué)院大學(xué)，北京 100039)
在疊加分析、緩沖區(qū)分析、拓?fù)浞治龅雀鞣N矢量數(shù)據(jù)分析過(guò)程中，首要面對(duì)的便是矢量數(shù)據(jù)拓?fù)湟恢滦詥?wèn)題。拓?fù)湟恢滦蕴幚硎菍?duì)GIS矢量數(shù)據(jù)中由于采集、存儲(chǔ)、壓縮、轉(zhuǎn)換導(dǎo)致的空間拓?fù)潢P(guān)系不一致問(wè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)間鄰近搜索等核心過(guò)程。對(duì)比實(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ù)精度的限制，在地理信息圖層疊加分析過(guò)程中，不同圖層間對(duì)象可能出現(xiàn)邊界線段不一致問(wèn)題，極易造成疊加結(jié)果產(chǎn)生不符合規(guī)范的細(xì)碎多邊形,如不對(duì)其進(jìn)行有效處理，將引起后續(xù)分析計(jì)算的異常[1]。因此在進(jìn)行疊加分析計(jì)算時(shí)引入了容限概念，從而在矢量數(shù)據(jù)幾何計(jì)算中修正與維護(hù)數(shù)據(jù)的拓?fù)湟恢滦?。但單純通過(guò)高精度節(jié)點(diǎn)捕捉低精度節(jié)點(diǎn)的處理方式很難從根本上避免和消除所有的拓?fù)洳灰恢虑闆r，因此一種較為系統(tǒng)的解決方案就顯得尤為重要。
在拓?fù)湟恢滦蕴幚砗童B加分析過(guò)程中存在著大量的計(jì)算幾何運(yùn)算，而基于計(jì)算幾何的算法實(shí)現(xiàn)過(guò)程主要面臨兩個(gè)挑戰(zhàn)：一是計(jì)算機(jī)在進(jìn)行數(shù)值計(jì)算時(shí)不可避免的數(shù)值精度誤差[2]。例如計(jì)算幾何中經(jīng)常需要判斷點(diǎn)和線段的空間位置關(guān)系，在通過(guò)求算線段方程判斷時(shí)，對(duì)方程結(jié)果是否為零的判斷極易出現(xiàn)求算結(jié)果略大或略小于零的情況，導(dǎo)致判斷失效。程序計(jì)算時(shí)的精度損失引起的誤差一般通過(guò)兩種方法解決，第一種方法是在中間計(jì)算過(guò)程中提高表達(dá)精度，進(jìn)行盡可能的“精確”計(jì)算[3]，第二種方法是設(shè)定對(duì)象間的“容限”使得計(jì)算結(jié)果都在容限范圍內(nèi)[2]。另一種挑戰(zhàn)稱之為表達(dá)誤差，由于矢量數(shù)據(jù)的本質(zhì)是真實(shí)地物對(duì)象的映射和模擬，因此在生產(chǎn)矢量數(shù)據(jù)的過(guò)程中不可避免地會(huì)引入表達(dá)誤差，即矢量數(shù)據(jù)和真實(shí)情況的偏移，或稱之為矢量數(shù)據(jù)的不確定性，這種誤差同樣會(huì)導(dǎo)致疊加計(jì)算過(guò)程出現(xiàn)細(xì)碎多邊形等異常情況。現(xiàn)有算法中主要通過(guò)一種稱為“epsilon geometry/tolerance”[4,5]的方法來(lái)處理表達(dá)誤差，即主要通過(guò)對(duì)待處理數(shù)據(jù)的規(guī)范化來(lái)避免誤差，且通過(guò)“epsilon geometry/tolerance”這一框架，可同時(shí)處理數(shù)值精度誤差和表達(dá)誤差問(wèn)題[6,7]。
Milenkovic針對(duì)以上問(wèn)題提出了數(shù)據(jù)規(guī)范化(data normalization)[8]，其解決思路是在計(jì)算分析之前對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，用以糾正所存在的拓?fù)洳灰恢聠?wèn)題。Pullar提出了一種效果較好的解決方案[9]，稱之為地圖調(diào)整(map accommodation)過(guò)程,該方法基于Milenkovic算法的思路進(jìn)行數(shù)據(jù)調(diào)整，但為了避免Milenkovic算法存在的問(wèn)題，在節(jié)點(diǎn)捕捉過(guò)程中引入聚類分析的概念。通過(guò)對(duì)待捕捉的節(jié)點(diǎn)進(jìn)行整體的聚類分析達(dá)到改進(jìn)拓?fù)湟恢滦圆蹲叫Ч哪康?，同時(shí)也可以通過(guò)在聚類分析中增加限制條件，解決多次移動(dòng)導(dǎo)致的節(jié)點(diǎn)偏移過(guò)大問(wèn)題。Harvey等提出了一種控制更加嚴(yán)格的以節(jié)點(diǎn)移動(dòng)為主要方法的拓?fù)湟恢滦蕴幚硭惴╗10]，該算法主要基于聚類分析實(shí)現(xiàn)，通過(guò)近似的啟發(fā)式算法選擇節(jié)點(diǎn)，要求用戶先選擇一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)，而后自動(dòng)調(diào)整另一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)與之匹配。ArcGIS的處理模式[11]整體上和Pullar算法接近，且Pullar算法中提及的需要迭代多次操作的情況在ArcGIS中也有體現(xiàn)。
1 拓?fù)湟恢滦蕴幚砀倪M(jìn)算法
針對(duì)已有的拓?fù)湟恢滦蕴幚硭惴ù嬖诘牟蛔?，本文提出一種性能較優(yōu)的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并對(duì)算法核心數(shù)據(jù)結(jié)構(gòu)以及弧段間拓?fù)涮幚?、?jié)點(diǎn)與弧段間拓?fù)涮幚?、?jié)點(diǎn)間鄰近搜索3個(gè)核心處理過(guò)程進(jìn)行詳細(xì)闡述。
1.1 核心數(shù)據(jù)結(jié)構(gòu)
(1)均勻格網(wǎng)索引信息結(jié)構(gòu)。在對(duì)待處理數(shù)據(jù)中需進(jìn)行拓?fù)湟恢滦蕴幚淼母鞣N情況進(jìn)行搜索查詢時(shí)，由于均勻格網(wǎng)索引結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎ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記錄該圖層中的對(duì)象索引值，nPntIndex記錄該對(duì)象中的節(jié)點(diǎn)索引值(當(dāng)針對(duì)弧段建立索引時(shí)，即記錄弧段的起始節(jié)點(diǎn)索引值)，nPntPos記錄該節(jié)點(diǎn)的索引節(jié)點(diǎn)數(shù)組Pnts中的位置，數(shù)組長(zhǎng)度為nPntCount；pSegmentUnit是一個(gè)TSegmentInfo類型的指針數(shù)組，該指針指向網(wǎng)格索引單元中具體索引的空間數(shù)據(jù)信息。經(jīng)過(guò)均勻格網(wǎng)索引建立過(guò)程后，空間數(shù)據(jù)中的節(jié)點(diǎn)都存儲(chǔ)在索引節(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ì)了一種較為簡(jiǎn)潔統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)各圖層中數(shù)據(jù)對(duì)象需要進(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對(duì)應(yīng)一個(gè)待調(diào)整的空間對(duì)象，nIntersetPntIndex記錄該對(duì)象需要調(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層多對(duì)象的處理，因此算法中使用的結(jié)構(gòu)為：
VectorparrTopoUnitNodes
parrTopoUnitNodes長(zhǎng)度為所需處理的圖層數(shù)目，每個(gè)圖層需要根據(jù)其對(duì)象數(shù)目nObjCount申請(qǐng)所需的內(nèi)存。
TopoUnitNodeInfo*pTopoUnitNodeInfo=new TopoUnitNodeInfo[nObjCount]
1.2 弧段間拓?fù)涮幚?/p>
弧段間拓?fù)涮幚磉^(guò)程主要是進(jìn)行弧段與弧段拓?fù)潢P(guān)系的判別，以及對(duì)不滿足弧段與弧段間拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)。當(dāng)兩弧段位置關(guān)系出現(xiàn)類似“十字”形的相交情況時(shí)，需在兩弧段的相交處各插入一個(gè)節(jié)點(diǎn)，即弧段間的相交情況只允許出現(xiàn)在弧段的起始或終止端點(diǎn)處。此過(guò)程基本對(duì)應(yīng)于Pullar算法中的弧段相交情況，但由于Pullar算法中弧段相交過(guò)程新增的節(jié)點(diǎn)有可能存在和其它弧段造成的二次修正情況，因此把該過(guò)程放在第一個(gè)流程進(jìn)行處理，使得新增節(jié)點(diǎn)可能導(dǎo)致的和其它弧段或者節(jié)點(diǎn)距離小于容限的情況在后續(xù)過(guò)程中依次進(jìn)行修正，避免了多次迭代修正的問(wèn)題。
整體處理過(guò)程可以劃分為檢測(cè)和修復(fù)兩大過(guò)程，在檢測(cè)過(guò)程中則對(duì)拓?fù)涮幚淼母鲌D層數(shù)據(jù)進(jìn)行遍歷查詢。通過(guò)建立均勻格網(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ù)涮幚磉^(guò)程中進(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ù)涮幚磉^(guò)程進(jìn)行處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對(duì)象，根據(jù)對(duì)象每條弧段位置建立網(wǎng)格索引，索引中記錄弧段所屬的數(shù)據(jù)集ID、對(duì)象ID、節(jié)點(diǎn)索引值等信息，并將所有弧段中節(jié)點(diǎn)統(tǒng)一存儲(chǔ)到一個(gè)節(jié)點(diǎn)數(shù)組中(相鄰兩弧段共用的起始終止節(jié)點(diǎn)只需存儲(chǔ)一次)。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)對(duì)象某一弧段需添加多個(gè)節(jié)點(diǎn)時(shí)，對(duì)新添加的節(jié)點(diǎn)排序，根據(jù)排序后的順序添加交點(diǎn)。
圖2 弧段間拓?fù)涮幚硖厥馇闆r
Fig.2Specialcasesofarcstopologyconsistencyprocess
1.3 節(jié)點(diǎn)與弧段間拓?fù)涮幚?/p>
在節(jié)點(diǎn)與弧段間拓?fù)涮幚磉^(guò)程中主要是判別節(jié)點(diǎn)與弧段的拓?fù)潢P(guān)系，以及對(duì)于不滿足節(jié)點(diǎn)與弧段拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)，即當(dāng)節(jié)點(diǎn)距某弧段距離小于容限時(shí)，需在弧段上添加此節(jié)點(diǎn)的垂足。此過(guò)程基本對(duì)應(yīng)于Pullar算法中的弧段插點(diǎn)過(guò)程，但由于Pullar算法流程中弧段插點(diǎn)過(guò)程理論上存在和其它弧段造成的二次修正情況，因此把該過(guò)程放在第二流程進(jìn)行處理，修正過(guò)程由第三過(guò)程完成。
整體處理過(guò)程同樣可以劃分為檢測(cè)和修復(fù)兩大過(guò)程，在檢測(cè)過(guò)程中遍歷數(shù)據(jù)，通過(guò)建立均勻格網(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í)，則無(wú)論節(jié)點(diǎn)與弧段的距離為多少都不進(jìn)行插入，而當(dāng)出現(xiàn)節(jié)點(diǎn)到弧段端點(diǎn)距離大于容限，但節(jié)點(diǎn)的垂足到弧段端點(diǎn)距離小于容限的情況時(shí)，則此垂足點(diǎn)也需插入到弧段中，此情況會(huì)在后續(xù)的節(jié)點(diǎn)間鄰近搜索過(guò)程中進(jìn)行處理。
如圖3所示，以弧段v1v2為例進(jìn)行節(jié)點(diǎn)與弧段拓?fù)涮幚淼恼f(shuō)明，當(dāng)節(jié)點(diǎn)v距弧段左右兩端點(diǎn)v1或v2的距離小于容限，即位于圖3中左右端A區(qū)域時(shí)，無(wú)需進(jìn)行處理，此情況會(huì)在后續(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)間鄰近搜索會(huì)處理此特殊情況。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)集圖層，取出每個(gè)對(duì)象，將其節(jié)點(diǎn)和線段建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲(chǔ)到一個(gè)節(jié)點(diǎn)數(shù)組中。使用兩個(gè)網(wǎng)格索引結(jié)構(gòu)分別存儲(chǔ)所有的節(jié)點(diǎn)信息和所有的弧段信息。需注意：節(jié)點(diǎn)索引中只需記錄節(jié)點(diǎn)的坐標(biāo)信息，無(wú)需記錄其所屬的數(shù)據(jù)圖層、對(duì)象、點(diǎn)串索引等信息?；《未嫒牖《尉W(wǎng)格索引結(jié)構(gòu)中，索引結(jié)構(gòu)中需要同步記錄該弧段所屬的數(shù)據(jù)圖層、對(duì)象、點(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)過(guò)弧段間拓?fù)涮幚砗凸?jié)點(diǎn)與弧段間拓?fù)涮幚韮蓚€(gè)過(guò)程后，已對(duì)數(shù)據(jù)中的弧段相交情況進(jìn)行了節(jié)點(diǎn)插入，并將數(shù)據(jù)中存在的節(jié)點(diǎn)與弧段距離小于容限的情況通過(guò)插入垂足節(jié)點(diǎn)的方式轉(zhuǎn)化為距離在容限范圍內(nèi)的節(jié)點(diǎn)問(wèn)題，此時(shí)需要通過(guò)節(jié)點(diǎn)間鄰近搜索過(guò)程對(duì)這些距離在容限范圍內(nèi)的節(jié)點(diǎn)情況進(jìn)行搜索和處理。不同于Pullar算法中的聚類過(guò)程，本文采用節(jié)點(diǎn)間鄰近搜索的策略將這些通過(guò)容限相關(guān)的節(jié)點(diǎn)搜索出來(lái)，而后統(tǒng)一調(diào)整為同一坐標(biāo)。
如圖4所示，通過(guò)節(jié)點(diǎn)v1進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v1在容限范圍內(nèi)的節(jié)點(diǎn)v2搜索出來(lái)，而繼續(xù)通過(guò)v2進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v2在容限范圍內(nèi)的節(jié)點(diǎn)v3搜索出來(lái)，直到通過(guò)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)位置記錄下來(lái)并反饋給用戶進(jìn)行手動(dòng)編輯處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對(duì)象，對(duì)其節(jié)點(diǎn)建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲(chǔ)到一個(gè)節(jié)點(diǎn)數(shù)組中。索引結(jié)構(gòu)中需要同步記錄該節(jié)點(diǎn)所屬的數(shù)據(jù)圖層、對(duì)象、點(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語(yǔ)言實(shí)現(xiàn)了上文描述的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并與ArcGIS桌面軟件拓?fù)湟恢滦蕴幚淼南嚓P(guān)功能進(jìn)行測(cè)試比較。實(shí)驗(yàn)環(huán)境為一臺(tái)主頻2.6GHz的雙核處理器PC機(jī)，內(nèi)存為2GB。由于疊加分析操作是對(duì)矢量數(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ù)疊加分析處理，而后對(duì)兩種處理結(jié)果進(jìn)行比較分析。為了保證測(cè)試驗(yàn)證的有效性，針對(duì)該數(shù)據(jù)分別使用“相交”和“對(duì)稱差”兩種疊加模式，且每種模式下都使用大小不等的兩種處理容限進(jìn)行測(cè)試。如表1所示，ArcGIS的拓?fù)湟恢滦蕴幚砗童B加分析操作在同樣的疊加模式下對(duì)于容限的改變較不敏感，而改進(jìn)算法中結(jié)果對(duì)于容限的改變較為敏感。在4組實(shí)驗(yàn)中，結(jié)果數(shù)據(jù)集總面積一項(xiàng)中表現(xiàn)出和ArcGIS較好的一致性，ArcGIS處理結(jié)果和改進(jìn)算法處理結(jié)果總面積偏差都在十萬(wàn)分之一以下，且有一組測(cè)試數(shù)據(jù)的總面積偏差在百萬(wàn)分之一以下，即經(jīng)過(guò)拓?fù)湟恢滦愿倪M(jìn)算法處理后的數(shù)據(jù)在疊加分析操作過(guò)程中表現(xiàn)出較好的數(shù)據(jù)質(zhì)量和處理效果。
表1 改進(jìn)算法和ArcGIS對(duì)比測(cè)試結(jié)果
Table 1 The result comparison of improved algorithm and ArcGIS
序號(hào)疊加方式疊加容限ArcGIS總面積(m2)改進(jìn)算法總面積(m2)面積偏差(m2)1相交5．25461348429912294．371348429614234．562．21042E-072相交0．00011348429912294．371348424580959．503．95374E-063對(duì)稱差5．25468183976303662．088183956850405．882．37699E-064對(duì)稱差0．00018183976303662．088183961789600．571．77347E-06
在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上，針對(duì)該改進(jìn)算法的性能與ArcGIS進(jìn)行進(jìn)一步的對(duì)比測(cè)試，為了保證測(cè)試的有效性，分別針對(duì)常用的線數(shù)據(jù)類型和面數(shù)據(jù)類型，選用了多組規(guī)模不等的空間數(shù)據(jù)進(jìn)行對(duì)比測(cè)試(表2)。由表2可知，無(wú)論是在線數(shù)據(jù)類型還是在面數(shù)據(jù)類型對(duì)比測(cè)試中，在多種數(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ù)類型性能對(duì)比測(cè)試結(jié)果
Table 2 The comparison of line and polygon dataset performance
序號(hào)線數(shù)據(jù)類型面數(shù)據(jù)類型對(duì)象數(shù)目ArcGIS(s)改進(jìn)算法(s)性能提升(%)對(duì)象數(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ù)集性能對(duì)比測(cè)試 圖6 面數(shù)據(jù)類型性能對(duì)比測(cè)試
Fig.5 Comparison of the line dataset performance Fig.6 Comparison of the polygon dataset performance
3 結(jié)語(yǔ)
在GIS矢量數(shù)據(jù)相關(guān)的各種空間分析中，拓?fù)湟恢滦缘奶幚硇Чc處理性能對(duì)于后續(xù)包括疊加分析、緩沖區(qū)分析、空間查詢等各種空間分析效果有較大的影響。本文首先針對(duì)已有的較為典型的拓?fù)湟恢滦蕴幚硭惴ㄟM(jìn)行了闡述和分析，主要包括Milenkovic算法、Pullar算法、Harvey&Vauglin算法以及ArcGIS的處理方式，重點(diǎn)針對(duì)各算法的使用情況以及局限性進(jìn)行了分析。在此基礎(chǔ)上提出了一種性能較優(yōu)的改進(jìn)算法，主要包括弧段間拓?fù)涮幚?、?jié)點(diǎn)與弧段間拓?fù)涮幚怼⒐?jié)點(diǎn)間鄰近搜索3個(gè)核心過(guò)程，并重點(diǎn)針對(duì)處理過(guò)程中容限的設(shè)置與處理、算法的核心數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行了詳細(xì)闡述。通過(guò)3組實(shí)驗(yàn)對(duì)該改進(jìn)算法的處理效果和處理性能進(jìn)行了對(duì)比驗(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] 王少華,鐘耳順,盧浩,等.基于非均勻多級(jí)網(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);中國(guó)科學(xué)院重點(diǎn)部署項(xiàng)目(KZZD-EW-07-01-001);國(guó)家科技支撐計(jì)劃項(xiàng)目(2011BAH06B03);資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室自主研究項(xiàng)目(088RAC00YA);中國(guó)科學(xué)院國(guó)防科技創(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
猜你喜歡
基于改進(jìn)弧段切點(diǎn)弦的多橢圓檢測(cè)電子設(shè)計(jì)工程(2022年24期)2022-12-23 鋼絲繩支撐波狀擋邊帶式輸送機(jī)物料通過(guò)支座的軌跡研究現(xiàn)代工業(yè)經(jīng)濟(jì)和信息化(2022年9期)2022-11-03 遙感數(shù)據(jù)即得即用（Ready To Use，RTU）地理格網(wǎng)產(chǎn)品規(guī)范 交通運(yùn)輸網(wǎng)絡(luò)的二叉堆索引及路徑算法優(yōu)化應(yīng)用科學(xué)學(xué)報(bào)(2020年6期)2021-01-04 實(shí)時(shí)電離層格網(wǎng)數(shù)據(jù)精度評(píng)估空間科學(xué)學(xué)報(bào)(2020年6期)2020-07-21 電弧增材制造過(guò)程的外形控制優(yōu)化電加工與模具(2020年2期)2020-04-29 矢量點(diǎn)狀數(shù)據(jù)抽稀方法的研究與實(shí)現(xiàn)城市勘測(cè)(2019年4期)2019-09-05 解密照片合成利器圖層混合模式攝影之友(影像視覺(jué))(2018年1期)2018-03-22 巧用混合圖層 制作抽象動(dòng)感森林攝影之友(影像視覺(jué))(2017年8期)2017-11-27 跟我學(xué)添加真實(shí)的光照效果影像研究與醫(yī)學(xué)應(yīng)用(2015年6期)2015-08-15
王 少 華,鐘 耳 順,李 紹 俊,3,盧 浩
(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國(guó)科學(xué)院大學(xué)，北京 100039)
?
面向矢量數(shù)據(jù)疊加分析的拓?fù)湟恢滦蕴幚硌芯?/p>
王 少 華1,2,鐘 耳 順1,李 紹 俊1,2,3,盧 浩2*
(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.北京超圖軟件股份有限公司，北京 100015；3.中國(guó)科學(xué)院大學(xué)，北京 100039)
在疊加分析、緩沖區(qū)分析、拓?fù)浞治龅雀鞣N矢量數(shù)據(jù)分析過(guò)程中，首要面對(duì)的便是矢量數(shù)據(jù)拓?fù)湟恢滦詥?wèn)題。拓?fù)湟恢滦蕴幚硎菍?duì)GIS矢量數(shù)據(jù)中由于采集、存儲(chǔ)、壓縮、轉(zhuǎn)換導(dǎo)致的空間拓?fù)潢P(guān)系不一致問(wè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)間鄰近搜索等核心過(guò)程。對(duì)比實(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ù)精度的限制，在地理信息圖層疊加分析過(guò)程中，不同圖層間對(duì)象可能出現(xiàn)邊界線段不一致問(wèn)題，極易造成疊加結(jié)果產(chǎn)生不符合規(guī)范的細(xì)碎多邊形,如不對(duì)其進(jìn)行有效處理，將引起后續(xù)分析計(jì)算的異常[1]。因此在進(jìn)行疊加分析計(jì)算時(shí)引入了容限概念，從而在矢量數(shù)據(jù)幾何計(jì)算中修正與維護(hù)數(shù)據(jù)的拓?fù)湟恢滦?。但單純通過(guò)高精度節(jié)點(diǎn)捕捉低精度節(jié)點(diǎn)的處理方式很難從根本上避免和消除所有的拓?fù)洳灰恢虑闆r，因此一種較為系統(tǒng)的解決方案就顯得尤為重要。
在拓?fù)湟恢滦蕴幚砗童B加分析過(guò)程中存在著大量的計(jì)算幾何運(yùn)算，而基于計(jì)算幾何的算法實(shí)現(xiàn)過(guò)程主要面臨兩個(gè)挑戰(zhàn)：一是計(jì)算機(jī)在進(jìn)行數(shù)值計(jì)算時(shí)不可避免的數(shù)值精度誤差[2]。例如計(jì)算幾何中經(jīng)常需要判斷點(diǎn)和線段的空間位置關(guān)系，在通過(guò)求算線段方程判斷時(shí)，對(duì)方程結(jié)果是否為零的判斷極易出現(xiàn)求算結(jié)果略大或略小于零的情況，導(dǎo)致判斷失效。程序計(jì)算時(shí)的精度損失引起的誤差一般通過(guò)兩種方法解決，第一種方法是在中間計(jì)算過(guò)程中提高表達(dá)精度，進(jìn)行盡可能的“精確”計(jì)算[3]，第二種方法是設(shè)定對(duì)象間的“容限”使得計(jì)算結(jié)果都在容限范圍內(nèi)[2]。另一種挑戰(zhàn)稱之為表達(dá)誤差，由于矢量數(shù)據(jù)的本質(zhì)是真實(shí)地物對(duì)象的映射和模擬，因此在生產(chǎn)矢量數(shù)據(jù)的過(guò)程中不可避免地會(huì)引入表達(dá)誤差，即矢量數(shù)據(jù)和真實(shí)情況的偏移，或稱之為矢量數(shù)據(jù)的不確定性，這種誤差同樣會(huì)導(dǎo)致疊加計(jì)算過(guò)程出現(xiàn)細(xì)碎多邊形等異常情況。現(xiàn)有算法中主要通過(guò)一種稱為“epsilon geometry/tolerance”[4,5]的方法來(lái)處理表達(dá)誤差，即主要通過(guò)對(duì)待處理數(shù)據(jù)的規(guī)范化來(lái)避免誤差，且通過(guò)“epsilon geometry/tolerance”這一框架，可同時(shí)處理數(shù)值精度誤差和表達(dá)誤差問(wèn)題[6,7]。
Milenkovic針對(duì)以上問(wèn)題提出了數(shù)據(jù)規(guī)范化(data normalization)[8]，其解決思路是在計(jì)算分析之前對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，用以糾正所存在的拓?fù)洳灰恢聠?wèn)題。Pullar提出了一種效果較好的解決方案[9]，稱之為地圖調(diào)整(map accommodation)過(guò)程,該方法基于Milenkovic算法的思路進(jìn)行數(shù)據(jù)調(diào)整，但為了避免Milenkovic算法存在的問(wèn)題，在節(jié)點(diǎn)捕捉過(guò)程中引入聚類分析的概念。通過(guò)對(duì)待捕捉的節(jié)點(diǎn)進(jìn)行整體的聚類分析達(dá)到改進(jìn)拓?fù)湟恢滦圆蹲叫Ч哪康?，同時(shí)也可以通過(guò)在聚類分析中增加限制條件，解決多次移動(dòng)導(dǎo)致的節(jié)點(diǎn)偏移過(guò)大問(wèn)題。Harvey等提出了一種控制更加嚴(yán)格的以節(jié)點(diǎn)移動(dòng)為主要方法的拓?fù)湟恢滦蕴幚硭惴╗10]，該算法主要基于聚類分析實(shí)現(xiàn)，通過(guò)近似的啟發(fā)式算法選擇節(jié)點(diǎn)，要求用戶先選擇一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)，而后自動(dòng)調(diào)整另一個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)與之匹配。ArcGIS的處理模式[11]整體上和Pullar算法接近，且Pullar算法中提及的需要迭代多次操作的情況在ArcGIS中也有體現(xiàn)。
1 拓?fù)湟恢滦蕴幚砀倪M(jìn)算法
針對(duì)已有的拓?fù)湟恢滦蕴幚硭惴ù嬖诘牟蛔?，本文提出一種性能較優(yōu)的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并對(duì)算法核心數(shù)據(jù)結(jié)構(gòu)以及弧段間拓?fù)涮幚?、?jié)點(diǎn)與弧段間拓?fù)涮幚?、?jié)點(diǎn)間鄰近搜索3個(gè)核心處理過(guò)程進(jìn)行詳細(xì)闡述。
1.1 核心數(shù)據(jù)結(jié)構(gòu)
(1)均勻格網(wǎng)索引信息結(jié)構(gòu)。在對(duì)待處理數(shù)據(jù)中需進(jìn)行拓?fù)湟恢滦蕴幚淼母鞣N情況進(jìn)行搜索查詢時(shí)，由于均勻格網(wǎng)索引結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎ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記錄該圖層中的對(duì)象索引值，nPntIndex記錄該對(duì)象中的節(jié)點(diǎn)索引值(當(dāng)針對(duì)弧段建立索引時(shí)，即記錄弧段的起始節(jié)點(diǎn)索引值)，nPntPos記錄該節(jié)點(diǎn)的索引節(jié)點(diǎn)數(shù)組Pnts中的位置，數(shù)組長(zhǎng)度為nPntCount；pSegmentUnit是一個(gè)TSegmentInfo類型的指針數(shù)組，該指針指向網(wǎng)格索引單元中具體索引的空間數(shù)據(jù)信息。經(jīng)過(guò)均勻格網(wǎng)索引建立過(guò)程后，空間數(shù)據(jù)中的節(jié)點(diǎn)都存儲(chǔ)在索引節(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ì)了一種較為簡(jiǎn)潔統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)各圖層中數(shù)據(jù)對(duì)象需要進(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對(duì)應(yīng)一個(gè)待調(diào)整的空間對(duì)象，nIntersetPntIndex記錄該對(duì)象需要調(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層多對(duì)象的處理，因此算法中使用的結(jié)構(gòu)為：
Vector
parrTopoUnitNodes長(zhǎng)度為所需處理的圖層數(shù)目，每個(gè)圖層需要根據(jù)其對(duì)象數(shù)目nObjCount申請(qǐng)所需的內(nèi)存。
TopoUnitNodeInfo*pTopoUnitNodeInfo=new TopoUnitNodeInfo[nObjCount]
1.2 弧段間拓?fù)涮幚?/p>
弧段間拓?fù)涮幚磉^(guò)程主要是進(jìn)行弧段與弧段拓?fù)潢P(guān)系的判別，以及對(duì)不滿足弧段與弧段間拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)。當(dāng)兩弧段位置關(guān)系出現(xiàn)類似“十字”形的相交情況時(shí)，需在兩弧段的相交處各插入一個(gè)節(jié)點(diǎn)，即弧段間的相交情況只允許出現(xiàn)在弧段的起始或終止端點(diǎn)處。此過(guò)程基本對(duì)應(yīng)于Pullar算法中的弧段相交情況，但由于Pullar算法中弧段相交過(guò)程新增的節(jié)點(diǎn)有可能存在和其它弧段造成的二次修正情況，因此把該過(guò)程放在第一個(gè)流程進(jìn)行處理，使得新增節(jié)點(diǎn)可能導(dǎo)致的和其它弧段或者節(jié)點(diǎn)距離小于容限的情況在后續(xù)過(guò)程中依次進(jìn)行修正，避免了多次迭代修正的問(wèn)題。
整體處理過(guò)程可以劃分為檢測(cè)和修復(fù)兩大過(guò)程，在檢測(cè)過(guò)程中則對(duì)拓?fù)涮幚淼母鲌D層數(shù)據(jù)進(jìn)行遍歷查詢。通過(guò)建立均勻格網(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ù)涮幚磉^(guò)程中進(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ù)涮幚磉^(guò)程進(jìn)行處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對(duì)象，根據(jù)對(duì)象每條弧段位置建立網(wǎng)格索引，索引中記錄弧段所屬的數(shù)據(jù)集ID、對(duì)象ID、節(jié)點(diǎn)索引值等信息，并將所有弧段中節(jié)點(diǎn)統(tǒng)一存儲(chǔ)到一個(gè)節(jié)點(diǎn)數(shù)組中(相鄰兩弧段共用的起始終止節(jié)點(diǎn)只需存儲(chǔ)一次)。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)對(duì)象某一弧段需添加多個(gè)節(jié)點(diǎn)時(shí)，對(duì)新添加的節(jié)點(diǎn)排序，根據(jù)排序后的順序添加交點(diǎn)。
圖2 弧段間拓?fù)涮幚硖厥馇闆r
Fig.2Specialcasesofarcstopologyconsistencyprocess
1.3 節(jié)點(diǎn)與弧段間拓?fù)涮幚?/p>
在節(jié)點(diǎn)與弧段間拓?fù)涮幚磉^(guò)程中主要是判別節(jié)點(diǎn)與弧段的拓?fù)潢P(guān)系，以及對(duì)于不滿足節(jié)點(diǎn)與弧段拓?fù)潢P(guān)系的數(shù)據(jù)進(jìn)行修正和維護(hù)，即當(dāng)節(jié)點(diǎn)距某弧段距離小于容限時(shí)，需在弧段上添加此節(jié)點(diǎn)的垂足。此過(guò)程基本對(duì)應(yīng)于Pullar算法中的弧段插點(diǎn)過(guò)程，但由于Pullar算法流程中弧段插點(diǎn)過(guò)程理論上存在和其它弧段造成的二次修正情況，因此把該過(guò)程放在第二流程進(jìn)行處理，修正過(guò)程由第三過(guò)程完成。
整體處理過(guò)程同樣可以劃分為檢測(cè)和修復(fù)兩大過(guò)程，在檢測(cè)過(guò)程中遍歷數(shù)據(jù)，通過(guò)建立均勻格網(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í)，則無(wú)論節(jié)點(diǎn)與弧段的距離為多少都不進(jìn)行插入，而當(dāng)出現(xiàn)節(jié)點(diǎn)到弧段端點(diǎn)距離大于容限，但節(jié)點(diǎn)的垂足到弧段端點(diǎn)距離小于容限的情況時(shí)，則此垂足點(diǎn)也需插入到弧段中，此情況會(huì)在后續(xù)的節(jié)點(diǎn)間鄰近搜索過(guò)程中進(jìn)行處理。
如圖3所示，以弧段v1v2為例進(jìn)行節(jié)點(diǎn)與弧段拓?fù)涮幚淼恼f(shuō)明，當(dāng)節(jié)點(diǎn)v距弧段左右兩端點(diǎn)v1或v2的距離小于容限，即位于圖3中左右端A區(qū)域時(shí)，無(wú)需進(jìn)行處理，此情況會(huì)在后續(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)間鄰近搜索會(huì)處理此特殊情況。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)集圖層，取出每個(gè)對(duì)象，將其節(jié)點(diǎn)和線段建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲(chǔ)到一個(gè)節(jié)點(diǎn)數(shù)組中。使用兩個(gè)網(wǎng)格索引結(jié)構(gòu)分別存儲(chǔ)所有的節(jié)點(diǎn)信息和所有的弧段信息。需注意：節(jié)點(diǎn)索引中只需記錄節(jié)點(diǎn)的坐標(biāo)信息，無(wú)需記錄其所屬的數(shù)據(jù)圖層、對(duì)象、點(diǎn)串索引等信息?；《未嫒牖《尉W(wǎng)格索引結(jié)構(gòu)中，索引結(jié)構(gòu)中需要同步記錄該弧段所屬的數(shù)據(jù)圖層、對(duì)象、點(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)過(guò)弧段間拓?fù)涮幚砗凸?jié)點(diǎn)與弧段間拓?fù)涮幚韮蓚€(gè)過(guò)程后，已對(duì)數(shù)據(jù)中的弧段相交情況進(jìn)行了節(jié)點(diǎn)插入，并將數(shù)據(jù)中存在的節(jié)點(diǎn)與弧段距離小于容限的情況通過(guò)插入垂足節(jié)點(diǎn)的方式轉(zhuǎn)化為距離在容限范圍內(nèi)的節(jié)點(diǎn)問(wèn)題，此時(shí)需要通過(guò)節(jié)點(diǎn)間鄰近搜索過(guò)程對(duì)這些距離在容限范圍內(nèi)的節(jié)點(diǎn)情況進(jìn)行搜索和處理。不同于Pullar算法中的聚類過(guò)程，本文采用節(jié)點(diǎn)間鄰近搜索的策略將這些通過(guò)容限相關(guān)的節(jié)點(diǎn)搜索出來(lái)，而后統(tǒng)一調(diào)整為同一坐標(biāo)。
如圖4所示，通過(guò)節(jié)點(diǎn)v1進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v1在容限范圍內(nèi)的節(jié)點(diǎn)v2搜索出來(lái)，而繼續(xù)通過(guò)v2進(jìn)行鄰近點(diǎn)搜索時(shí)可將距離v2在容限范圍內(nèi)的節(jié)點(diǎn)v3搜索出來(lái)，直到通過(guò)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)位置記錄下來(lái)并反饋給用戶進(jìn)行手動(dòng)編輯處理。整體處理流程如下：1) 依次遍歷矢量數(shù)據(jù)圖層，取出每個(gè)對(duì)象，對(duì)其節(jié)點(diǎn)建立網(wǎng)格索引，并將所有節(jié)點(diǎn)存儲(chǔ)到一個(gè)節(jié)點(diǎn)數(shù)組中。索引結(jié)構(gòu)中需要同步記錄該節(jié)點(diǎn)所屬的數(shù)據(jù)圖層、對(duì)象、點(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語(yǔ)言實(shí)現(xiàn)了上文描述的拓?fù)湟恢滦蕴幚砀倪M(jìn)算法，并與ArcGIS桌面軟件拓?fù)湟恢滦蕴幚淼南嚓P(guān)功能進(jìn)行測(cè)試比較。實(shí)驗(yàn)環(huán)境為一臺(tái)主頻2.6GHz的雙核處理器PC機(jī)，內(nèi)存為2GB。由于疊加分析操作是對(duì)矢量數(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ù)疊加分析處理，而后對(duì)兩種處理結(jié)果進(jìn)行比較分析。為了保證測(cè)試驗(yàn)證的有效性，針對(duì)該數(shù)據(jù)分別使用“相交”和“對(duì)稱差”兩種疊加模式，且每種模式下都使用大小不等的兩種處理容限進(jìn)行測(cè)試。如表1所示，ArcGIS的拓?fù)湟恢滦蕴幚砗童B加分析操作在同樣的疊加模式下對(duì)于容限的改變較不敏感，而改進(jìn)算法中結(jié)果對(duì)于容限的改變較為敏感。在4組實(shí)驗(yàn)中，結(jié)果數(shù)據(jù)集總面積一項(xiàng)中表現(xiàn)出和ArcGIS較好的一致性，ArcGIS處理結(jié)果和改進(jìn)算法處理結(jié)果總面積偏差都在十萬(wàn)分之一以下，且有一組測(cè)試數(shù)據(jù)的總面積偏差在百萬(wàn)分之一以下，即經(jīng)過(guò)拓?fù)湟恢滦愿倪M(jìn)算法處理后的數(shù)據(jù)在疊加分析操作過(guò)程中表現(xiàn)出較好的數(shù)據(jù)質(zhì)量和處理效果。
表1 改進(jìn)算法和ArcGIS對(duì)比測(cè)試結(jié)果
Table 1 The result comparison of improved algorithm and ArcGIS
序號(hào)疊加方式疊加容限ArcGIS總面積(m2)改進(jìn)算法總面積(m2)面積偏差(m2)1相交5．25461348429912294．371348429614234．562．21042E-072相交0．00011348429912294．371348424580959．503．95374E-063對(duì)稱差5．25468183976303662．088183956850405．882．37699E-064對(duì)稱差0．00018183976303662．088183961789600．571．77347E-06
在保證拓?fù)湟恢滦蕴幚硇Ч幕A(chǔ)上，針對(duì)該改進(jìn)算法的性能與ArcGIS進(jìn)行進(jìn)一步的對(duì)比測(cè)試，為了保證測(cè)試的有效性，分別針對(duì)常用的線數(shù)據(jù)類型和面數(shù)據(jù)類型，選用了多組規(guī)模不等的空間數(shù)據(jù)進(jìn)行對(duì)比測(cè)試(表2)。由表2可知，無(wú)論是在線數(shù)據(jù)類型還是在面數(shù)據(jù)類型對(duì)比測(cè)試中，在多種數(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ù)類型性能對(duì)比測(cè)試結(jié)果
Table 2 The comparison of line and polygon dataset performance
序號(hào)線數(shù)據(jù)類型面數(shù)據(jù)類型對(duì)象數(shù)目ArcGIS(s)改進(jìn)算法(s)性能提升(%)對(duì)象數(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ù)集性能對(duì)比測(cè)試 圖6 面數(shù)據(jù)類型性能對(duì)比測(cè)試
Fig.5 Comparison of the line dataset performance Fig.6 Comparison of the polygon dataset performance
3 結(jié)語(yǔ)
在GIS矢量數(shù)據(jù)相關(guān)的各種空間分析中，拓?fù)湟恢滦缘奶幚硇Чc處理性能對(duì)于后續(xù)包括疊加分析、緩沖區(qū)分析、空間查詢等各種空間分析效果有較大的影響。本文首先針對(duì)已有的較為典型的拓?fù)湟恢滦蕴幚硭惴ㄟM(jìn)行了闡述和分析，主要包括Milenkovic算法、Pullar算法、Harvey&Vauglin算法以及ArcGIS的處理方式，重點(diǎn)針對(duì)各算法的使用情況以及局限性進(jìn)行了分析。在此基礎(chǔ)上提出了一種性能較優(yōu)的改進(jìn)算法，主要包括弧段間拓?fù)涮幚?、?jié)點(diǎn)與弧段間拓?fù)涮幚怼⒐?jié)點(diǎn)間鄰近搜索3個(gè)核心過(guò)程，并重點(diǎn)針對(duì)處理過(guò)程中容限的設(shè)置與處理、算法的核心數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行了詳細(xì)闡述。通過(guò)3組實(shí)驗(yàn)對(duì)該改進(jìn)算法的處理效果和處理性能進(jìn)行了對(duì)比驗(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] 王少華,鐘耳順,盧浩,等.基于非均勻多級(jí)網(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);中國(guó)科學(xué)院重點(diǎn)部署項(xiàng)目(KZZD-EW-07-01-001);國(guó)家科技支撐計(jì)劃項(xiàng)目(2011BAH06B03);資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室自主研究項(xiàng)目(088RAC00YA);中國(guó)科學(xué)院國(guó)防科技創(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
猜你喜歡
電子設(shè)計(jì)工程(2022年24期)2022-12-23
現(xiàn)代工業(yè)經(jīng)濟(jì)和信息化(2022年9期)2022-11-03
應(yīng)用科學(xué)學(xué)報(bào)(2020年6期)2021-01-04
空間科學(xué)學(xué)報(bào)(2020年6期)2020-07-21
電加工與模具(2020年2期)2020-04-29
城市勘測(cè)(2019年4期)2019-09-05
攝影之友(影像視覺(jué))(2018年1期)2018-03-22
攝影之友(影像視覺(jué))(2017年8期)2017-11-27
影像研究與醫(yī)學(xué)應(yīng)用(2015年6期)2015-08-15
