張青年

(中山大學(xué)地理科學(xué)與規(guī)劃學(xué)院，廣東 廣州 510275)

在地圖編輯和空間數(shù)據(jù)更新等工作中，需要對(duì)多個(gè)來源的空間數(shù)據(jù)進(jìn)行融合處理。但由于不同來源的空間數(shù)據(jù)采用的數(shù)據(jù)分類體系、位置精度和數(shù)據(jù)現(xiàn)勢(shì)性存在差異，同一地物在不同來源的地圖上的位置和形狀并不相同［1－4］。例如，我國地形圖與海圖不一致的問題普遍存在，海岸線在地形圖和海圖上的形狀和性質(zhì)都有差異［5］，一般應(yīng)將地形圖上的海岸線調(diào)整到海圖上的參考海岸線圖形位置［6］。

對(duì)象捕捉是一種基本的地圖編輯功能［7］，用戶利用該功能可以迅速、準(zhǔn)確地將輸入圖形捕捉到線的結(jié)點(diǎn)、直線的交點(diǎn)和圓的圓心等參考圖形上的某些特殊點(diǎn)，從而能精確地繪制圖形。顯然，利用對(duì)象捕捉可以實(shí)現(xiàn)圖形數(shù)據(jù)整合處理。通過批量捕捉處理，將輸入圖形捕捉到容限距離內(nèi)的參考圖形位置，從而消除輸入圖形與參考圖形之間的不一致。現(xiàn)有捕捉處理方法有兩種捕捉方式，都是通過移動(dòng)圖形的結(jié)點(diǎn)來實(shí)現(xiàn)的。第一種捕捉方式僅移動(dòng)輸入圖形的結(jié)點(diǎn)到參考圖形位置，而參考圖形的形狀和位置保持不變。第二種捕捉方式則同時(shí)移動(dòng)輸入圖形和參考圖形，使兩者在新的中間位置上重合，是一種廣義的結(jié)點(diǎn)捕捉方式［8－9］。

由于不同來源的圖形數(shù)據(jù)在位置精度和現(xiàn)勢(shì)性等方面存在差異，通常不宜采用廣義結(jié)點(diǎn)捕捉方式進(jìn)行圖形數(shù)據(jù)融合。在大多數(shù)情況下，需要以選定的參考圖形為準(zhǔn)，將輸入圖形改正到參考圖形位置。例如，在土地利用變更調(diào)查等工作中，應(yīng)該以上一年度的土地利用現(xiàn)狀圖為參考圖，修改本年度的土地利用變更圖斑邊線，消除前后兩個(gè)年度的圖斑邊線在容限距離內(nèi)的不一致，以避免產(chǎn)生細(xì)小狹長(zhǎng)的變更過程圖斑。目前，一些GIS軟件可自動(dòng)將輸入圖層上的結(jié)點(diǎn)捕捉到參考圖層上的圖形，但并不能實(shí)現(xiàn)輸入邊與容限距離內(nèi)的參考邊完全一致。

1 結(jié)點(diǎn)捕捉存在的問題

在CAD和GIS等圖形處理軟件中，對(duì)象捕捉都是針對(duì)結(jié)點(diǎn)進(jìn)行處理的，其基本功能是將正在繪制的圖形結(jié)點(diǎn)抓取到已有參考圖形上的某個(gè)特殊點(diǎn)。如果對(duì)大量結(jié)點(diǎn)進(jìn)行批量捕捉處理，則發(fā)展成為一種圖形數(shù)據(jù)融合方法。例如，ArcGIS軟件的ArcToolBox模塊中提供了捕捉工具，它將輸入圖層中的邊線捕捉到參考圖層中的邊線上。實(shí)際上，它將輸入邊上所有在容限距離內(nèi)的結(jié)點(diǎn)捕捉到參考邊線上的垂足點(diǎn)或參考邊線結(jié)點(diǎn)。

CAD和GIS等圖形處理軟件基于結(jié)點(diǎn)層次進(jìn)行圖形捕捉，并不能將輸入邊捕捉到與容限距離內(nèi)的參考邊完全重合的位置。如圖1所示，輸入邊在參考邊兩側(cè)小幅度擺動(dòng)，其間距小于容限值。利用ArcGIS軟件進(jìn)行捕捉處理，將捕捉類型設(shè)置為Vertex，捕捉后的輸入邊有2處與參考邊不重合。如果將捕捉類型改為Edge，則捕捉后的結(jié)點(diǎn)與參考邊結(jié)點(diǎn)不重合。總之，捕捉處理過程中只移動(dòng)了輸入邊的結(jié)點(diǎn)，沒有有效地調(diào)整輸入邊的形狀，因此不能與參考邊完全重合。

