周曉光，陳 斐，，陳 軍

1.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長(zhǎng)沙410083；2.國(guó)家基礎(chǔ)地理信息中心，北京100036

1 引 言

線/面實(shí)體間存在多種拓?fù)潢P(guān)系，這些關(guān)系在空間數(shù)據(jù)建模、分析、查詢(xún)、更新與質(zhì)量控制中起著重要作用。如圖1所示的線狀道路與面狀河流間的沖突檢測(cè)中，一般認(rèn)為道路與河流應(yīng)為分離關(guān)系，如果相交，則可能存在沖突。圖1（a）中彎曲河流（灰色面）與道路（黑色線）間存在4個(gè)交，各個(gè)交的細(xì)分情況又彼此不同：圖1（b）道路穿越河流，圖1（c）道路完全落入河流，圖1（d）道路部分落入河流，圖1（e）道路接觸河流。上述4種線面拓?fù)潢P(guān)系細(xì)分情況對(duì)應(yīng)著不同的處理方法：圖1（b）所示的沖突一般將穿越路段用橋梁替代；圖1（c）可能是由于該道路目標(biāo)位置信息或編碼信息存在錯(cuò)誤；圖1（d）在數(shù)據(jù)質(zhì)量控制時(shí)，要對(duì)落入河流的路段進(jìn)行檢測(cè)，如果該路段在容差允許范圍內(nèi)應(yīng)該將其剪切掉；圖1（e）可能是測(cè)量誤差所致，一般對(duì)接觸路段簡(jiǎn)單移位即可。

圖1 線狀道路與面狀河流間的細(xì)分拓?fù)潢P(guān)系Fig.1 Examples of the refined topological intersection types between lines（roads）and polygons（rivers）

從圖1可看出，一條河流可能與多條道路有交，也可能與一條道路存在多個(gè)不同的交。在空間數(shù)據(jù)沖突檢測(cè)與處理中，需要檢測(cè)出每一個(gè)線/面交，并區(qū)分交的細(xì)分類(lèi)型，然后根據(jù)細(xì)分類(lèi)型采取不同的處理方法。

近年來(lái)，多位學(xué)者在二維空間目標(biāo)拓?fù)潢P(guān)系的描述與計(jì)算方面開(kāi)展了大量的研究工作，取得了豐富的研究成果，主要包括基本拓?fù)潢P(guān)系模型和細(xì)分拓?fù)潢P(guān)系模型兩大類(lèi)?；就?fù)潢P(guān)系模型用若干個(gè)特定變量的不同取值來(lái)區(qū)分二元目標(biāo)間的相離、相接、相交、包含、相等基本拓?fù)潢P(guān)系類(lèi)型，代表性模型包括四元組模型［1］，九元組模型［2］，基 于 維 數(shù) 擴(kuò) 展 的 九 元 組 模 型［3－4］，基 于Voronoi圖的 V9I模型［5－6］，使用目標(biāo)整體及其Voronoi區(qū)域的VW 方法［7］，基于目標(biāo)整體交、差結(jié)果的歐拉數(shù)的 E－WID 方法［8－12］，基于目標(biāo)整體的空間邏輯的RCC方法［13－15］等。上述基本拓?fù)潢P(guān)系模型無(wú)法精確區(qū)分如圖1所示的線/面目標(biāo)間存在多個(gè)交的細(xì)分類(lèi)型，難以滿(mǎn)足數(shù)據(jù)質(zhì)量檢查與處理的應(yīng)用需求。

為此，多位學(xué)者發(fā)展了通過(guò)交的順序、類(lèi)型等分量表達(dá)目標(biāo)間精確拓?fù)潢P(guān)系的細(xì)分拓?fù)潢P(guān)系模型。在面/面細(xì)分拓?fù)潢P(guān)系方面，文獻(xiàn)［16—17］提出基于邊界/邊界交的細(xì)分模型；文獻(xiàn)［8］提出基于目標(biāo)整體交、差結(jié)果的歐拉數(shù)的E－WID模型；文獻(xiàn)［18］提出一種空間拓?fù)潢P(guān)系進(jìn)行定量描述的方法。在線/線細(xì)分拓?fù)潢P(guān)系方面，文獻(xiàn)［4］提出一種基于線目標(biāo)整體交的順序、共線性、類(lèi)型、連接方向的細(xì)分方法。另外，多位學(xué)者探索了不確定線/面目標(biāo)間的拓?fù)潢P(guān)系問(wèn)題［20－21］等，但在線/面細(xì)分拓?fù)潢P(guān)系模型研究方面成果有限。

