基于拓撲與緩沖查詢快速提取AutoCAD數(shù)據(jù)信息

韋 勝 葉興平

(江蘇省城市規(guī)劃設計研究院,南京 210036)

當前,我國有很大一部分的地形圖數(shù)據(jù)是以AutoCAD格式存儲的,對于其信息提取主要有兩種方式:第一種是先對其格式轉(zhuǎn)換再進行相關軟件的處理,如陳能等[1]在研究AutoCAD數(shù)據(jù)向GIS數(shù)據(jù)入庫時,提出了基于地理編碼和規(guī)則庫的方案,但這種方式需要用戶熟悉其它軟件、增加了用戶的操作復雜度且缺乏拓撲規(guī)則處理;第二種是基于AutoCAD數(shù)據(jù)自身結(jié)構(gòu)特點的處理辦法,如馬文祥等[2]在研究AutoCAD地形圖中離散高程點提取時,提出了基于最鄰近關系的提取方法.另外,ArcGIS軟件也在空間關聯(lián)性處理(spacial join)上提供了基于要素的合并(union)、相交(intersect)等方式,但需要轉(zhuǎn)換數(shù)據(jù)格式且不能解決一些特殊環(huán)境下的數(shù)據(jù)問題.

通過研究發(fā)現(xiàn),AutoCAD數(shù)據(jù)與GIS數(shù)據(jù)相比較,缺乏拓撲關系及詳細的屬性信息.如果對Auto-CAD數(shù)據(jù)實體建立一定的拓撲關系,并以此提取信息,將會減少數(shù)據(jù)空間關系上的錯誤.為了提高利用效率,本文給出了一般性的基于拓撲關系的信息提取程序接口.由于在大數(shù)據(jù)量下處理速度將會緩慢,為此本文提出在緩沖查詢基礎上進行相關信息提取.同時,在AutoCAD二次開發(fā)基礎上進行信息提取,減少了人為處理的不必要的錯誤,也增強了大數(shù)據(jù)量處理的效率及更強的適應性.最后,總結(jié)了提取步驟并以離散高程點的提取作為實例驗證了該思路的正確性和有效性.

1 拓撲處理

本文中的拓撲處理主要是指對AutoCAD中實體建立拓撲關系,并按需求給出信息提取的方法,其需要確定兩個方面內(nèi)容:實體的類型及其集合、實體間拓撲關系.其中拓撲關系包括面面相交、線線重疊等.由于在AutoCAD中實體間拓撲關系沒有明確給出,為此先要確定拓撲關系,再進行具體信息提取.

1.1 拓撲關系

AutoCAD由于缺乏豐富的拓撲功能,各實體間缺乏有效的拓撲檢查及數(shù)據(jù)約束,為此需要用戶依據(jù)不同的實體類型等去建立拓撲關系.本文僅以面面間3個(相交、重疊、島)重要的拓撲關系的提取為例來說明,這里的面指AutoCAD里的閉合多段線.

如果要判斷面面之間的上述3個拓撲關系,需要將不同的兩個面(閉合多段線)轉(zhuǎn)化為面域,再通過面域之間的拓撲計算進行判斷.如果計算后得到的面域面積等于0,則認為兩面相離;如果計算后得到的面域面積小于最小面的面積,則認為兩面為相交的關系;如果計算后得到的面域面積等于最小面的面積,則還需要判斷這兩個面的面積是否相等,如果兩個面的面積相等則認為兩面重疊,如果兩面面積不相等則認為兩面為島的關系;如圖1所示.

圖1 面面間拓撲關系示意圖

1.2 基于拓撲的處理

基于拓撲的處理主要依據(jù)AutoCAD數(shù)據(jù)本身特點、應用情況及空間拓撲關系來建立實體間拓撲規(guī)則.拓撲規(guī)則的建立要依據(jù)以下幾個原則:

第1,實體的類型及其集合.在GIS中,將現(xiàn)實世界的實體主要分為點、線、面3種類型,而在Auto-CAD制圖環(huán)境下,操作人員可以對這3種類型實體,在不同尺度下以不同的圖元類型表示,如水井既可用單點來表示,也可用一定大小的圓來表示[3].不同類型實體對應的拓撲規(guī)則可能不同,如面面相交、線割面,所以要依據(jù)實體類型建立相應的拓撲規(guī)則.對于一定數(shù)量的同類型實體以集合(Collection)的形式存儲表示.集合操作具有很多優(yōu)點,便于對實體遍歷、刪除、增加等操作.集合管理方式也實現(xiàn)了對不同實體功能、結(jié)構(gòu)的封裝抽象.

