土地?cái)?shù)據(jù)中空間重復(fù)、覆蓋和縫隙的快速檢查算法

一、引 　言

在土地空間數(shù)據(jù)處理及應(yīng)用中 ,需要對空間關(guān)系進(jìn)行檢查以保證數(shù)據(jù)質(zhì)量 ,如對于圖斑數(shù)據(jù)或全劃宗的地籍?dāng)?shù)據(jù) ,圖斑對象或宗地對象間應(yīng)該形成無覆蓋、無重復(fù)和無縫隙的滿覆蓋的面 ,需要通過GIS 中的空間關(guān)系查詢算法檢查出數(shù)據(jù)集內(nèi)所有發(fā)生覆蓋、重復(fù)和縫隙的對象 ,提交后續(xù)編輯處理。

目前 GIS 中對空間關(guān)系查詢算法的研究較為深入 ,各大 GIS 軟件平臺中都提供了較成熟的空間關(guān)系查詢算法?？臻g關(guān)系包括重復(fù)、包含、內(nèi)含、相交、相離、覆蓋、切觸等 , GIS 中通用的空間關(guān)系查詢算法是根據(jù)數(shù)據(jù)集的空間索引搜索出當(dāng)前空間對象所在的索引區(qū) ,然后判斷其與相鄰的空間對象的空間關(guān)系類型。大多數(shù) GIS 軟件都采用這種方式實(shí)現(xiàn)空間查詢 ,它依賴于不同的索引方式和具體算法。應(yīng)用這種方式對土地?cái)?shù)據(jù)進(jìn)行檢查 ,無法一次檢查出數(shù)據(jù)集內(nèi)存在的覆蓋、重復(fù)和縫隙錯誤 ,而且當(dāng)檢查對象及對象間關(guān)系的復(fù)雜性增加 ,查詢時(shí)間會大幅度地增長。如圖斑對象形狀復(fù)雜 ,通常有很多個(gè)節(jié)點(diǎn) ,且一個(gè)圖斑與很多個(gè)圖斑相鄰 ,對圖斑進(jìn)行空間關(guān)系的查詢要比宗地耗費(fèi)的時(shí)間多。

為了解決此類問題 ,本文提出了一種空間關(guān)系檢查的快速算法 ,該算法主要針對單個(gè)面數(shù)據(jù)集 ,檢查出該數(shù)據(jù)集內(nèi)出現(xiàn)空間覆蓋、重復(fù)和縫隙的對象 ,算法只需要對面數(shù)據(jù)集內(nèi)的空間對象循環(huán)一遍 ,即可檢查出空間覆蓋、重復(fù)和縫隙這幾類空間關(guān)系錯誤。

經(jīng)過實(shí)踐驗(yàn)證 ,采用該算法能極大地提高對面數(shù)據(jù)集進(jìn)行以上類型空間關(guān)系錯誤檢查的效率。

二、空間關(guān)系快速檢查方法的思想

這種空間關(guān)系快速檢查方法主要是檢查面數(shù)據(jù)集內(nèi)出現(xiàn)空間覆蓋、重復(fù)和縫隙等空間關(guān)系的對象。在對面數(shù)據(jù)集進(jìn)行檢查時(shí) ,需要一個(gè)與該面數(shù)據(jù)集空間范圍一致或者能完全覆蓋該面數(shù)據(jù)集的背景圖形 (下文將稱之為背景圖形) ,如檢查圖斑數(shù)據(jù)集 ,可以獲取該圖斑數(shù)據(jù)集的最大空間范圍生成一個(gè)面圖形作為背景圖形 ,然后通過該對象與圖斑數(shù)據(jù)集內(nèi)的每一個(gè)圖斑對象進(jìn)行運(yùn)算 ,得到出現(xiàn)空間覆蓋和縫隙的圖斑對象。

該算法的總體思想是循環(huán)取得待檢查數(shù)據(jù)集中的空間對象 ,依次從背景圖形中通過空間擦除操作擦除待檢查數(shù)據(jù)集中的對象 ,每一次擦除后得到一個(gè)剩余的背景圖形 ,計(jì)算該剩余圖形的面積值 M1 ;同時(shí)計(jì)算執(zhí)行該次擦除操作前的剩余背景圖形的面積與被擦除的對象的面積的差值 M2 ,將 M1 和 M2 兩個(gè)面積值進(jìn)行比較 ,以判斷該被擦除的對象是否與其他圖形重疊 ;當(dāng)從背景圖形中擦除完所有的對象后 ,剩余的圖形即為待檢查數(shù)據(jù)集內(nèi)空間對象間的縫隙 ,如果剩余圖形為空(面積為零) ,說明無縫隙。

下面舉例說明這個(gè)算法的思想。設(shè)有一個(gè)待檢查的面數(shù)據(jù)集和一個(gè)空間范圍完全覆蓋該數(shù)據(jù)集的背景圖形 ,背景圖形為 A , 待檢查數(shù)據(jù)集包含圖形P , Q ,如圖 1 (a) 為背景區(qū)域和待檢查數(shù)據(jù)集的疊加圖。令背景圖形 A 面積為 MA ,待檢查的面圖形 P , Q 面積分別為 M p , M q , 圖形 P , Q 發(fā)生了覆蓋 , 令覆蓋部分的面積為 M O 。

第一步 ,首先從背景圖形 A 中擦除第一個(gè)空間對象 P 得到一個(gè)剩余的背景圖形 ,圖 1 ( b) 為背景圖形 A 與待檢查對象 P 圖形作空間擦除操作后剩余的圖形 A′,該圖形的面積為 M A′= M A - M P ; 計(jì)算進(jìn)行空間擦除操作的兩個(gè)圖形的屬性面積差值 , 即背景圖形 A 與圖形 P 的屬性面積差值 , 為 M′′= MA - M P ,可以看出 M A′= M′′,即從背景圖形中空間擦除第一個(gè)圖形后 , 剩余背景圖形的空間圖形面積與通過屬性面積計(jì)算得到的兩個(gè)面積值相等。

第二步 ,從剩余的背景圖形中擦除第二個(gè)空間對象 ,圖 1(c) 為剩余的背景圖形 A′與待檢查對象 Q 作空間擦除后剩余的圖形 A″,該圖形的面積為 MA″= MA- MP - MQ + MO ,其中 MO 為對象 P, Q 發(fā)生覆蓋部分的面積 ,由于從背景圖形中減去對象 P 和 Q 的面積 ,將覆蓋部分面積減去了 2 次 ,故計(jì)算剩余背景圖形面積時(shí)應(yīng)該加上 MO ;然后計(jì)算進(jìn)行本次空間擦除操作的兩個(gè)圖形的屬性面積差值 ,即剩余背景圖形 A′與圖形 Q 的面積差值 ,因?yàn)?M′″= ( MA - MP) - MQ ,可以看出 MA″> M′A″,說明剛被擦除的圖形 Q 與其他圖形發(fā)生了覆蓋。這是因?yàn)橥ㄟ^空間擦除方式得到的圖形面積 MA″是從背景圖形中減去發(fā)生重疊的 P, Q 圖形的并集 ,而通過從背景圖形中依次減去 P, Q 圖形面積所得到的面積差值 M′″則多減去了發(fā)生覆蓋部分的面積 MO ,因此前者得到的面積值大于后者。而如果 MA″= M′A″,則說明剛剛被擦除的空間圖形沒有與其他圖形發(fā)生覆蓋。

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