在現(xiàn)有文獻(xiàn)中線/面細(xì)分拓?fù)潢P(guān)系的研究成果主要包括文獻(xiàn)［22］提出的一種通過(guò)線目標(biāo)整體與面目標(biāo)邊界交的基本拓?fù)潢P(guān)系來(lái)區(qū)分線/面目標(biāo)間細(xì)分拓?fù)潢P(guān)系的方法。該方法將線/面基本拓?fù)潢P(guān)系定義為“一條線和一個(gè)面邊界相交為0或1次的關(guān)系”。根據(jù)該定義他們通過(guò)枚舉方法得到了16種基本拓?fù)潢P(guān)系（包括相離，2種交點(diǎn)類(lèi)型和13種交線類(lèi)型，交線類(lèi)型中又包括3種對(duì)稱(chēng)交線類(lèi)型，因此實(shí)質(zhì)為10種交線類(lèi)型）。但是上述16種線/面基本拓?fù)潢P(guān)系不包括最常見(jiàn)的穿越關(guān)系（即一條線和一個(gè)面的邊界交于兩個(gè)點(diǎn)的關(guān)系，如圖1（b）所示），不符合人們的認(rèn)知習(xí)慣。且根據(jù)上述定義，基本交線的劃分不具有唯一性，如圖2中的P1—P2、P3—P4必須被打斷，其基本交線可劃為P1—A1、A1—P2、P2—P3、P3—A2、A2—P4、P4—P5、P5—P6，也可分為P1—A1、A1—B1、B1—A2、A2—B2、B2—P6，或P1—A1、A1—P3、P3—A2、A2—P5、P5—P6等。此外，文獻(xiàn)［19］提出一種線/面拓?fù)潢P(guān)系的組合推理方法，推導(dǎo)出了97種線/面拓?fù)潢P(guān)系組合類(lèi)型；文獻(xiàn)［23］提出了一種用拓?fù)浜投攘糠至烤仃噷?duì)線/面關(guān)系進(jìn)行細(xì)分描述和計(jì)算的方法；這些方法沒(méi)有明確定義包含多個(gè)交的線面關(guān)系中每個(gè)交的細(xì)分類(lèi)型與描述方法，因此難以指導(dǎo)線/面目標(biāo)間的沖突檢測(cè)與處理。

圖2 現(xiàn)有線/面基本交線劃分非唯一性Fig.2 An example of non－uniqueness of the line/polygon intersection segment

空間目標(biāo)間的拓?fù)潢P(guān)系是客觀存在的，理論上線/面目標(biāo)間可存在無(wú)數(shù)個(gè)交，各個(gè)交的類(lèi)型又可能不一樣，因此具有多個(gè)交的線/面拓?fù)潢P(guān)系的組合類(lèi)型可能是無(wú)窮的。人們對(duì)拓?fù)潢P(guān)系的認(rèn)識(shí)是由粗到細(xì)、由宏觀到微觀、由淺入深，具有層次性。在宏觀層面對(duì)拓?fù)潢P(guān)系的描述往往包括兩目標(biāo)是否有交、有幾個(gè)交、交的維數(shù)如何、交集對(duì)兩目標(biāo)的作用效果如何等；而微觀層次對(duì)拓?fù)潢P(guān)系的描述則詳細(xì)到每個(gè)交的具體情況，但目前尚缺少符合認(rèn)知習(xí)慣的線/面拓?fù)潢P(guān)系層次模型。

本文在基于目標(biāo)整體交、差結(jié)果的歐拉數(shù)的E－WID層次模型［8－10］的基礎(chǔ)上，引入結(jié)點(diǎn)度來(lái)區(qū)分線/面交的細(xì)分拓?fù)潢P(guān)系類(lèi)型，提出一種基于結(jié)點(diǎn)度的線/面拓?fù)潢P(guān)系細(xì)分方法。

2 結(jié)點(diǎn)度的引入

E－WID層次模型如式（1）、式（2）所示，能夠計(jì)算基礎(chǔ)拓?fù)潢P(guān)系和部分細(xì)分拓?fù)潢P(guān)系。在粗分層次采用式（1）所示目標(biāo)整體交、差結(jié)果的維數(shù)和歐拉數(shù)來(lái)描述兩目標(biāo)是否有交、交的個(gè)數(shù)、維數(shù)及交對(duì)兩目標(biāo)的分割效果；在細(xì)分層次上，則通過(guò)式（2）所示每個(gè)交的維數(shù)、類(lèi)型及順序來(lái)表達(dá)目標(biāo)間拓?fù)潢P(guān)系的細(xì)分情況