圖1 將輸入邊的結(jié)點(diǎn)捕捉到參考邊Fig.1 Snap input edge to the location of reference edge

顯然，必須在輸入邊上插入附加結(jié)點(diǎn)，通過捕捉移動(dòng)附加結(jié)點(diǎn)來改變輸入邊的局部形狀，才能使輸入邊與容限距離內(nèi)的參考邊完全重合。如圖2所示，輸入邊到參考邊的結(jié)點(diǎn)q2的距離小于容限，但在不插入附加結(jié)點(diǎn)的情況下無法將輸入邊捕捉到q2位置。在輸入邊上按指定間距插入5個(gè)結(jié)點(diǎn)p3～p7，其中p5靠近q2，可以被捕捉到q2處。此外，通過插入附加結(jié)點(diǎn)，實(shí)際上對(duì)輸入邊進(jìn)行了分段，從而可對(duì)各段邊線分別進(jìn)行捕捉處理。例如，圖2中附加結(jié)點(diǎn)將輸入邊分為6段，其中結(jié)點(diǎn)p3～p7到參考邊的距離都小于容限，將被捕捉到參考邊上。于是輸入邊的p3－p7段被捕捉到參考邊，而p1－p3和p7－p2段不捕捉。

圖2 基于插入的附加結(jié)點(diǎn)進(jìn)行捕捉Fig.2 Snap an edge with added nodes

結(jié)點(diǎn)捕捉的另一個(gè)問題是捕捉后的邊線可能出現(xiàn)自相交錯(cuò)誤。如圖3所示，輸入邊的結(jié)點(diǎn)v2、v3、v4和v5到參考邊的距離小于容限而被捕捉到參考邊，捕捉之后v'2v'3與v'3v'4、v'3v'4與v'4v'5之間存在自相交問題。本文通過引入附加的結(jié)點(diǎn)順序調(diào)整步驟來解決線自相交問題。

圖3 輸入邊捕捉處理后的自相交問題Fig.3 The self-intersections on snapped edge

2 基于結(jié)點(diǎn)加密的捕捉算法

如前所述，結(jié)點(diǎn)層次的捕捉算法只能完成對(duì)原有結(jié)點(diǎn)的捕捉，并且結(jié)點(diǎn)捕捉之后存在自相交問題。本文針對(duì)結(jié)點(diǎn)捕捉算法的兩個(gè)局限，增設(shè)結(jié)點(diǎn)加密和結(jié)點(diǎn)順序調(diào)整兩個(gè)步驟，從而使結(jié)點(diǎn)和結(jié)點(diǎn)之間的線段都捕捉到與參考邊重合，即發(fā)展成一種邊線層次的捕捉算法。此外，針對(duì)現(xiàn)有算法將結(jié)點(diǎn)全部捕捉到垂足點(diǎn)或者全部捕捉到參考邊結(jié)點(diǎn)的僵化配置問題，本文算法依據(jù)具體條件靈活選取垂足點(diǎn)或參考邊結(jié)點(diǎn)作為目標(biāo)捕捉位置。即，輸入邊結(jié)點(diǎn)的容限距離內(nèi)有參考邊結(jié)點(diǎn)時(shí)以其為捕捉點(diǎn);否則以該結(jié)點(diǎn)在參考邊上的垂足點(diǎn)為捕捉點(diǎn)。

2.1 主要數(shù)據(jù)結(jié)構(gòu)

主要數(shù)據(jù)結(jié)構(gòu)為邊線結(jié)點(diǎn)鏈表SnapList，其數(shù)據(jù)元素為結(jié)構(gòu)類型:

社會(huì)主義核心價(jià)值觀如何培育與踐行？習(xí)近平總書記2014年5月中旬到上海考察時(shí)指出，“培育和踐行社會(huì)主義核心價(jià)值觀，貴在堅(jiān)持知行合一、堅(jiān)持行勝于言，在落細(xì)、落小、落實(shí)上下功夫?！敝驹阜?wù)作為普通老百姓自覺的助人行為，充分體現(xiàn)了細(xì)、小、實(shí)的特點(diǎn)，是培育和踐行社會(huì)主義核心價(jià)值觀重要載體。筆者擬結(jié)合泉州志愿服務(wù)開展的現(xiàn)狀與特點(diǎn)，探討完善志愿服務(wù)，培育與踐行社會(huì)主義價(jià)值觀的思路。

