周麗珠 ，劉富東，周義軍，王光昇

(1.天津市測(cè)繪院，天津 300381;2.天津市市政工程建設(shè)公司，天津 300100)

1 引言

地理信息是圖形信息和屬性信息兩類(lèi)信息的集成，地理要素是地理信息的載體?，F(xiàn)實(shí)中，所有的地理要素都是完整的個(gè)體。由于傳統(tǒng)習(xí)慣和用戶(hù)的需求，數(shù)字測(cè)圖仍采用分幅的圖幅設(shè)計(jì)方法，將連續(xù)的地表空間劃分為若干子空間，將圖幅邊線(xiàn)處完整的地理實(shí)體分割后放置在相鄰的圖幅中。而實(shí)際應(yīng)用中，所需的數(shù)據(jù)中地理要素應(yīng)為一個(gè)完整的個(gè)體，因此，數(shù)據(jù)的圖幅接邊不可避免，如何精確高效地解決圖幅接邊問(wèn)題成為測(cè)圖領(lǐng)域中的一個(gè)研究課題，同樣也是GIS應(yīng)用領(lǐng)域的一個(gè)研究課題。為此，筆者設(shè)計(jì)了一種基于關(guān)系探測(cè)聚類(lèi)的圖幅自動(dòng)接邊算法，并利用ArcGIS Engine 9.3二次開(kāi)發(fā)組件實(shí)現(xiàn)了此算法，提高了接邊效率和準(zhǔn)確度。

2 自動(dòng)接邊關(guān)鍵技術(shù)

2.1 地物匹配

接邊線(xiàn)兩側(cè)的地物自動(dòng)匹配是自動(dòng)接邊算法的核心所在，本文從如下三個(gè)方面提高匹配的準(zhǔn)確度:類(lèi)別匹配，圖形匹配和屬性匹配。

(1)類(lèi)別匹配，只有同類(lèi)的地物才進(jìn)行匹配。在數(shù)據(jù)表現(xiàn)上，以圖層為劃分單位。

(2)圖形匹配，一般以距離為指標(biāo)，距離在閾值范圍內(nèi)的圖形要素才進(jìn)行匹配。但是，面要素應(yīng)排除點(diǎn)連接的情況，只保留線(xiàn)連接情況，如圖1所示。

(3)屬性匹配，綜合考慮屬性結(jié)構(gòu)和屬性值這兩類(lèi)因素，完全相同，則匹配成功，否則失敗。

這三方面，每一方面都獨(dú)立于其他兩方面存在，假設(shè)每方面的匹配錯(cuò)誤概率都為10%，那么，綜合考慮三方面后的匹配錯(cuò)誤率為P，則P在區(qū)間［0，10%］內(nèi)，由“中心極限定理”可知，如果一個(gè)量是由許多微小的獨(dú)立隨機(jī)因素影響的結(jié)果，那么這個(gè)量就可看成符合正態(tài)分布的，可見(jiàn)這種匹配系統(tǒng)是可行且有效的。

圖1 面要素連接的兩種方式

2.2 空間聚類(lèi)

空間聚類(lèi)是將空間對(duì)象幾何劃分為由相似對(duì)象組成的多個(gè)簇的過(guò)程。同簇內(nèi)的對(duì)象之間具有盡可能大的相似性，而不同簇的對(duì)象之間則具有較大的差異性，從而有助于人們認(rèn)識(shí)現(xiàn)象的整體分布模式。在GIS研究中，學(xué)者們將計(jì)算幾何技術(shù)、圖論方法與傳統(tǒng)的聚類(lèi)分析方法結(jié)合提出了面向空間目標(biāo)的空間聚類(lèi)方法。

本文基于空間聚類(lèi)方法的思想，聯(lián)系自動(dòng)接邊的實(shí)際需求，設(shè)計(jì)出基于關(guān)系探測(cè)聚類(lèi)的圖形自動(dòng)接邊算法，方便接邊檢查，提高了運(yùn)算效率。

2.3 合并要素

