平面分割的線／線相接、交叉類型判斷

陳 斐，周曉光

中南大學(xué) 地球科學(xué)與信息物理學(xué)院，湖南 長(zhǎng)沙410083

1 引 言

線目標(biāo)間存在多種空間拓?fù)潢P(guān)系約束條件，是數(shù)據(jù)組織、更新與一致性檢查的基礎(chǔ)［1－2］。例如在空間數(shù)據(jù)增量更新中，河流往往相對(duì)穩(wěn)定，道路為基礎(chǔ)設(shè)施，發(fā)展迅速。新修道路后，一般通過外業(yè)測(cè)量新增道路的空間位置，再通過與已有地圖數(shù)據(jù)進(jìn)行疊加，通過拓?fù)潢P(guān)系計(jì)算、語義規(guī)則等方法來處理一致性沖突、構(gòu)建變化后的河流等。如新修道路與已有河流間如存在“交叉”關(guān)系則被認(rèn)為是存在沖突，需要插入橋梁或隧道等符號(hào)；而存在“相接”關(guān)系在某些比例尺中則是合理的。道路和較小河流在中小比例尺中常用線目標(biāo)來表達(dá)，如在圖1中（見文末），亮紅色線表示更新后的道路，綠色線表示已有地圖中的河流。圖1（a）、圖1（c）表示的是“交叉”關(guān)系，表示道路跨越了河流，需要插入橋梁或隧道符號(hào)。圖1（b）表示的是“相接”關(guān)系，可能是合理關(guān)系，或道路與河流平行，由于表達(dá)的尺度和精度等原因?qū)е碌缆放c河流重疊。因此線目標(biāo)間的相接、交叉關(guān)系的區(qū)分在空間更新與質(zhì)量控制處理中有著重要作用。

圖1中的道路跨越河流的拓?fù)潢P(guān)系在目前通用的4I、9I模型中都表達(dá)為“內(nèi)部／內(nèi)部”有交，但“內(nèi)部／內(nèi)部”有交又包括多種細(xì)分情況，如交點(diǎn)的“相接”、“交叉”，交線的“相接”、“交叉”等，而4I、9I模型不能區(qū)分上述細(xì)分情況。

近年來，隨著拓?fù)潢P(guān)系研究與應(yīng)用的深入發(fā)展，國(guó)內(nèi)外多位學(xué)者在線／線拓?fù)潢P(guān)系的分類與細(xì)化計(jì)算方面開展了大量的研究工作，取得了可喜的研究成果。文獻(xiàn)［3］對(duì)線／線交進(jìn)行了相接、交叉類型的細(xì)化分類，但未給出具體計(jì)算算法。文獻(xiàn)［4］提出了線線空間關(guān)系描述的拓?fù)滏溎Ｐ团c線目標(biāo)間拓?fù)潢P(guān)系的細(xì)化計(jì)算方法，其中涉及線／線交的相接、交叉的計(jì)算算法，但該方法僅適用于交點(diǎn)的相接、交叉關(guān)系的判斷，不能計(jì)算交線的相接、交叉類型。文獻(xiàn)［5］提出的線目標(biāo)間拓?fù)潢P(guān)系細(xì)化計(jì)算的分解一組合方法，將線分解，計(jì)算局部拓?fù)潢P(guān)系，再將局部拓?fù)潢P(guān)系按照一定順序組成拓?fù)滏渷肀磉_(dá)線線之間的拓?fù)潢P(guān)系，此方法不能判斷相接交線與交叉交線。文獻(xiàn)［6］提出的GIS線目標(biāo)間空間關(guān)系的集成表達(dá)方法，建立一個(gè)綜合描述線目標(biāo)拓?fù)?、方向、距離關(guān)系的方法，此模型中涉及多種空間關(guān)系的度量，描述復(fù)雜，不易于交流。而在Oracle空間數(shù)據(jù)庫(kù)中應(yīng)用廣泛的空間線線拓?fù)潢P(guān)系也只給出了11種基本空間拓?fù)潢P(guān)系查詢的操作算子，文獻(xiàn)［7］提出的基于Oracle Spatial的空間線線拓?fù)潢P(guān)系判斷的實(shí)現(xiàn)，描述了33種線線空間關(guān)系，但并不包括相接、交叉分類［3－22］。