struct SnapPoint

{

IPoint pt;∥坐標(biāo)點(diǎn)

bool bIsAdded;∥是否附加結(jié)點(diǎn)

bool bMoved;∥是否被捕捉

int refGeomOID，refPartIndex，refSegmentIndex;∥參考幾何體OID，參考部件序號(hào)，參考線段序號(hào)

IPoint refPoint;∥捕捉點(diǎn)

double refDistance;∥到參考幾何體的距離

double fromPointDistance;∥到參考線段起點(diǎn)的距離

}

2.2 算法步驟

本算法通過結(jié)點(diǎn)加密、結(jié)點(diǎn)捕捉和結(jié)點(diǎn)順序調(diào)整等多個(gè)步驟對(duì)邊線進(jìn)行捕捉處理，主要步驟為:

1)加密結(jié)點(diǎn)。依次讀入輸入邊ledit的各個(gè)結(jié)點(diǎn)，在相鄰兩個(gè)結(jié)點(diǎn)之間以容限d為間距插入附加結(jié)點(diǎn)。如圖4所示，空心點(diǎn)為插入的附加結(jié)點(diǎn)。為每個(gè)結(jié)點(diǎn)新建為一個(gè)SnapPoint元素，其中原有結(jié)點(diǎn)的 bIsAdded為 false，附加結(jié)點(diǎn)的 bIsAdded為Ture。將各個(gè)SnapPoint元素依次寫入SnapList鏈表。

圖4 加密結(jié)點(diǎn)Fig.4 Insert nodes on the edited line

2)查找最近的捕捉點(diǎn)。對(duì)于SnapList鏈表中的每個(gè)元素vi，查找在其容限d內(nèi)的參考邊并計(jì)算到該參考邊上的最近距離和最近距離點(diǎn)，將其記錄到 refGeomOID、 refPartIndex、 refSegmentIndex、refDistance和 refPoint字段，并將 bMoved賦值為True。

若在結(jié)點(diǎn)vi的容限距離d內(nèi)找到多條參考邊，取refDistance最小者為捕捉目標(biāo)，并更新refGeomOID、refPartIndex、refSegmentIndex和 refDistance和refPoint。如圖5所示，結(jié)點(diǎn) vi到參考邊 lref和的距離都小于容限，取間距更小的參考邊為vi捕捉的目標(biāo)對(duì)象。

圖5 將間距最小的參考邊作為捕捉目標(biāo)Fig.5 The nearest reference works as snapping target

若在結(jié)點(diǎn)vi的容限距離d內(nèi)沒有任何參考邊，并且它是一個(gè)bIsAdded值為True的附加結(jié)點(diǎn)，將其從鏈表中刪除。

3)調(diào)整捕捉點(diǎn)到參考邊結(jié)點(diǎn)。依據(jù)refGeomOID、refPartIndex、refSegmentIndex取得結(jié)點(diǎn) vi的捕捉點(diǎn)所在的參考線段。若該結(jié)點(diǎn)到參考線段的某個(gè)端點(diǎn)uk的距離小于容限，則將其捕捉點(diǎn)改為端點(diǎn)uk。如圖6所示，v3到參考線段的端點(diǎn)u4的距離小于容限，將其捕捉點(diǎn)由垂足u3改為結(jié)點(diǎn)u4;v1和v2在參考邊上的捕捉點(diǎn)分別為結(jié)點(diǎn)u1和垂足點(diǎn)u2，保持不變。

圖6 將捕捉點(diǎn)調(diào)整到參考線段的端點(diǎn)Fig.6 Adjust snapped points to segments'ends

4)調(diào)整結(jié)點(diǎn)次序。遍歷SnapList鏈表，依據(jù)bMoved、refGeomOID和refPartIndex將其劃分成若干個(gè)子序列。同一個(gè)子序列中的各個(gè)結(jié)點(diǎn)全部未捕捉，或者全部被捕捉到同一條參考邊;不同的子序列中的結(jié)點(diǎn)被捕捉到不同的參考邊。同一個(gè)子序列中的各個(gè)結(jié)點(diǎn)的捕捉點(diǎn)所在的參考線段序號(hào)應(yīng)該是單調(diào)增加或單調(diào)減少的。如果某個(gè)子序列中起點(diǎn)和終點(diǎn)對(duì)應(yīng)的參考線段序號(hào)是增大的，但其內(nèi)部某些相鄰結(jié)點(diǎn)對(duì)應(yīng)的參考線段序號(hào)是減小的，則在這些參考線段序號(hào)減小的結(jié)點(diǎn)的捕捉點(diǎn)處發(fā)生了方向反轉(zhuǎn)，引起自相交問題;反之，如果某個(gè)子序列中起點(diǎn)和終點(diǎn)對(duì)應(yīng)的參考線段序號(hào)是減小的，參考線段序號(hào)增大的結(jié)點(diǎn)的捕捉點(diǎn)處發(fā)生了方向反轉(zhuǎn)。具體檢測(cè)時(shí)，如果相鄰兩個(gè)捕捉點(diǎn)的refSegmentIndex相等，還需進(jìn)一步計(jì)算fromPointDistance來判斷結(jié)點(diǎn)前進(jìn)方向。