式（1）中，A、B分別表示面和線，符號(hào)“∩”、“＼”分別表示交、差運(yùn)算，A∩B、A＼B、B＼A分別表示A與B的3種集合運(yùn)算與fE分別表示運(yùn)算結(jié)果的維數(shù)與歐拉數(shù)，其中A∩B的運(yùn)算結(jié)果可能包括空、純點(diǎn)、純線和點(diǎn)/線混合情況；B＼A的運(yùn)算結(jié)果可能為空集或線集，A＼B的運(yùn)算結(jié)果一般為面集。因此的取值范圍為｛－1、0、1、2、3｝，分別表示結(jié)果為空（?）、0維（點(diǎn)）、1維（線）、2維（面）、0維點(diǎn)和1維線組合情況等。fE表示結(jié)果的歐拉數(shù)。

式（2）中，Ni（N1，N2，…，Nm）表示交的編號(hào)；Di（D1，D2，…，Dm）表示交的維數(shù)；Ti（T1，T2，…，Tm）表示交的類(lèi)型［8］。式（2）通過(guò)單元交的順序與類(lèi)型來(lái)區(qū)分兩者的細(xì)分拓?fù)潢P(guān)系。

在拓?fù)鋵W(xué)中，兩個(gè)閉集的差可能為開(kāi)集。一般認(rèn)為GIS中的拓?fù)錇閼?yīng)用拓?fù)?，空間目標(biāo)為封閉目標(biāo)（閉集），其交、差運(yùn)算結(jié)果集合中的目標(biāo)仍為封閉目標(biāo)（閉集）。圖3說(shuō)明本文線/面目標(biāo)整體交、差運(yùn)算操作的結(jié)果。設(shè)圖3（a）為面目標(biāo)A與線目標(biāo)B的拓?fù)潢P(guān)系，則A∩B、A＼B、B＼A的結(jié)果分別如圖3（b）、圖3（c）、圖3（d）所示。

圖3 面目標(biāo)A與線目標(biāo)B間交、差集合操作的定義Fig.3 The definitions of the two set operations（intersection and difference）between polygon Aand line B

式（2）中的0維交點(diǎn)的類(lèi)型易于區(qū)分。如圖4所示，設(shè)A、B為待求拓?fù)潢P(guān)系的面和線目標(biāo)，IP表示A、B的交點(diǎn)。IP僅包括在端點(diǎn)相交和在中間點(diǎn)相交兩種類(lèi)型，通過(guò)fE（B＼IP）的值即可區(qū)分。fE（B＼IP）＝1，交點(diǎn)為B的端點(diǎn)；fE（B＼IP）＝2，交點(diǎn)為B的中間點(diǎn)。

圖4 線/面交點(diǎn)類(lèi)型定義Fig.4 The definition of the topological intersection point types

交線的情況則復(fù)雜得多，當(dāng)交線多次穿越面時(shí)（圖2），單元交線的定義就存在異議。圖2中，設(shè)A為一湖泊，B為志愿者的行車(chē)軌跡。若將行車(chē)軌跡繪制為道路，根據(jù)經(jīng)驗(yàn)，P1—P2、P3—P4可能為跨湖橋梁；P2—P3、P4—P5可能為沿湖道路，P5—P6可能為碼頭等，都可能為獨(dú)立單元。可將A、B的交集打斷為P1—P2、P2—P3、P3—P4、P4—P5、P5—P65段單元交線。這些單元交線或完全位于面的內(nèi)部，或完全位于面的邊界上，或端點(diǎn)位于面的邊界上、其余點(diǎn)全位于面的內(nèi)部。為了保障基本交線的唯一性，本文對(duì)線/面單元交線定義如下：

定義：線/面單元交線為完全位于面的內(nèi)部，或完全位于面的邊界上，或僅有1—2個(gè)端點(diǎn)位于面的邊界上其余點(diǎn)全在面的內(nèi)部的連續(xù)線段，線/面交線與面目標(biāo)邊界的交點(diǎn)必為單元交線的端點(diǎn)。

此外，即使參照面/面二維交細(xì)分類(lèi)型區(qū)分方法，采用兩目標(biāo)與某個(gè)交的差的歐拉數(shù)來(lái)區(qū)分該交的細(xì)分類(lèi)型［8］，即如IL為A、B的某個(gè)單元交線，則可通過(guò)A、B與該交線IL的差的歐拉數(shù)，即fE（A＼IL）和fE（B＼IL）的取值來(lái)區(qū)分該交線的細(xì)分類(lèi)型。但該方法不能區(qū)分如圖5所示的兩對(duì)單元交線圖5（a）和圖5（b）及圖5（c）和圖5（d）的類(lèi)型。