總之，目前盡管在線／線拓?fù)潢P(guān)系的描述、區(qū)分與細(xì)化計(jì)算方面取得了可喜的研究成果，但仍缺少線／線“相接”“交叉”細(xì)化類型的判斷算法，不能滿足數(shù)據(jù)更新、數(shù)據(jù)質(zhì)量檢查等對(duì)拓?fù)潢P(guān)系細(xì)化計(jì)算的應(yīng)用需求。因此本文提出一種基于局部平面分割的線／線交點(diǎn)和交線的相接、交叉類型的判斷算法。該算法采用局部平面分割的基本思想，在線／線交的鄰域內(nèi)，一條線將鄰域平面分割成兩個(gè)平面區(qū)域，通過判斷另一條線中與交相連的兩線段是否處于同一個(gè)平面區(qū)域，確定該交的相接、交叉類型。

2 基于局部平面分割的線／線相接、交叉類型的判斷原理

文獻(xiàn)［3］將線／線交的相接、交叉類型定義為：兩線lA、lB相交，如圖2所示（粗直線表示lA，細(xì)虛線表示lB），構(gòu)建交的鄰域，在交的鄰域內(nèi)，將與交點(diǎn)（線）相連的線段按順時(shí)針排序，得出線段序列T（k）＝（a1，a2，a3，a4）。如果同一線目標(biāo)中的兩線段在該序列中不相鄰，稱為交叉交類型，如圖2（a）、（b）所示，a1、a3屬于線lA，a2、a4屬于線lB；如果同一線目標(biāo)中的兩線段在該序列中相鄰，稱為相接交類型，如圖2（c）、（d）所示，即a1、a2屬于線lA，a3、a4屬于線lB［2］。

圖2 線／線交的相接、交叉定義示意圖Fig.2 Examples of the crossing and touching intersection types

通過分析圖2，發(fā)現(xiàn)交的鄰域總會(huì)被線目標(biāo)分割。如圖2中l(wèi)A總是把鄰域分成兩個(gè)平面區(qū)域，lB中與交相連的兩線段總會(huì)落在這兩個(gè)平面區(qū)域內(nèi)。而且在交叉交的鄰域內(nèi)，T（k）中l(wèi)A、lB與交相連的線段序列相互交叉，lB中的兩線段處于兩個(gè)不同的平面區(qū)域。在相接交的鄰域內(nèi)，lB中的兩線段落在同一平面區(qū)域。因此，如果可以判斷l(xiāng)B中與交相連的兩線段是否被lA分割到同一平面區(qū)域，就可以判斷交的相接、交叉類型，這就是局部平面分割的思想。

應(yīng)用于局部平面分割的計(jì)算幾何原理是由矢量叉積的性質(zhì)推出的。性質(zhì)描述為：設(shè)向量M、Q，若M×Q＞0，則M在Q的順時(shí)針方向。若M×Q＜0，則M在Q的逆時(shí)針方向。若M×Q＝0，則M與Q共線，但可能同向也可能反向。

根據(jù)上述定理求已知坐標(biāo)的兩點(diǎn)B1、B2是否被已知線段lA1A2分割到同一平面區(qū)域，可以判斷矢量叉積的符號(hào)是否相同，總結(jié)為式（1）

此時(shí)，如果Side（lA1A2，B1，B2）值為true，那么B1、B2在線段的同一側(cè)，即分割到同一平面區(qū)域。這一方程可以直接應(yīng)用到最簡(jiǎn)單的平面分割情況——點(diǎn)A1、A2與交點(diǎn)P在一直線上時(shí)（如圖2（a）所示），直接判斷矢量之間的關(guān)系。