合并要素是將某類(lèi)幾何要素合成一體，并保證其屬性不變。在理論上，這些幾何要素應(yīng)完全吻合，實(shí)際中，由于數(shù)據(jù)的誤差，常常做不到這一點(diǎn)。如圖2所示，線(xiàn)要素間存在錯(cuò)位和面要素間存在縫隙。這時(shí)，就需要采取一些方法來(lái)將幾何要素接合起來(lái)，使得圖形完全吻合［1］。

圖2 合并要素錯(cuò)誤

解決這個(gè)問(wèn)題通常有三種方式［2］:

(1)平均法

平均法是取圖形兩邊待接點(diǎn)的坐標(biāo)均值作為接邊后的點(diǎn)的坐標(biāo)。該方法簡(jiǎn)單易行，適用于接邊誤差在精度允許范圍內(nèi)的各種直線(xiàn)、折線(xiàn)的接邊處理，容易實(shí)現(xiàn)接邊的全自動(dòng)批量處理。

(2)強(qiáng)制法

強(qiáng)制法是把一條待接邊的待接點(diǎn)強(qiáng)制附和到另一條待接邊的待接點(diǎn)上。該方法主要用于用戶(hù)能明顯判斷出哪一條待接邊比另一條待接邊更準(zhǔn)確、可靠，適合交互式的接邊處理。

(3)優(yōu)化法

無(wú)論采用平均法還是強(qiáng)制法，在邊界處都要產(chǎn)生一個(gè)拐點(diǎn)。一般拐點(diǎn)的拐角很小。但是如果待接邊明顯是一條直線(xiàn)邊的話(huà)，這個(gè)很小的拐角也影響圖形美觀(guān)。因此應(yīng)考慮接邊后兩端線(xiàn)段仍要在一條直線(xiàn)上，既要共點(diǎn)，也要共線(xiàn)。

以上三種方式各有優(yōu)缺點(diǎn)，可根據(jù)實(shí)際情況決定采用哪種方式。本文采用了平均法的方式處理圖形誤差，實(shí)現(xiàn)自動(dòng)接邊算法。而且線(xiàn)要素和面要素可以統(tǒng)一為一種方式進(jìn)行處理，以面要素為例，如圖2中的面要素縫隙所示。

首先，找出面A上與接邊線(xiàn)距離在閾值范圍內(nèi)的點(diǎn)的集合Q={點(diǎn)a，點(diǎn)b}，同理，面B的點(diǎn)集合為W={點(diǎn) c，點(diǎn) d}。

其次，針對(duì)點(diǎn)集Q和W中的點(diǎn)元素進(jìn)行匹配，如點(diǎn)a和點(diǎn)c分屬點(diǎn)集Q和W，并且點(diǎn)a和點(diǎn)c之間的距離在閾值范圍內(nèi)，則匹配成功。

最后，對(duì)匹配成功的點(diǎn)對(duì)，用平均法進(jìn)行處理，之后進(jìn)行要素合并。

3 自動(dòng)接邊的邏輯思維

自動(dòng)接邊算法實(shí)質(zhì)為確定其邏輯順序的過(guò)程，而自動(dòng)接邊的邏輯思維大體可分為兩類(lèi)，一是循環(huán)邏輯思維，一是階段性邏輯思維。

3.1 循環(huán)邏輯思維

循環(huán)邏輯思維是抽出具有共性的過(guò)程作為基本單元，循環(huán)基本單元，直到滿(mǎn)足臨界條件為止?，F(xiàn)有的自動(dòng)接邊算法大多采用循環(huán)邏輯思維，如圖3所示，設(shè)線(xiàn)要素1與線(xiàn)要素2接邊為一個(gè)過(guò)程A，即為接邊過(guò)程的基本單元。過(guò)程A通常包含“地物匹配”和“合并要素”兩個(gè)步驟，通過(guò)這兩個(gè)步驟可得到線(xiàn)要素1'，將線(xiàn)要素1'取代線(xiàn)要素1和2加入到選擇集中，更新地物和選擇集。重復(fù)過(guò)程A直到所有地物接邊完成。

圖3 循環(huán)邏輯思維

3.2 階段性邏輯思維