圖5 fE（A＼IL）和fE（B＼IL）的取值不能區(qū)分的單元交線類(lèi)型Fig.5 The undistinguishable units intersection segment using fE（A＼IL）and fE（B＼IL）

仔細(xì)分析圖5中的（a）與（b）及（c）與（d）這兩對(duì)單元交線，發(fā)現(xiàn)盡管交線對(duì)A、B的分割效果完全相同，即fE（A＼IL）和fE（B＼IL）的取值完全相同，但其端點(diǎn)連通狀況完全不同。在拓?fù)鋵W(xué)和圖論中有一個(gè)反映結(jié)點(diǎn)連通狀況的指標(biāo)——結(jié)點(diǎn)的度（或次）。

拓?fù)鋵W(xué)將平面圖定義為：圖G是由點(diǎn)集V和邊集E構(gòu)成的集合，記為G＝（V，E），其中點(diǎn)集和邊集分別表示為：V＝｛v1，v1，…，vn｝，vi也稱(chēng)為頂點(diǎn)、端點(diǎn)或結(jié)點(diǎn)；E＝｛e1，e1，…，en｝，ei可以是邊（沒(méi)有方向），也可以是?。ㄓ蟹较颍?。

與點(diǎn)vi關(guān)聯(lián)的邊數(shù)稱(chēng)為該點(diǎn)的度（或次），記為deg（v）。其中度為0（deg（v）＝0）的點(diǎn)為孤立點(diǎn)；度為1（deg（v）＝1）的點(diǎn)為懸掛點(diǎn)（即線段端點(diǎn)）；度為2（deg（v）＝2）的點(diǎn)為線段中間點(diǎn)；度大于或等于3（deg（v）≥3）的點(diǎn)為結(jié)點(diǎn)［24－25］。如圖6所示，圖6（a）中的交線端點(diǎn)P1、P2的度分別為1和3；圖6（b）中的交線端點(diǎn)P1、P2的度均為2；圖6（c）中的交線端點(diǎn)P1、P2的度分別為2和3；圖6（d）中的交線端點(diǎn)P1、P2的度分別為1和4。

圖6 用結(jié)點(diǎn)度區(qū)分圖5所示的單元交線類(lèi)型Fig.6 Discriminating the unit intersection segment using node－degree

由此可見(jiàn)，在線/面交中引入結(jié)點(diǎn)的度（或次）有助于判斷線/面單元交線的細(xì)分類(lèi)型。另外，引入結(jié)點(diǎn)度后不難發(fā)現(xiàn)，盡管線/面交點(diǎn)類(lèi)型可通過(guò)fE（B＼IP）的值來(lái)區(qū)分，但用交點(diǎn)度來(lái)區(qū)分更為簡(jiǎn)單、直接，設(shè)交點(diǎn)為P，deg（P）＝3，則P為B的端點(diǎn)；deg（P）＝4，P為B的中間點(diǎn)。因此，本文采用結(jié)點(diǎn)度來(lái)區(qū)分線/面交點(diǎn)、交線的細(xì)分類(lèi)型。在E－WID模型的式（2）中引入結(jié)點(diǎn)度來(lái)區(qū)分線/面交的細(xì)分類(lèi)型：設(shè)交線的兩個(gè)端點(diǎn)為P1、P2，則交線類(lèi)型ti可用（deg（P1），deg（P2））來(lái)區(qū)分；設(shè)交點(diǎn)為P，交點(diǎn)的類(lèi)型ti可用（deg（P））來(lái)區(qū)分。

3 基于結(jié)點(diǎn)度的線/面單元交線類(lèi)型細(xì)分

引入結(jié)點(diǎn)度后，線/面單元交線的兩個(gè)端點(diǎn)P1、P2的度分別包括｛1，2，3，4｝4種可能取值，共包括16種可能組合情況。剔除其中無(wú)意義及對(duì)稱(chēng)的取值，可得到8種有意義的端點(diǎn)度組合情況，即單元交線端點(diǎn)度分別為（1，1）、（1，3）、（1，4）、（2，2）、（2，3）、（3，3）、（3，4）、（4，4）。