如果點(diǎn)A1、A2與交點(diǎn)P不在一直線上時(shí)，即折線段lA1PA2將鄰域分割成兩個(gè)平面區(qū)域Ⅰ、Ⅱ，如圖3（a）。向量及其延長(zhǎng)線將鄰域分割成ⅰ、ⅱ、ⅲ、ⅳ4個(gè)輔助性區(qū)域，如圖3（b），此時(shí)區(qū)域Ⅰ與輔助性的區(qū)域ⅰ完全相等，選取將這一獨(dú)立的輔助性區(qū)域（ⅰ區(qū)或Ⅰ區(qū)）內(nèi)的一點(diǎn)——例如A1、A2的中點(diǎn)PZ，作為參考點(diǎn)，向量叉積的正負(fù)符號(hào)就代表了Ⅰ區(qū)內(nèi)任一以點(diǎn)P為起點(diǎn)的向量與與叉積的結(jié)果。如果判斷是否在同一平面區(qū)域，只需要將與作比較，分別判斷與是否在同一區(qū)域，當(dāng)都在同一區(qū)域或都不在同一區(qū)域時(shí)，交點(diǎn)是相接交，否則是交叉交。以判斷是否在同一區(qū)域?yàn)槔?，總結(jié)為式（2）

圖3 折線段分割局部平面的計(jì)算原理Fig.3 The calculation principle of segment splitting the disc

利用式（1）和式（2）可以計(jì)算所有相接／交叉的交點(diǎn)類型。而交線的鄰域中存在更復(fù)雜的平面分割，如圖2（b）、（d）。此時(shí)需要進(jìn)行簡(jiǎn)化。如果分別以交線的首尾節(jié)點(diǎn)P1、P2為圓心做輔助性的節(jié)點(diǎn)圓形鄰域，如圖4（a）、（b），那么在每一個(gè)節(jié)點(diǎn)圓形鄰域內(nèi)，線lA都將鄰域圓分割為兩個(gè)不同的區(qū)域。引入交線的方向P1→P2，被分割的平面區(qū)域統(tǒng)一就歸納為lP1→P2的左側(cè)區(qū)域與lP1→P2的右側(cè)區(qū)域。此時(shí)，利用上述分割定理分別確定處于節(jié)點(diǎn)圓鄰域中的左側(cè)區(qū)域還是右側(cè)區(qū)域，就可以判斷B1、B2是否處于lP1→P2的同一側(cè)。

圖4 交線相接／交叉類型的計(jì)算方法Fig.4 The method of dividing line intersections into touching and crossing

3 線線交的相接／交叉類型規(guī)則

3.1 交點(diǎn)相接／交叉類型計(jì)算規(guī)則

假設(shè)：線lA、lB相交于點(diǎn)P，lA中與點(diǎn)P相連的形狀點(diǎn)為A1、A2，lB中與點(diǎn)P相連的形狀點(diǎn)為B1、B2。

此時(shí)，基于上述理論，在線／線交點(diǎn)的鄰域中，選取lA將鄰域分割為兩個(gè)平面區(qū)域。由于分割線的類型不同，使用的原理也不同。所以，先判斷l(xiāng)A在鄰域內(nèi)的部分是否是直線段。判斷方法：交點(diǎn)P是否是lA的形狀點(diǎn)。

如果P不是lA的形狀點(diǎn)，那么lA在鄰域內(nèi)的部分是直線段。將矢量代入式（1），判斷的值，如果Side（lPA2，B1，B2）＝true，那么B1、B2在被分割到同一平面區(qū)域，交點(diǎn)P是相接；如果那么B1、B2被分割到不同平面區(qū)域，交點(diǎn)P是交叉?？偨Y(jié)為規(guī)則一。

規(guī)則1：P不是形狀點(diǎn)

如果Side（lPA2，B1，B2）值為真，那么交點(diǎn)P是相接交，否則交點(diǎn)P是交叉交。

如果P是lA的形狀點(diǎn)，計(jì)算lA1A2的中點(diǎn)PZ，分 別 將代 入 式（2），如果Side（lAPA，B1，PZ）＝true，那么B1與點(diǎn)PZ