階段性邏輯思維是將過(guò)程分成各個(gè)階段，每個(gè)階段完成后才進(jìn)行下一階段的操作。本文從實(shí)際應(yīng)用出發(fā)，采用了這種邏輯思維方式進(jìn)行自動(dòng)接邊算法設(shè)計(jì)。利用關(guān)系探測(cè)聚類(lèi)的方法，將自動(dòng)接邊過(guò)程分成“地物聚類(lèi)”和“合并地物”兩個(gè)階段。

地物聚類(lèi)是將接邊線(xiàn)兩側(cè)需要接邊的圖形要素聚集成n個(gè)子類(lèi)，如圖4所示，線(xiàn)段1、線(xiàn)段2和線(xiàn)段3為一個(gè)子類(lèi);線(xiàn)段4和線(xiàn)段5為另一個(gè)子類(lèi)。

合并地物是依據(jù)地物聚類(lèi)后的結(jié)果，利用ArcGIS Engine組件中 ITopologicalOperator接口的ConstructU-nion方法分別對(duì)各個(gè)子類(lèi)中的圖形要素進(jìn)行合并操作，得到接邊后的結(jié)果。

圖4 順序邏輯思維

3.3 兩種邏輯思維的比較

在自動(dòng)接邊算法上，階段性邏輯思維與循環(huán)邏輯思維相比，具有兩種優(yōu)勢(shì)。

第一，在同一圖層數(shù)據(jù)的接邊中，“地物匹配”和“合并要素”徹底分離開(kāi)來(lái)，也即將接邊檢查和實(shí)際接邊操作分離開(kāi)來(lái)，接邊檢查只需進(jìn)行地物聚類(lèi)過(guò)程，提高了接邊檢查的速度。

第二，減少更新圖形數(shù)據(jù)和數(shù)據(jù)選擇集的次數(shù)，提高了算法的效率，而且選擇集中的要素?cái)?shù)量越多，算法效率提升得越明顯。

4 基于關(guān)系探測(cè)聚類(lèi)的自動(dòng)接邊算法設(shè)計(jì)

本文按照階段性邏輯思維，融合空間聚類(lèi)的思想，設(shè)計(jì)出基于關(guān)系探測(cè)聚類(lèi)的自動(dòng)接邊算法，其算法具體步驟如圖5所示。

4.1 算法流程

通過(guò)接邊線(xiàn)建立接邊要素的選擇集，對(duì)選擇集中的要素通過(guò)關(guān)系探測(cè)方法進(jìn)行聚類(lèi)，得到子類(lèi)1，子類(lèi)2，…，子類(lèi)n，這其中，只有一個(gè)地理要素的子類(lèi)屬于接邊錯(cuò)誤，輸出到錯(cuò)誤報(bào)表。之后分別對(duì)需要接邊的子類(lèi)進(jìn)行合并要素操作，得到接邊完成的數(shù)據(jù)。

圖5 自動(dòng)接邊算法流程

4.2 關(guān)系探測(cè)聚類(lèi)

(1)關(guān)系聚類(lèi)算法設(shè)計(jì)

本文中，空間對(duì)象的相似性可理解為空間對(duì)象之間的關(guān)系定義，這種關(guān)系定義決定了聚類(lèi)的結(jié)果。基于此，本文提出了一種關(guān)系探測(cè)聚類(lèi)方法。根據(jù)實(shí)際需要定義關(guān)系函數(shù)，依據(jù)關(guān)系函數(shù)初始化關(guān)系鏈，再通過(guò)探測(cè)各個(gè)關(guān)系鏈達(dá)到聚類(lèi)目的。

算法步驟如下:

輸入:幾何要素集 δ={幾何要素 a，b，c，d，e，……}

輸出:幾何要素子集 A，B，C，……

步1:根據(jù)實(shí)際要求，定義關(guān)系函數(shù)f(x，y)，f(x，y)表示幾何要素x與y的關(guān)系。

步2:對(duì)幾何要素集δ中每一個(gè)幾何要素都產(chǎn)生一個(gè)關(guān)系集 S(a)，S(a)定義如下式子，S(a)={x|f(x，a)=1，x∈δ}，其中 a 為幾何要素集 δ中任意一個(gè)幾何要素。