這一方法可以完全區(qū)分端點(diǎn)度組合為（1，1）、（2，2）的基本交線，而端點(diǎn)度包含3與4的基本交線仍然不能被詳細(xì)區(qū)分。例如，端點(diǎn)度為（1，3）、（2，3）、（1，4）的基本交線包含圖7（a）與圖7（b）、圖7（c）與圖7（d）、圖7（e）與圖7（f）3組不同的細(xì)分拓?fù)漕?lèi)型。觀察分析得出3組之間的差異，主要是由度為3或4的端點(diǎn)引起的。圖7（a）與圖7（b）的差異是交線端點(diǎn)P2是否是線目標(biāo)B的端點(diǎn)，圖7（c）與圖7（d）、圖7（e）與圖7（f）中的差異是與P2相連的線段在多邊形A的內(nèi)部還是外部。究其原因，度為3或4的端點(diǎn)既可能是線的端點(diǎn)，又可能存在相連線段，而相連線段與面的拓?fù)潢P(guān)系又存在多種情況，這些都導(dǎo)致了端點(diǎn)度包含3與4的基本交線更加復(fù)雜，而度為1或2的端點(diǎn)通常都是線目標(biāo)的端點(diǎn)，不存在相連線段，所以度為（1，1）、（2，2）的基本交線具有唯一性。

因此，為了進(jìn)一步區(qū)分采用端點(diǎn)度仍不能區(qū)分的基本交線類(lèi)型，需要對(duì)存在度大于等于3的端點(diǎn)的交線類(lèi)型進(jìn)一步細(xì)分。本文根據(jù)此類(lèi)交線是為線目標(biāo)的端點(diǎn)還是中間點(diǎn)來(lái)進(jìn)一步細(xì)分。如該點(diǎn)為線目標(biāo)端點(diǎn)，則B中不存在與之相連的線段，用“null”表示；如該點(diǎn)為線目標(biāo)中間點(diǎn)，則B中存在相連線段，相連線段與面目標(biāo)A的拓?fù)潢P(guān)系仍存在在內(nèi)部（interior）、在外部（exterior）或在邊界上（on－boundary）3種類(lèi)型。

圖7 用結(jié)點(diǎn)度仍不能區(qū)分的單元交線類(lèi)型舉例Fig.7 Examples of the undistinguishable unit intersection segment using node－degree

因此本文在8種有意義的交線端點(diǎn)度組合情況的基礎(chǔ)上，對(duì)度為3和4的交線端點(diǎn)再次細(xì)分，用null、on－boundary、interior、exterior分別表示不存在相連線段、相連線段位于面的邊界、內(nèi)部和外部4種情況，組合得到有實(shí)際意義的21種線/面單元交線類(lèi)型，如圖8所示。

圖8 21種有意義的線/面單元交線類(lèi)型Fig.8 21refined topological intersection types between lines and polygons

4 比較分析與含多個(gè)交的線/面細(xì)分拓?fù)潢P(guān)系層次描述舉例

將圖8所示的21種有意義的線/面單元交線類(lèi)型與文獻(xiàn)［22］的定義線/面基本拓?fù)潢P(guān)系（后文稱(chēng)為現(xiàn)有方法）比較不難發(fā)現(xiàn)，兩種方法主要存在如下3點(diǎn)區(qū)別：

（1）基本拓?fù)潢P(guān)系（單元交線）定義不同：現(xiàn)有方法將線/面基本拓?fù)潢P(guān)系定義為“一條線和一個(gè)面邊界相交為0或1次的關(guān)系”；本文將線/面單元交線定義為“完全位于面的內(nèi)部，或完全位于面的邊界上，或僅有端點(diǎn)位于面的邊界上其余點(diǎn)全在面內(nèi)部的連續(xù)線段”。根據(jù)上述定義，前一種方法的基本拓?fù)潢P(guān)系不包含最常見(jiàn)的穿越關(guān)系，且基本交線劃分具有非唯一性。本文單元交線包含穿越交線，且單元交線劃分具有唯一性，符合人們的認(rèn)知習(xí)慣。

（2）在區(qū)分能力方面，本文基于結(jié)點(diǎn)度的線/面單元交線包括圖8所示的21種類(lèi)型，其中包含了現(xiàn)有方法所定義的10種基本交線類(lèi)型，更豐富了兩端點(diǎn)都在面的邊界上的穿越交線類(lèi)型。

（3）在描述方法方面，基于結(jié)點(diǎn)度的線/面單元交線可通過(guò)交線端點(diǎn)的結(jié)點(diǎn)度和null、onboundary、interior、exterior 4個(gè)謂詞來(lái)區(qū)分，現(xiàn)有方法通過(guò)定義基本交線順序號(hào)來(lái)區(qū)分，不便于交流。