12被分割到同一平面區(qū)域。同理，如果那么B2與點(diǎn)PZ被分割到同一平面區(qū)域。如果B1、B2被分割到同一平面區(qū)域，那么交點(diǎn)P是相接。如果B1、B2被分割到不同平面區(qū)域，那么交點(diǎn)P是交叉?？偨Y(jié)為規(guī)則2。

規(guī)則2：P是形狀點(diǎn)

如果Side（，B1，PZ）∧Side（lAPA，B2，12PZ）值為真，那么交點(diǎn)P是交叉交，否則交點(diǎn)P是相接交。

3.2 交線相接＼交叉類型計(jì)算規(guī)則

假設(shè)：線lA、lB相交于線lP1P2，交線lP1P2的端點(diǎn)是P1、P2，lA中分別與點(diǎn)P1、P2相連的形狀點(diǎn)為A1、A2，lB中分別與點(diǎn)P1、P2相連的形狀點(diǎn)為B1、B2。

此時(shí)，可以利用直線分割平面原理進(jìn)行計(jì)算。引入lA的方向，交線的方向P1→P2，這兩個(gè)方向必須完全一致。此時(shí)，在P1的節(jié)點(diǎn)圓形鄰域中確認(rèn)B1的左右位置，在P2的節(jié)點(diǎn)圓形鄰域中確認(rèn)B2的左右位置，就可以求出B1相對(duì)lA的左右位置的值，用 Right（lA，B1）表示，值為布爾型，B1在lA的右側(cè)時(shí)值為真，B2相對(duì)lA的左右位置Right（lA，B2），就可以總結(jié)出交線lP1P2的類型。

以求點(diǎn)B1的位置為例，查找交線中與P1相連的節(jié)點(diǎn)Pf，第一步同樣是判斷A1→P1→Pf是否是一直線段。判斷方法可以采用：判斷交線節(jié)點(diǎn)P1是否是lA的形狀點(diǎn)。

如果P1不是lA的形狀點(diǎn)，那么lA在節(jié)點(diǎn)鄰域鄰域內(nèi)的部分是直線段，根據(jù)的叉積結(jié)果判斷與向量（與P1→P2的方向一致）的左右關(guān)系，如果那么Right（lA，B1）＝True在lA的右側(cè)。

規(guī)則3：P不是形狀點(diǎn)

如果P1是lA的形狀點(diǎn)，此時(shí)求B1與的左右關(guān)系。求出A1、Pf的中點(diǎn)，將向量代入式（2），求出的值，確認(rèn)與是否分布在同一區(qū)域。根據(jù)規(guī)則3計(jì)算PZ1與有向線lA的左右位置關(guān)系

？true：false。如果B1與點(diǎn)被分割到同一平面區(qū)域，B1與點(diǎn)PZ1所處的左右位置關(guān)系相同；如果B1與點(diǎn)PZ1被分割到不同的平面區(qū)域，B1與點(diǎn)PZ1所處的左右位置關(guān)系相反?？偨Y(jié)為規(guī)則4。

規(guī)則4：P是形狀點(diǎn)

如果 Side（，B1，PZ）值為真，那么1Right（lA，B1）＝Right（lA，PZ1），否則 Right（lA，B1）＝﹁Right（lA，PZ1）；同理可以判斷B2，查找交線中與P2相連的節(jié)點(diǎn)Pl，計(jì)算的關(guān)鍵在于統(tǒng)一交線的方向，即確定Pl→P2→A2的方向與P1→P2的方向一致。這樣才能確保求得的B1、B2的左右位置是絕對(duì)的。最后，總結(jié)B1、B2的左右位置得出交線的類型，總結(jié)為規(guī)則5。

規(guī)則5：如果 Right（lA，B1）∧Right（lA，B2）值為真，那么交線lP1P2是交叉交，否則交線lP1P2是相接交。

4 試驗(yàn)實(shí)現(xiàn)