第2,拓撲關系本身特點.拓撲關系可以依據(jù)OGC(Open GIS Consortium)制定的地理信息系統(tǒng)空間標準.空間拓撲關系謂詞包括:Crosses、Disjoint、Within、Contains、Equals、Touches、Intersects、Overlaps等8種.另外,還有實體的方向關系等.對于系統(tǒng)用戶而言,對不同實體的不同空間拓撲關系進行記錄,并對每種記錄做唯一的標識,表1給出了部分拓撲關系的示例.這樣在一個統(tǒng)一的系統(tǒng)環(huán)境下,用戶根據(jù)這些不同的拓撲關系編寫不同的實現(xiàn)功能代碼,提高代碼的可利用性.

表1 部分拓撲關系示例

第3,實體最小外接矩形.為了對各種不同類型的實體在空間拓撲關系上進行拓撲分析,如兩實體間的位置方向分析,需要確定各種實體的最小包絡矩形以簡化不規(guī)則實體間復雜的空間關系處理.如圖2所示,實體A與實體B相交,實體A與實體C、實體B與實體C均是分離的關系.A、B、C之間的這些關系可以利用這些外接矩形來做一些簡化處理,如果兩個實體的最小外接矩形相離,則認為這兩個實體相離.實體的最小外接矩形的最大點是矩形的右上角點,最小點是矩形的左下角點.另外,實體的最小外接矩形也是對實體在二維空間地理空間定位最有利的條件依據(jù),只要查詢到最小外接矩形便可以依據(jù)坐標關系迅速地尋找到實體的所在地,這也是信息提取的一個重要處理辦法.

圖2 實體最小外接矩形示例

2 提取的一般接口形式

在一些實際情況下,依據(jù)實體類型、實體間距離等將一些實體間的空間關系作相應的轉(zhuǎn)換處理.如點點之間可以有“包含”(Contains)關系,其中Contains指的是以兩個點中的其中一個點建立一定范圍內(nèi)的緩沖區(qū),并以此緩沖區(qū)判斷是否包含另外一個點,如果包含則做“T rue”標記,如果不包含則做“False”標記.點點之間還可以根據(jù)點的最小外接矩形做出點點間方位的判斷.

根據(jù)上述原則,可以在連續(xù)的AutoCAD二維空間Ω內(nèi)的實體集ES(E)={{E1},{E2},…,{En}}、拓撲關系集TS(T)={T1,T2,…,Tn}及用戶參數(shù)集PS(P)={P1,P2,…,Pn}上建立信息提取的一般接口形式:

其中,{E1},{E2},…,{En}代表各種類型實體的集合,如{E1}代表點實體集、{E2}代表文字實體集合; T1,T2,…,Tn代表各拓撲關系,如 T1代表包含關系,T2代表方向關系;P1,P2,…,Pn代表用戶輸入的各種參數(shù),如P1代表上述包含關系中的緩沖查詢距離;F為拓撲處理方法.在實際程序中,可以將T I轉(zhuǎn)換為具體接口形式,這樣ES,TS,PS分別為接口的不同屬性,F為接口的處理方法.另外,需說明的是這里所說的接口是對信息提取方法的一般抽象.

如果用戶要提取AutoCAD中的相交、重疊及島關系的面(閉合多段線)集合,可以建立如下的接口TI1={EP1,{Tintersect,Toverlap,Tisland},F};其中,EP1為用戶傳入的面(多段線)集合,Tintersect、Toverlap、Tisland分別為面之間的拓撲相交、重疊、島的標識.如果用戶要刪除指定圓集合中重復的部分可以建立如下的接口,T I2={EP2,Trepeat,d,F};其中,EP2為用戶傳入的圓集合,Trepeat為圓重復拓撲關系的標識,d為系統(tǒng)確認兩個圓重復與否的最小距離容差值.T I1、T I2均繼承TI.

3 緩沖查詢

在連續(xù)的AutoCAD二維空間Ω內(nèi),有類型為A的實體集合ES(A)={A1,A2,…,Am},類型為B的實體集合ES(B)={B1,B2,…,Bn},ES(A)與ES (B)可能存在某種拓撲關系T,假設兩不同類型實體做一次拓撲關系 T的檢查確認的平均時間為t.如果需要檢查ES(A)與ES(B)之間所有的拓撲關系,那么查詢消耗將隨著m、n的增大而迅速增加,特別是在大數(shù)據(jù)量的情況下.以下從兩種不同的方法去考慮查詢優(yōu)化問題.

3.1 二次遍歷查詢

如果以二次遍歷查詢作為不同實體間拓撲關系的查詢方式,那么在一般情況下將會有m×n×t的時間消耗.再利用實體最小外接矩形的簡單坐標過濾作用,如果每次過濾的所需時間t1小于t,那么總的時間消耗會在數(shù)積m×n×t的參數(shù)t上有所減小.但這并沒有改變m、n的數(shù)量很大的情況下的時間消耗,也缺乏人為空間查詢范圍等的參數(shù)化控制功能.