從上述分析可看出，本文方法與現(xiàn)有方法相比，在基本交線類(lèi)型的定義、區(qū)分能力與描述方法方面都具有明顯優(yōu)勢(shì)。下面舉例說(shuō)明含多個(gè)交的復(fù)雜線/面拓?fù)潢P(guān)系的層次描述方法。

采用式（1）、式（2）所示的E－WID層次模型、圖8所示的21種線/面單元交線類(lèi)型和上述交點(diǎn)類(lèi)型可以詳細(xì)表達(dá)出簡(jiǎn)單線/面目標(biāo)之間的任意復(fù)雜拓?fù)潢P(guān)系。下面以圖9為例來(lái)說(shuō)明詳細(xì)描述方法。圖9（a）、圖9（b）都包含5個(gè)交，交的維數(shù)都包含0維點(diǎn)和1維線，A＼B和B＼A的維數(shù)和歐拉數(shù)都相同，因此R1所示的6元組完全相同。但圖9（a）、（b）中的2、3、4所示3個(gè)交的類(lèi)型卻不一樣，用結(jié)點(diǎn)度和“null、on－boundary、interior、exterior”（分別簡(jiǎn)寫(xiě)為N，D，I，E）4個(gè)謂詞可將這些交點(diǎn)、交線類(lèi)型完全區(qū)分開(kāi)來(lái)。

圖9 本文方法區(qū)分復(fù)雜線/面細(xì)分拓?fù)潢P(guān)系示例Fig.9 Examples of refined complex line/polygon topological relations distinguished by the proposed model

5 線/面細(xì)分拓?fù)潢P(guān)系應(yīng)用舉例

為了驗(yàn)證本文線/面拓?fù)潢P(guān)系細(xì)分模型與方法的有效性，以線狀道路與面狀河流為例分析了21種線/面單元交線與2種交點(diǎn)類(lèi)型的可能沖突類(lèi)型及相應(yīng)處理方法（可包含多種），發(fā)展了一套基于細(xì)分拓?fù)潢P(guān)系的沖突檢測(cè)與自動(dòng)（半自動(dòng)）化處理規(guī)則。采用自動(dòng)檢測(cè)沖突類(lèi)型、根據(jù)沖突類(lèi)型提供人機(jī)交互選擇自動(dòng)修正處理方法的模式，在課題組已開(kāi)發(fā)出的增量采編原型系統(tǒng)上，用Visual Studio 2008的C＃編程開(kāi)發(fā)了線/面拓?fù)潢P(guān)系的細(xì)分計(jì)算與基于細(xì)分關(guān)系的道路、面狀河流沖突檢測(cè)與處理原型系統(tǒng)，并用如圖10所示的實(shí)際數(shù)據(jù)驗(yàn)證了其有效性。

圖10是一幅從OpenStreetMap（OSM）上下載的老撾萬(wàn)象地區(qū)的道路與水系地形圖（圖1（a）為圖10紅色方框的局部放大圖）。圖中紫色線狀實(shí)體為道路，藍(lán)色面狀實(shí)體為面狀水體。用本文方法檢測(cè)出兩個(gè)圖層存在的圖8中的a類(lèi)交4個(gè)、c類(lèi)交1個(gè)、d類(lèi)交15個(gè)、g類(lèi)交1個(gè)、j類(lèi)交1個(gè)、o類(lèi)交9個(gè)、p類(lèi)交12個(gè)、t類(lèi)交2個(gè)。試驗(yàn)證明本文方法能夠提高沖突檢測(cè)與處理效率。

圖10 基于結(jié)點(diǎn)度的線/面細(xì)分拓?fù)潢P(guān)系應(yīng)用Fig.10 An applied example of node－degree based line/polygon topological relationship refinement model

6 結(jié)論與討論