總結(jié)3.1與2.2，可以將線線交的相接＼交叉類型計(jì)算歸納如下。

假設(shè)：線lA與線lB，求出兩線的交類型。函數(shù)Inter（lA，lB）為求線lA與線lB的交。定義PZ為變量點(diǎn)對(duì)（q1，q2）的中點(diǎn)；定義lA的節(jié)點(diǎn)與形狀點(diǎn)為點(diǎn)集shapept。Right（lA，B1）是求點(diǎn)B1與有向線lA的左右方向的函數(shù)，值為布爾型，B1在lA的右側(cè)時(shí)值為真。

（1）Inter（lA，lB）得出交集，其中交點(diǎn)集為Pt，交線集為L(zhǎng)ine。

（2）求交點(diǎn)集Pt中的每一個(gè)元素Pt［i］的相接＼交叉類型。查找lA中與Pt［i］相連的節(jié)點(diǎn)A1、A2，lB中與 Pt［i］相連的節(jié)點(diǎn)B1、B2。如果Pt［i］與shapept中的元素相等，令PZ為（A1，A2）的中點(diǎn)，進(jìn)行 Side（，B1，PZ）∧Side運(yùn)算，值為真時(shí)點(diǎn)Pt［i］是交叉，值為假時(shí)點(diǎn)Pt［i］是相接，利用規(guī)則一求出Pt［i］的類型；如果Pt［i］與shapept中的元素全不相等，進(jìn)行Side（，B1，B2）運(yùn)算，值為真時(shí)點(diǎn) Pt［i］是相接，值為假時(shí)點(diǎn)Pt［i］是交叉。

（3）求交線集Line中的每一個(gè)元素的類型。計(jì)算的流程總結(jié)如圖5所示。其中，Line［i］表示交線集Line中元素，頭結(jié)點(diǎn)為P1，尾節(jié)點(diǎn)為P2。A1是lA中與P1相連的節(jié)點(diǎn)，Pf是Line［i］中與P1相連的節(jié)點(diǎn)，B1是lB中與P1相連的節(jié)點(diǎn)。如果P1→A1→Pf在一條直線上，即P1是形狀點(diǎn)shapept，利用規(guī)則3求出B1的左右位置，其中l(wèi)A1Pf表示由點(diǎn)A1→Pf的有向線段。否則，令PZ為（P1，Pf）的中點(diǎn)，利用規(guī)則4求出B1的左右位置，其中l(wèi)A1P1，lP1Pf表示由點(diǎn)P1、A1與P1、Pf構(gòu)成的兩條直線段。lA中與P2相連的節(jié)點(diǎn)是A2，Line［i］中與P2相連的節(jié)點(diǎn)是Pl，lB中與P2相連的節(jié)點(diǎn)是B2。如果Pl→P2→A2在一條直線上，利用規(guī)則3求出B2的左右位置；否則，令PZ為（P2，Pl）的中點(diǎn)，利用規(guī)則4求出B2的左右位置。最后規(guī)則5求出Line［i］的類型。

圖1 道路線與河流線相交的3種細(xì)分類型Fig.1 Three intersection types including between rivers and roads

圖5 交線相接＼交叉計(jì)算流程Fig.5 Calculation flow chart of dividing intersections into touching and crossing

為了驗(yàn)證本文的方法與模型，在增量采編原型系統(tǒng)上，用Visual Studio 2008的C＃編程實(shí)現(xiàn)了基于局部平面分割的線／線交相接、交叉類型計(jì)算方法。

圖6是一幅1∶25萬中國(guó)行政區(qū)道路與河流網(wǎng)地形圖的局部，其中，道路經(jīng)過更新，圖中紅色的線表示更新后的道路，綠色線表示河流。選取這一條更新后的道路線（紅色粗實(shí)線），與一條相交的河流線（深綠色粗實(shí)線），用本文提出的方法計(jì)算了該道路線與該河流線之間相接、交叉交的類型，并且分別用藍(lán)色高亮顯示相接交與交叉交。計(jì)算結(jié)果如圖6所示，（a）圖中高亮顯示了兩條線的交叉交，包括一條交線與兩個(gè)交點(diǎn)，（b）圖中高亮顯示了兩條線的相接交，只有一個(gè)交點(diǎn)。試驗(yàn)驗(yàn)證了本文計(jì)算方法的正確性?？梢栽谂袛嘞嘟?、交叉類型的基礎(chǔ)上進(jìn)行下一步處理，在交叉交的位置按照實(shí)際情況插入跨河的橋梁或隧道。