3.2 緩沖查詢

為了改變每個實體A都需要去與每個實體B做一定的比較,可以考慮讓以每個實體A只與一定范圍內(nèi)的實體B做比較,這不僅解決了二次遍歷的數(shù)據(jù)量龐大的問題,也提供了用戶參數(shù)化的控制功能.緩沖查詢便是利用這樣的原理,即通過對實體做一定范圍的搜索查詢,這個范圍可以是與實體相關的一定矩形、圓形等.由于現(xiàn)在的商業(yè)軟件在空間查詢方面都具有很高的執(zhí)行效率(利用空間索引),因此這種緩沖查詢的效率是有所保證的[4].此外,緩沖查詢具有實際的可操作性,很多實際應用問題也證實了這種方法的可行性.

如圖3所示,對實體A以一定范圍內(nèi)的矩形作為緩沖查詢,則只需對其緩沖范圍內(nèi)的實體進行拓撲檢查,對于圖3中左邊圖的情況,只需進行3次檢查.另外,用戶也可以通過改變矩形范圍的大小來達到不同的實際目的.圖3中右邊圖的情況,用戶在不同的矩形緩沖范圍內(nèi)會得到不同的查詢結(jié)果,這樣對于不同的地形圖就可以按照圖面的實際距離情況進行緩沖查詢操作.

圖3 基于矩形的實體緩沖查詢示意圖

緩沖查詢方式在某些特殊情況下具有非常高的執(zhí)行效率.假設在連續(xù)的AutoCAD二維空間 Ω內(nèi),有數(shù)量為p(p可以趨向無窮大)的不規(guī)則實體,其中很多實體是由于用戶操作不當導致的重復實體,有的重復數(shù)還較大,還有些實體出現(xiàn)了很小空間范圍內(nèi)的重疊.如果使用二次遍歷的處理方式,那么在這些重復實體、重疊實體的查詢處理上就會造成大量的時間浪費[5].而如果采用實體緩沖查詢方式.如圖4所示,實體C與實體A出現(xiàn)重疊,另外實體A還有重復的實體,而在用戶的實際需求中,只需要保留下實體A.經(jīng)分析,采取以實體A的最小外接矩形做緩沖區(qū)分析,如果這個緩沖區(qū)內(nèi)包含與A一樣的類型實體,則將其刪除.這種處理方式,避免了實體A與實體C的及其重復實體的反復比較處理,只需進行一次遍歷的緩沖查詢便將不需要的實體提取出并刪除[6].

圖4 利用最小外接矩形做緩沖查詢示意圖

3.3 查詢比較

本文以對9037個圓圖元的重復圖元刪除為實驗題材,分別以基于緩沖查詢的一次遍歷與二次遍歷為查詢處理方法.比較發(fā)現(xiàn):這個試驗中,基于緩沖查詢的一次遍歷的執(zhí)行效率是二次遍歷的9倍,結(jié)果見表2.

表2 查詢比較

4 信息提取步驟

提取AutoCAD信息需要確定3個因素:不同實體集、拓撲關系及用戶參數(shù).為了提高空間查詢的效率,需要利用緩沖查詢來減少遍歷次數(shù).為此,信息提取步驟分為以下4個環(huán)節(jié).

第1,實體集與拓撲關系的確定.不同類型的實體具有不同的性質(zhì),為此需要將不同實體劃分開來,并組成個數(shù)大于等于1的實體集合.一般情況下,為了簡化問題的處理,只需要確定兩類不同類型的實體集合ES(K)與ES(L),即實體集E(Q)={{ES (K)},{ES(L)}}.

確定實體集合后,找出這兩種不同類型實體間需要確定或處理的拓撲關系.比如確定的某種拓撲關系T(M).如果是基于兩種不同拓撲關系處理,則需要確定另外的某個拓撲關系T(N).多種拓撲關系依次類推.

第2,用戶參數(shù)確定.實際工作中,用戶需要具有一定的控制處理功能,為此,通過一些參數(shù)傳遞達到這個目的,如實體間距離參數(shù)d.需注意的是,參數(shù)是根據(jù)具體問題具體分析而得來.

第3,緩沖查詢處理.如果需要通過查詢來實現(xiàn)較高的執(zhí)行效率,可以以某類型實體的一定距離范圍或給定具體坐標范圍來進行緩沖查詢.緩沖查詢應該是具有反復修改查詢范圍的功能來達到用戶的控制使用效果.

第4,根據(jù)信息提取具體的結(jié)果,經(jīng)反復測試,在程序中建立信息提取的功能接口I(P)={E(Q),{T (M),T(N)},d,F}.其中F為拓撲處理的具體方法.