線/面細(xì)分拓?fù)潢P(guān)系在空間數(shù)據(jù)更新、質(zhì)量檢查與分析應(yīng)用中具有重要作用，但現(xiàn)有的線/面細(xì)分拓?fù)潢P(guān)系模型在基本交線定義、區(qū)分能力與描述方法等方面都存在不足。本文針對(duì)上述問(wèn)題，在基于目標(biāo)整體交、差結(jié)果的歐拉數(shù)的E－WID層次模型的基礎(chǔ)上，引入結(jié)點(diǎn)度來(lái)區(qū)分線/面交的細(xì)分拓?fù)潢P(guān)系類(lèi)型，提出了一種基于結(jié)點(diǎn)度的線/面拓?fù)潢P(guān)系細(xì)分方法。該方法以單元交線的端點(diǎn)度為基礎(chǔ)，結(jié)合線目標(biāo)在度為3和4的交線端點(diǎn)處是否有相連線段、相連線段位于多邊形的邊界上、內(nèi)部和外部（分別用null、on－boundary、interior、exterior表示）4個(gè)謂詞，推導(dǎo)出21種線/面單元交線類(lèi)型。通過(guò)比較分析本文方法與現(xiàn)有方法，闡明了本文方法在單元交線劃分、區(qū)分能力與描述方法等方面都優(yōu)于現(xiàn)有方法。舉例說(shuō)明了在E－WID層次模型下用21種線/面單元交線類(lèi)型和基于結(jié)點(diǎn)度的交點(diǎn)類(lèi)型詳細(xì)描述簡(jiǎn)單線/面目標(biāo)之間任意復(fù)雜拓?fù)潢P(guān)系的方法，最后以實(shí)際數(shù)據(jù)驗(yàn)證了本文方法在空間數(shù)據(jù)質(zhì)量檢查與處理中的有效性。

應(yīng)該說(shuō)明的是，本文基于結(jié)點(diǎn)度的線/面拓?fù)潢P(guān)系細(xì)分方法是對(duì)基于目標(biāo)整體交、差結(jié)果的歐拉數(shù)的E－WID層次模型的補(bǔ)充和發(fā)展。另外，交線端點(diǎn)的度同樣可用來(lái)描述線目標(biāo)間單元交線的細(xì)分類(lèi)型。由于E－WID層次模型和本文基于結(jié)點(diǎn)度的交線細(xì)分方法中所用的集合操作（交、差）和拓?fù)洳蛔兞浚W拉數(shù)和結(jié)點(diǎn)度）都可用于三維空間，因此基于目標(biāo)整體交、差結(jié)果的歐拉數(shù)和結(jié)點(diǎn)度的三維拓?fù)潢P(guān)系模型將是本文的后續(xù)研究工作。

［1］EGENHOFER M J，F(xiàn)RANZOSA R D.Point－set Topological Spatial Relations［J］.International Journal of Geographical Information System，1991，5（2）：161－174.

［2］EGENHOFER M J，SHARMA J，MARK D M.A Critical Comparison of the 4－intersection and 9－intersection Models for Spatial Relations：Formal Analysis［C］∥Auto Carto11：Proceedings of the Eleventh International Symposium on Computer－assisted Cartography Autocarto Conference.［S.l.］：American Society for Photogrammetry and Remote Sensing，1993：1.

［3］CLEMENTINI E，F(xiàn)ELICE P D.A Comparison of Methods for Representing Topological Relationships［J］.Information Sciences：Applications，1995，3（3）：149－178.

［4］CLEMENTINI E，DI FELICE P D.Topological Invariants for Lines［J］.IEEE Transactions on Knowledge and Data Engineering，1998，10（1）：38－54.

［5］CHEN Jun，ZHAO Renliang，QIAO Chaofei.Voronoi Diagram＿Based GIS Spatial Analysis［J］.Geomatics and Information Science of Wuhan University，2003，28（sup1）：32－37.（陳軍，趙仁亮，喬朝飛.基于 Voronoi圖的GIS空間分析研究［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2003，28（sup1）：32－37.）

［6］CHEN J，LI C M，LI Z L，et al.A Voronoi－based 9－intersection Model for Spatial Relations［J］.International Journal of Geographical Information Science，2001，15（3）：201－220.

［7］LIZL，ZHAO RL，CHEN J.A Voronoi－based Spatial Algebra for Spatial Relations［J］.Progress in Natural Science，2002，12（7）：528－536.

［8］ZHOU X G，CHEN J，ZHAN F，et al.A Euler－numberbased Topological Computation Model for Land Parcel Database Updating［J］.International Journal of Geographical Information Science，2013，27（10）：1983－2005.

［9］ZHOU Xiaoguang，CHEN Jun.Computation of Topological Relations between Cadastral Objects Based on Euler－number［J］.Acta Geodaetica et Cartographica Sinica，2006，8（3）：291－298.（周曉光，陳軍.基于歐拉數(shù)的地籍拓?fù)潢P(guān)系計(jì)算［J］.測(cè)繪學(xué)報(bào)，2006，35（3）：291－298.）

［10］ZHOU Xiaoguang.Incremental Updating of Cadastral Database［M］.Beijing：Surveying and Mapping Press，2007.（周曉光.地籍?dāng)?shù)據(jù)庫(kù)增量更新［M］.北京：測(cè)繪出版社，2007.）