圖6 試驗(yàn)實(shí)例圖Fig.6 Data of test

5 結(jié) 論

論文闡述了直線分割平面的計(jì)算原理，根據(jù)幾何代數(shù)中直線分割平面定理，按照一條直線分割平面、兩條相交直線分割平面和有向直線段分割平面3種情況推導(dǎo)出3個(gè)原理方程；提出了計(jì)算交相接／交叉類型時(shí)的5條規(guī)則，分別適用于交點(diǎn)鄰域中的兩種不同的分割情況和交線頭尾節(jié)點(diǎn)鄰域中的兩種不同的分割情況；給出了線線交叉、相接交分類計(jì)算的算法流程。最后，在數(shù)據(jù)更新系統(tǒng)平臺(tái)中用Visual Studio 2008的C＃編程實(shí)現(xiàn)了該方法，并以中國(guó)道路與河流網(wǎng)為實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了試驗(yàn)，驗(yàn)證了算法的正確性。

目前在拓?fù)潢P(guān)系描述區(qū)分方面的模型較多，但在拓?fù)潢P(guān)系細(xì)化計(jì)算方面的成果仍不能滿足應(yīng)用需求。因此本文的后續(xù)研究工作包括：①將繼續(xù)研究線線拓?fù)潢P(guān)系的其他細(xì)化算法，并考慮將線線交叉、相接細(xì)分類型判斷算法應(yīng)用到線面拓?fù)潢P(guān)系的細(xì)化計(jì)算中；②探索線線交叉、相接細(xì)分類型的實(shí)際應(yīng)用，如，GIS不同類型線要素間具有交叉、相接關(guān)系類型在數(shù)據(jù)庫(kù)更新中所對(duì)應(yīng)的目標(biāo)重構(gòu)與更新處理方法，在數(shù)據(jù)質(zhì)量控制中對(duì)應(yīng)的沖突類型與處理算法等。

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

［2］ XING Hanfa，ZHOU Xiaoguang.Local Contour Line Fusion Based on Line／Line Topological Relations［J］.Geomatics and Information Science of Wuhan University，2010，35（11）：1322－1326.（邢漢發(fā)，周曉光.基于線／線拓?fù)潢P(guān)系的局部變化等高線融合［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2010，35（11）：1322－1326.）

［3］ CLEMENTINI E，DIFELICE P.Topological Invariants for Lines［J］.IEEE Transactions on Knowledge and Data Engineering，1998，10：38－54.

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

［5］ CHEN Jun，LIU Wanzeng，LI Zhilin.The Refined Calculation Method of Topological Relationships between Line Objects［J］.Acta Geodaetica et Cartographica Sinica，2006，35（3）：255－260.（陳軍，劉萬增.線目標(biāo)間拓?fù)潢P(guān)系的細(xì)化計(jì)算方法［J］.測(cè)繪學(xué)報(bào)，2006，35（3）：255－260）

［6］ DENG Min，LI Zhilin.An Integrated Approach to Representing Line－line Spatial Relations in GIS［J］. Acta Geodaetica et Cartographica Sinica，2007，36（4）：421－427.（鄧敏，李志強(qiáng).GIS線目標(biāo)間空間關(guān)系的集成表達(dá)方法［J］.測(cè)繪學(xué)報(bào)，2007，36（4）：421－427.）