步3:關(guān)系探測(cè)得到一個(gè)聚類(lèi)結(jié)果——幾何要素子集A。

搜索 S(a)，設(shè) S(a)={x，y，z，……}，此時(shí)子集A為空集，所以幾何要素 x，y，z，……都不屬于子集A，則將幾何要素 x，y，z，……加入到子集 A中，循環(huán)搜索對(duì)應(yīng)于幾何要素 x，y，z，……的關(guān)系集 S(x)，S(y)，S(z)，……。如果S(x)中存在幾何要素α不屬于子集A，則將幾何要素α加入到幾何要素集A中，更新子集A，接著搜索S(a)，搜索過(guò)程同S(a)。關(guān)系集S(x)(x∈δ)完成搜索的標(biāo)志為——幾何要素集A的個(gè)數(shù)不再增加。

步4:循環(huán)探測(cè)，得到所有聚類(lèi)后的幾何要素子集。

設(shè)幾何要素b屬于幾何要素集δ，但幾何要素b對(duì)應(yīng)的關(guān)系集沒(méi)有被探測(cè)，即不屬于任何一個(gè)現(xiàn)有的幾何要素子集A，B，C，……。用幾何要素b代替步4中的幾何要素a，重復(fù)步3，直到所有的幾何要素的關(guān)系集都被探測(cè)，得到最后聚類(lèi)的結(jié)果——幾何要素子集A，B，C，……。

(2)定義自動(dòng)接邊的聚類(lèi)關(guān)系函數(shù)

根據(jù)本文所提的地物匹配原則，具體定義關(guān)系函數(shù) f(x，y)，如圖6所示。

圖6 定義關(guān)系函數(shù)

5 應(yīng)用實(shí)例

目前，此算法已經(jīng)實(shí)現(xiàn)并應(yīng)用到《天津市1∶2000地形圖數(shù)據(jù)改造》項(xiàng)目中，合并了大概 13 700幅標(biāo)準(zhǔn)圖幅的地形圖數(shù)據(jù)，大大提高了工作效率。圖7為接邊程序界面。

圖8為接邊前的兩幅地形圖，圖9為接邊后的兩幅地形圖，圖中圖形接邊都可自動(dòng)完成。

圖7 接邊程序

圖8 接邊前的兩幅圖

圖9 接邊后的兩幅圖

6 結(jié)語(yǔ)

在數(shù)字測(cè)圖的今天，接邊問(wèn)題仍然存在，特別是在已有地圖的數(shù)字化過(guò)程中，接邊工作量占整個(gè)圖形編輯工作量的20% ～30%［3］，而接邊工作的好壞直接影響數(shù)據(jù)質(zhì)量。

本文提出了一種基于關(guān)系探測(cè)聚類(lèi)的自動(dòng)接邊算法，將地物匹配和合并要素徹底分離開(kāi)來(lái)，有利于接邊檢查。另外，此算法減少更新數(shù)據(jù)和選擇集的次數(shù)，提高了程序效率。

［1］劉慶元，周容.一種基于ArcG IS Engine的線(xiàn)狀圖幅接邊方法［J］.計(jì)算機(jī)時(shí)代，2008(2):4～5

［2］宋偉東，吳澤金，趙東輝.數(shù)字地形圖接邊方法研究［J］.遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2000，19(5):493～496

［3］劉興權(quán)，尹長(zhǎng)林，牛續(xù)苗等.AutoCAD Map2000在圖形接邊中的應(yīng)用［J］.測(cè)繪工程，2003(1):53～54

［4］趙江洪.GIS中多圖幅自動(dòng)接邊的實(shí)現(xiàn)方法探討［J］.測(cè)繪通報(bào)，2006(2):50～52

［5］龔健雅.當(dāng)代GIS的若干理論與技術(shù)［M］.武漢:武漢測(cè)繪科技大學(xué)出版社，1993

［6］樊紅.Arc/Info應(yīng)用與開(kāi)發(fā)技術(shù)［M］.武漢:武漢測(cè)繪科技大學(xué)出版社，1999