［11］ZHOU Xiaoguang，YUE Guosen，WEI Jinzhan.A Computation Method of Parcels’Topological Relations Based on Oracle Spatial［J］.Journal of Central South University：Science and Technology，2005，36（2）：317－322.（周曉光，岳國(guó)森，魏金占.基于Oracle Spatial的地籍地塊空間拓?fù)潢P(guān)系判斷［J］.中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，36（2）：317－322.）

［12］ZHOU Xiaoguang，CHEN Jun，JIANG Jie.Topological Relations between Parcels［J］.Acta Geodaetica et Cartographica Sinica，2003，32（4）：356－361.（周曉光，陳軍，蔣捷.地籍地塊間的空間拓?fù)潢P(guān)系［J］.測(cè)繪學(xué)報(bào)，2003，32（4）：356－361.）

［13］RANDELL D A，CUI Z，COHN A G.A Spatiallogicbased on Regions and Connection［C］∥Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning.San Francisco：Morgan Kaufmann，1992：165－176.

［14］CUI Z，COHN A G，RANDELL D A.Qualitative and Topological Relationships in Spatial Databases［C］∥Proceedings of the Third International Symposium on Advances in Spatial Data Bases.Singapore：Springer－Verlag，1993：293－315.

［15］COHN A G.Exploiting Temporal Continuity in Qualitative Spatial Calculi.［C］∥Spatial and Temporal Reasoning in Geographic Information Systems.New York：Oxford University Press，1998：5－24.

［16］EGENHOFER M J，F(xiàn)RANZOSA R.On the Equivalence of Topological Relations［J］.International Journal of Geographical Information Systems，1995，9：133－152.

［17］DENG M，CHENG T，CHEN X，et al.Multi－level Topological Relations between Spatial Regions Based upon Topological Invariants［J］.Geoinformatica，2007，11：239－267.

［18］GUO Qingsheng，DU Xiaochu，LIU Hao.Research on Quantitative Representation and Abstraction of Topological Relation between Two Regions［J］.Acta Geodaetica et Cartographica Sinica，2005，34（2）：123－128.（郭慶勝，杜曉初，劉浩.空間拓?fù)潢P(guān)系定量描述與抽象方法研究［J］.測(cè)繪學(xué)報(bào)，2005，34（2）：123－128.）

［19］GUO Qingsheng，CHEN Yujian，LIU Hao.Combinational Reasoning of Spatial Topological Relations between a Line and an Area［J］.Geomatics and Information Science of Wuhan University，2005，30（6）：529－532.（郭慶勝，陳宇箭，劉浩.線與面的空間拓?fù)潢P(guān)系組合推理［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30（6）：529－532.）

［20］DU S，WANG Q，GUO L.Modelling the Scale Dependences of Topological Relations between Lines and Regions Induced by Reduction of Attributes［J］.International Journal of Geographical Information Systems，2010，24：1649－1686.

［21］DU Xiaochu，HUANG Maojun.Description and Discrimination of Topological Relations between Uncertain Linear and Area Object［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：340－350.（杜曉初，黃茂軍.不確定線－面拓?fù)潢P(guān)系的描述與判別［J］.測(cè)繪學(xué)報(bào)，2007，36（3）：340－350.）

［22］DENG Min，MA Hangying.The Hierarchical Representation of Topological Relations between a Line and an Area［J］.Acta Geodaetica et Cartographica Sinica，2008，37（4）：507－513.（鄧敏，馬杭英.線與面目標(biāo)間拓?fù)潢P(guān)系的層次表達(dá)方法［J］.測(cè)繪學(xué)報(bào)，2008，37（4）：507－513.）

［23］WU Changbin，LüGuonian.Detail Representation and Calculation Method of Topological and Metric Relationships between Line and Region［J］.Journal of Computer－aided Design ＆ Computer Graphics，2009，21（11）：1551－1556.（吳長(zhǎng)彬，閭國(guó)年.線面拓?fù)浜投攘筷P(guān)系的細(xì)分描述和計(jì)算方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，21（11）：1551－1556.）

［24］HU Jiaji.Operations Research［M］.Changsha：Central South University Press，1987.（胡家驥.運(yùn)籌學(xué)［M］.長(zhǎng)沙：中南工業(yè)出版社，1987.）

［25］WANG Yongxian.Operations Research：Programming Theory and Network［M］.Beijing：Tsinghua University Press，1993.（王永縣.運(yùn)籌學(xué)：規(guī)劃論及網(wǎng)絡(luò)［M］.北京：清華大學(xué)出版社，1993.）