［7］ WANG Lijiang，YUE Guoshen.The Realization of Differentiating Spatial Topological Relations between Lines Based on Oracle Spatial［J］.Acta Geodaetica et Cartographica Sinica，2006，35（1）：78－82.（王禮江，岳國(guó)森.基于Oracle Spatial的空間線線拓?fù)潢P(guān)系判斷的實(shí)現(xiàn)［J］.測(cè)繪學(xué)報(bào)，2006，35（1）：78－82.）

［8］ LIU Wanzeng，CHEN Jun.A Topology Chain Model for Describing Line－line Spatial Relations［J］.Journal of China University of Mining ＆ Technology，2010，39（1）：75－79.（劉萬增，陳軍.線線空間關(guān)系描述的拓?fù)滏溎Ｐ停跩］.中國(guó)礦業(yè)大學(xué)學(xué)報(bào)，2010，39（1）：75－79.）

［9］ NI Jianhua，ZHOU Xiaoguang.The Computation of Basic Line／Line Topological Relations Based on Line Segment［J］.Geomatics World，2009，10（5）：39－43.（倪建華，周曉光.基于線段的基本線／線拓?fù)潢P(guān)系計(jì)算［J］.地理信息世界，2009，10（5）：39－43.）

［10］ LIU Wanzeng，CHEN Jun.Automatic Detection of Spatial Conflicts between Line Objects［J］.Journal of China University of Mining ＆ Technology，2006，35（6）：767－771.（劉萬增，陳軍.線目標(biāo)空間沖突自動(dòng)檢測(cè)方法研究［J］.中國(guó)礦業(yè)大學(xué)學(xué)報(bào)，2006，35（6）：767－771.

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

［12］ EGENHOFER M.A Model for Detailed Binary Topological Relations［J］.Geomatica，1993，47：261－273.

［13］ MAX J.Modeling Conceptual Neighborhoods of Topological Line－Region Relations ［J］.International Journal of Geographical Information Science，1995，9（5）：555－565.

［14］ NEDAS K A，EGNHOFER M J.Metric Details of Topological Line－line Relations［J］.International Journal of Geographical Information Science，2007，1（21）：21－48.

［15］ 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.

［16］ LI S.A Complete Classification of Topological Relations Using the 9－intersection Method［J］，International Journal of Geographical Information Science，2006，20：589－610.

［17］ LI S，LIU W.Topological Relations between Convex Regions［J］.Proceedings of the Twenty－fourth AAAI Conference on Artificial Intelligence，2010，AAAI－10：321－326.

［18］ CHEN J，LIU W.Detection of Spatial Conflicts between Rivers and Contours in Digital Map［J］.International Journal of Geographical Information Science，2007，21（10）：1093－1114.

［19］ CHEN Jun，ZHAO Renliang.Spatial Relations in GIS：A Survey on Its Key Issues and Research Progress［J］.Acta Geodaetica et Cartographica Sinica，1999，28（2）：95－102.（陳軍，趙仁亮.GIS空間關(guān)系的基本問題與研究進(jìn)展［J］.測(cè)繪學(xué)報(bào)，1999，28（2）：95－102.）

［20］ DENG Min，ZHAO Binbin，XU Zhen.Representation Methods of Distance between Spatial Objects in GIS and Their Analysis［J］.Computer Engineering and Applications，2011，47（1）：35－39.（鄧敏，趙彬彬，徐震.GIS空間目標(biāo)間距離表達(dá)方法及分析［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（1）：35－39.）

［21］ LIU Wanzeng，CHEN Jun.Detecting the Spatial Inconsistency between the Updated Rivers and Valleys［J］.Journal of Image and Graphics，2008，13（5）：1003－1008.（劉萬增，陳軍.數(shù)據(jù)庫(kù)更新中河流與山谷線一致性檢測(cè)［J］.中國(guó)圖象圖形學(xué)報(bào)，2008，13（5）：1003－1008.）

［22］ ZHOU P.Calculating Geometry：Design and Analysis of Arithmetic ［M］.Beijing：Tsinghua University Press，2011.（周培德.計(jì)算幾何－－算法設(shè)計(jì)與分析［M］.北京：清華大學(xué)出版社，2011.）