若相鄰兩個(gè)捕捉點(diǎn)v'i到v'i+1存在方向上的反轉(zhuǎn)，依次回退檢測(cè)v'i的前一個(gè)捕捉點(diǎn)v'i－1到v'i+1是否存在方向上的反轉(zhuǎn);若滿足反轉(zhuǎn)條件，繼續(xù)比較v'i－1的前一個(gè)捕捉點(diǎn)v'i－2，直到某個(gè)前驅(qū)捕捉點(diǎn)v'k到v'i+1不存在方向反轉(zhuǎn)為止。此時(shí)，將v'i+1從鏈表中刪除后重新插入到v'k之后的位置，從而消除v'i+1引起的反轉(zhuǎn)現(xiàn)象。依次處理該子序列中的反轉(zhuǎn)捕捉點(diǎn)，直到消除所有反轉(zhuǎn)現(xiàn)象。

如圖7所示，輸入邊ledit上的5個(gè)原有結(jié)點(diǎn)v2、v3、v4、v5、v6和1個(gè)附加結(jié)點(diǎn)v8被捕捉到參考邊lref上。輸入邊捕捉處理后的結(jié)點(diǎn)序列為v'1、v'2、v'3、v'4、v'5、v'8、v'6、v'7。其中，v'2v'3與 v'3v'4、v'3v'4與 v'4v'5、v'3v'4與 v'5v'8之間存在自相交問題。經(jīng)過糾正處理后，結(jié)點(diǎn)序列將調(diào)整為v'1、v'4、v'2、v'5、v'8、v'3、v'6、v'7。

圖7 處理捕捉點(diǎn)順序反轉(zhuǎn)引起的自相交問題Fig.7 Processing reversed snapped points

(5)依據(jù)鏈表中保留的結(jié)點(diǎn)的捕捉點(diǎn)構(gòu)造一條新邊線。其中，某個(gè)結(jié)點(diǎn)無捕捉點(diǎn)時(shí)用原坐標(biāo)點(diǎn)代替。判斷邊線上相鄰的三個(gè)結(jié)點(diǎn)是否共線，刪除共線的多余的結(jié)點(diǎn)，得到最終的捕捉處理結(jié)果。

3 實(shí)驗(yàn)結(jié)果與分析

在土地利用變更調(diào)查中，新調(diào)繪的本年度變更圖斑需要與上一年度的地類圖斑協(xié)調(diào)一致。如圖8(a)所示，分別以本年度的變更圖斑和上一年度的地類圖斑為輸入圖形和參考圖形，輸入邊與參考邊非常接近但又不完全重合。本次實(shí)驗(yàn)中將捕捉容限設(shè)定為1 m，輸入邊上全部10個(gè)結(jié)點(diǎn)到參考邊的距離都小于容限，線段v9v10到結(jié)點(diǎn)h的距離大于容限。

本文算法捕捉處理結(jié)果見圖8(b)。其中，輸入邊按間距1 m加密結(jié)點(diǎn)。分析捕捉線發(fā)現(xiàn)，輸入邊上的全部結(jié)點(diǎn)都被捕捉到參考邊;而且除線段v8v9之外，其余組成線段與參考邊完全重合。實(shí)際上，除參考邊的結(jié)點(diǎn)h之外，輸入邊和參考邊相互之間的距離均小于容限，因此捕捉處理是完全的和準(zhǔn)確的。

作為比較，我們給出了ArcGIS軟件捕捉處理的結(jié)果，其捕捉類型設(shè)為Edge和Vertex，分別見圖8(c)和圖8(d)。ArcGIS提供批量捕捉結(jié)點(diǎn)的功能，其捕捉結(jié)果有一定的代表性。在圖8(c)中，輸入邊上的線段 v1v2、v2v3、v3v4、v5v6和v8v9未被捕捉到與參考邊重合;線段v3v4與v4v5之間存在自相交問題。在圖8(d)中，結(jié)點(diǎn)v5和v7未被捕捉到參考邊，線段 v1v2、v6v7、v7v8和v8v9未被捕捉到與參考邊重合。這兩種捕捉結(jié)果都不符合要求，未實(shí)現(xiàn)有效的邊線捕捉。