5 應用實例

為了驗證本文所提出的方法的正確性,以某地區(qū)的原始AutoCAD地形圖提取高程點信息做為實驗驗證.在地形圖中,高程點以圓圖元表示,高程值以單行文本圖元表示,高程點數(shù)為9037個(包括大量的重復點),高程文本圖元數(shù)為4503個.高程點集合與高程數(shù)值集合分別記為數(shù)據(jù)集E(M)、E(N).經(jīng)分析高程點與高程文本圖元的一般間隔距離d大概為12個圖面單位距離,可以采用空間關系中最鄰近距離實現(xiàn)匹配,其中d可以作為用戶的輸入?yún)?shù).然而,在高程點較密集的地方,出現(xiàn)如圖5中情況,最鄰近距離匹配的影響可能沒有高程注記字位的影響因子大,即黑色填充的圓點盡管與數(shù)值為1 200.2的文本距離較近,但實際中,與其匹配的高程值應該是數(shù)值為1452.2的文本.這說明高程注記文本的字位在匹配中也是一個關鍵的考慮因素.此外,重復的高程點需要刪除.所以,采取了基于兩種空間關系處理方法,即最鄰近距離T(N)與高程注記字位在高程點右下角優(yōu)先T(S).

圖5 注記字位的影響

為此,可建立程序接口I={{E(M),E(N)},{T (N),T(S)},d,F}.其偽代碼形式如下:

在具體功能類的實現(xiàn)時,先以高程點最小外接矩形范圍作緩沖查詢刪除重復高程點,再以高程點集合作為遍歷條件,以12個圖面單位作為每個高程點的緩沖查詢范圍,以注記字位為位于高程點右下角優(yōu)先及最鄰近距離拓撲關系的原則匹配出高程點的(X, Y,Z).其中,緩沖查詢使用的是AutoCAD提供的功能接口函數(shù)SelectCrossingWindow[7].

最后,隨機提取100個高程點(包含一些高程點密集的地方),發(fā)現(xiàn)正確率在97%.而只使用最鄰近距離匹配方法時,正確率只有87%.利用這些高程點制作的地形模擬圖如圖6所示.軟件操作界面如圖7所示.

6 結(jié) 語

一般的AutoCAD地形圖數(shù)據(jù)缺乏拓撲關系,用戶在數(shù)據(jù)提取時往往忽視了數(shù)據(jù)本身一些潛在的空間關系,導致直接使用某些專業(yè)軟件產(chǎn)生了較大的錯誤率.本文研究了基于空間拓撲關系與緩沖查詢的AutoCAD二次開發(fā)提取數(shù)據(jù)信息的方法,并給出了完整的操作流程,強調(diào)了應根據(jù)實際情況利用不同拓撲關系去提取信息.其中緩沖查詢提高了大數(shù)據(jù)量環(huán)境下的查詢效率,也為用戶操作提供了更好的互操作方式.實驗結(jié)果表明,這種方式提取信息具有很好的實際效果,可解決AutoCAD環(huán)境下地形圖數(shù)據(jù)一些特殊的問題,如最鄰近距離無法很準確的提取出高程點信息.本文只是提出了一般意義上的AutoCAD地形數(shù)據(jù)提取方法,還要根據(jù)實際情況建立更多的處理接口去實現(xiàn)用戶不同需求.接口數(shù)量的增加及空間關系的復雜性增強,將會帶來接口分離、繼承等問題的出現(xiàn),這也是本文后續(xù)研究的重點.

[1] 陳 能,施蓓琦.AutoCAD地形圖數(shù)據(jù)轉(zhuǎn)換為GIS空間數(shù)據(jù)的技術研究與應用[J].測繪通報,2005(8):11-14.

[2] 馬文祥,金芳麗.在AutoCAD中實現(xiàn)高程信息的快速提取[J].測繪通報,2006(3):54-55.

[3] 解云琳,彭明軍.用MapInfo快速提取高程點信息[J].測繪通報,2003(1):48-50.

[4] 秦洪現(xiàn),崔惠嵐,孫 劍.Autodesk系列產(chǎn)品開發(fā)培訓教程[M].北京:化學工業(yè)出版社,2008.

[5] 曾憲硅,徐昌榮.數(shù)字地形圖清理研究[J].測繪通報, 2002(2):31-33.

[6] 余承飛,方 勇.AutoCAD2000二次開發(fā)技術(Object-ARX)[M].北京:人民郵電出版社,1999.

[7] 龔家玉,黃德詠.AutoCAD與其他常用軟件的數(shù)據(jù)轉(zhuǎn)換[J].四川測繪,2004,27(1):32-35.