從結(jié)點(diǎn)捕捉的有效性看，本文算法將原結(jié)點(diǎn)捕捉和附加結(jié)點(diǎn)都捕捉到容限距離內(nèi)參考邊上正確的位置;而ArcGIS軟件計(jì)算的捕捉點(diǎn)偏離參考邊上對(duì)應(yīng)的結(jié)點(diǎn)，或者沒有捕捉到容限距離內(nèi)的參考邊。從結(jié)點(diǎn)之間的線段來看，本文算法將各條線段準(zhǔn)確捕捉到容限距離內(nèi)與參考邊重合的位置;而ArcGIS軟件捕捉處理后的線段并不與參考邊完全重合。從圖形的拓?fù)湔_性看，本文算法處理結(jié)果中不存在線自相交錯(cuò)誤;而ArcGIS軟件處理結(jié)果不能排除自相交錯(cuò)誤。這三個(gè)方面體現(xiàn)了本文算法的有效性和可靠性。

4 結(jié)論

根據(jù)以上研究和實(shí)驗(yàn)，可以得到以下結(jié)論:

1)通過調(diào)整捕捉點(diǎn)到容限距離內(nèi)的參考邊的結(jié)點(diǎn)，本文算法實(shí)現(xiàn)了輸入邊結(jié)點(diǎn)與參考邊結(jié)點(diǎn)的嚴(yán)密配準(zhǔn)。

2)本文算法在邊線上插入附加結(jié)點(diǎn)，實(shí)現(xiàn)了邊線層次的配準(zhǔn)和捕捉處理。通過對(duì)附加結(jié)點(diǎn)的捕捉和移動(dòng)，使一些直線段轉(zhuǎn)換為折線段，從而捕捉到與容限距離內(nèi)的參考邊完全重合的位置。

3)結(jié)點(diǎn)捕捉改變了結(jié)點(diǎn)的相對(duì)位置，從而引起線自相交錯(cuò)誤。本文算法引入的結(jié)點(diǎn)順序調(diào)整處理步驟有效地消除了結(jié)點(diǎn)次序反轉(zhuǎn)現(xiàn)象，解決了捕捉后的邊線的自相交問題。

4)本文方法實(shí)現(xiàn)了線層次的圖形捕捉處理，相對(duì)于以ArcGIS為代表的結(jié)點(diǎn)捕捉算法而言能更有效地進(jìn)行圖形數(shù)據(jù)融合。

［1］SAALFELD A.Conflation:automated map compilation［J］.International Journal of Geographical Information Systems，1988，2(3)，pp.217 －228.

［2］SERVIGNE S，UBEDA T.A Methodology of Spatial Consistency Improvement of Geographic Databases ［J］.GeoInformatica，2000，4(1):7－34.

［3］SAMAL A，SETH S，CUETO K.A feature-based approach to conflation of geospatial sources［J］.International Journal of Geographical Information Science，2004，18(5)，pp.459－489.

［4］魯偉，謝順平，鄧 敏，周立國.多源空間數(shù)據(jù)間不一致性研究現(xiàn)狀及其進(jìn)展［J］.測(cè)繪科學(xué)，2009，34(4):57－60.

［5］韓凌云，楊英力.地形圖與海圖拼接的矛盾問題及其處理［J］.海洋測(cè)繪，2003，23(4):33－35.

［6］呂蓬，張立朝，王耿峰.空間數(shù)據(jù)融合在海圖中的應(yīng)用［J］.測(cè)繪通報(bào)，2007，(11):43－45，56.

［7］吳磊，黃先鋒，舒寧.GIS大數(shù)據(jù)量編輯處理中快速捕捉的優(yōu)化策略［J］.武漢理工大學(xué)學(xué)報(bào):交通科學(xué)與工程版，2005，29(2):315－318.

［8］劉文寶，夏宗國，崔先國.GIS結(jié)點(diǎn)捕捉的廣義算法及誤差傳播模型［J］.測(cè)繪學(xué)報(bào)，2001，30(2):140－147.

［9］鄧敏，劉文寶，馮學(xué)智.GIS中地理邊線不一致性的處理［J］.遙感學(xué)報(bào)，2005，9(4):343－348.