楊宜舟，吳立新，2，＊，郭甲騰，李志鋒，劉善軍

（1.東北大學(xué)測(cè)繪遙感與數(shù)字礦山研究所，遼寧 沈陽 110819；2.中國礦業(yè)大學(xué)物聯(lián)網(wǎng)（感知礦山）國家地方聯(lián)合工程實(shí)驗(yàn)室，江蘇 徐州 221008；3.北京師范大學(xué)民政部／教育部減災(zāi)與應(yīng)急管理研究院，北京 100875）

0 引言

雖然近年計(jì)算機(jī)計(jì)算能力迅速提高，尤其是多核計(jì)算機(jī)和并行計(jì)算機(jī)開始普及，但傳統(tǒng)GIS的串行算法卻難以充分利用這些先進(jìn)的計(jì)算資源［1］。如何充分利用這些新的計(jì)算資源解決更復(fù)雜的實(shí)際應(yīng)用，已成為目前十分關(guān)注的問題。在信息領(lǐng)域，并行計(jì)算為協(xié)同利用更多的計(jì)算資源提供了新的手段，實(shí)現(xiàn)了利用多個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算資源來提高計(jì)算能力［2］，為GIS高效處理大規(guī)?？臻g數(shù)據(jù)提供了理論和技術(shù)支撐。目前，GIS領(lǐng)域柵格數(shù)據(jù)并行算法研究較多［3－5］，而矢量數(shù)據(jù)并行算法主要關(guān)于空間分析，如最短路徑分析［6，7］、疊加分析［8］等，關(guān)于空間關(guān)系（度量關(guān)系、方向關(guān)系、拓?fù)潢P(guān)系）的并行算法研究幾乎空白。

并行算法中影響算法效率的重要方面是并行計(jì)算過程中的任務(wù)均衡與負(fù)載均衡，而影響任務(wù)均衡與負(fù)載均衡最基礎(chǔ)也最重要的因素是數(shù)據(jù)集劃分?？臻g數(shù)據(jù)劃分策略在空間數(shù)據(jù)管理中發(fā)揮著重要作用［9］，尤其是對(duì)矢量并行算法整體性能的提高至關(guān)重要。目前針對(duì)關(guān)系型數(shù)據(jù)集的劃分方法主要有輪轉(zhuǎn)劃分法［1，2］、范圍劃分法［10］、散列劃分法［11］、混合劃分法［12］等，但這些數(shù)據(jù)劃分方法針對(duì)的是數(shù)據(jù)集的屬性特征，未顧及空間數(shù)據(jù)的特點(diǎn)，采用這些數(shù)據(jù)劃分方法會(huì)導(dǎo)致并行計(jì)算的任務(wù)不均衡。目前針對(duì)空間數(shù)據(jù)的劃分方法主要是空間曲線劃分法［13－15］，如Hilbert曲線劃分［14］、Z曲線劃分等，但這些劃分方法均不能針對(duì)拓?fù)潢P(guān)系算法的特點(diǎn)來保障拓?fù)潢P(guān)系并行算法中各進(jìn)程的任務(wù)均衡與負(fù)載均衡，影響了計(jì)算效率。因此，本文在分析拓?fù)潢P(guān)系計(jì)算特點(diǎn)的基礎(chǔ)上，提出顧及拓?fù)潢P(guān)系并行計(jì)算的任務(wù)均衡與負(fù)載均衡的空間數(shù)據(jù)劃分方法。

1 拓?fù)潢P(guān)系原理與計(jì)算

1.1 拓?fù)潢P(guān)系基本原理

拓?fù)潢P(guān)系是空間目標(biāo)在延展、移動(dòng)、旋轉(zhuǎn)等變換下保持不變的一種定性關(guān)系，在空間數(shù)據(jù)組織、分析、查詢等方面有著十分重要的作用。拓?fù)潢P(guān)系在空間推理和空間查詢上也扮演著非常重要的角色，是GIS的重要特征。很多學(xué)者在空間拓?fù)潢P(guān)系描述模型方面進(jìn)行了大量的探討和研究，常見的空間關(guān)系描述模型有：基于點(diǎn)集理論的描述模型（4－交模型［16］與9－交模型［17］）、基于RCC理論的描述模型［18］、基于 Voronoi圖的9－交模型［19］等?；邳c(diǎn)集理論的9－交模型是當(dāng)前最為常用的拓?fù)潢P(guān)系分析和計(jì)算模型，具有廣泛的適用范圍和較高的計(jì)算效率，相比其它兩種描述模型更適合于高性能拓?fù)潢P(guān)系的計(jì)算（表1）。

表1 三類拓?fù)潢P(guān)系描述模型的比較Table 1 Comparison for three kinds of topology models

基于點(diǎn)集理論的拓?fù)潢P(guān)系描述模型的原理為：矢量空間目標(biāo)分解成邊界、內(nèi)部和外部3部分，構(gòu)成一個(gè)用于描述拓?fù)潢P(guān)系的3×3相交矩陣。本文采用開放地理信息系統(tǒng)協(xié)會(huì)（Open GIS Consortium，OGC）基于點(diǎn)集理論維度擴(kuò)展的9交模型（Dimensionally Extended Nine－Intersection Model，DE－9IM），作為描述簡(jiǎn)單要素間拓?fù)潢P(guān)系的模型［18］。DE－9IM的數(shù)學(xué)表達(dá)式為：

式中：A°、A和A－（B°、B、和B－）分別表示實(shí)體A（B）的內(nèi)部、邊界和外部；dim（P）為計(jì)算矩陣元素值最大值維度的函數(shù)，其中P為空間目標(biāo)相交的結(jié)果元素。求維函數(shù)的取值范圍為｛－1，0，1，2｝，其定義如下：

1.2 拓?fù)潢P(guān)系算法

基于DE－9IM，OGC定義了8種空間拓?fù)潢P(guān)系接口和一個(gè)判斷給定拓?fù)潢P(guān)系類型的接口，這8種空間關(guān)系之間存在一定的轉(zhuǎn)化和包含關(guān)系，具體含義描述如下：

根據(jù)這8種拓?fù)潢P(guān)系間的聯(lián)系，可確定一個(gè)最小覆蓋關(guān)系集，其中包含5種關(guān)系類型：disjoints（相離）、touches（相接）、overlaps（疊加）、within／contains（包含）和crosses（穿越）。這5種關(guān)系能對(duì)所有的空間關(guān)系構(gòu)成一個(gè)完整的覆蓋，它們是基本的、互斥的［18］。根據(jù)這5種基本的關(guān)系集，判斷計(jì)算兩個(gè)空間幾何體間拓?fù)潢P(guān)系的過程可以采用空間決策樹表示?？臻g決策樹能提高兩個(gè)空間目標(biāo)間拓?fù)潢P(guān)系的計(jì)算效率，達(dá)到快速、準(zhǔn)確地判斷拓?fù)潢P(guān)系的目的。

1.3 拓?fù)潢P(guān)系并行算法及其特點(diǎn)

現(xiàn)有并行編程模型可分為3類［20］：消息傳遞模型、共享存儲(chǔ)模型和數(shù)據(jù)并行模型。消息傳遞模型是目前使用最為廣泛的并行模型，有兩大優(yōu)勢(shì)：1）消息傳遞程序具有高度的可移植性，理論上可在任何并行機(jī)上執(zhí)行，即不需要特殊的硬件支持；2）允許用戶顯式地控制并行程序中每個(gè)進(jìn)程內(nèi)存的使用，為編程人員實(shí)現(xiàn)高性能計(jì)算提供便利。其并行程序開發(fā)模式通常有兩種：SPMD（Single Program Multiple Data，單程序多數(shù)據(jù)）模式和MPMD（Multiple Program Multiple Data，多程序多數(shù)據(jù)）模式。本文將數(shù)據(jù)集劃分至不同進(jìn)程后，各進(jìn)程對(duì)已分配的數(shù)據(jù)集進(jìn)行拓?fù)潢P(guān)系計(jì)算，即各進(jìn)程執(zhí)行相同的算法對(duì)不同的數(shù)據(jù)集協(xié)同進(jìn)行計(jì)算。因此，本文采用SPMD模式設(shè)計(jì)并行算法，主要內(nèi)容有：1）數(shù)據(jù)與任務(wù)的劃分，保障進(jìn)程間的任務(wù)均衡與負(fù)載均衡；2）進(jìn)程間通信的優(yōu)化，減少進(jìn)程間的通信。

矢量目標(biāo)拓?fù)潢P(guān)系并行算法由兩部分組成（圖1）：1）矢量目標(biāo)集的劃分；2）矢量目標(biāo)拓?fù)潢P(guān)系的計(jì)算與判斷。影響并行算法效率的兩個(gè)重要方面是：進(jìn)程間的負(fù)載均衡與任務(wù)均衡。根據(jù)SPMD并行程序設(shè)計(jì)的內(nèi)容，數(shù)據(jù)集劃分是影響并行算法負(fù)載均衡及任務(wù)均衡的關(guān)鍵。因此，矢量目標(biāo)集的劃分是拓?fù)潢P(guān)系并行算法最基礎(chǔ)也是最重要的內(nèi)容。

圖1 矢量目標(biāo)拓?fù)潢P(guān)系并行計(jì)算Fig.1 Parallel computing of topological relations between vector objects

設(shè)計(jì)出適用于矢量目標(biāo)拓?fù)潢P(guān)系并行計(jì)算的矢量目標(biāo)集的數(shù)據(jù)劃分算法，首先需分析矢量目標(biāo)拓?fù)潢P(guān)系計(jì)算的特點(diǎn)。如圖2所示，拓?fù)潢P(guān)系計(jì)算時(shí)先要判斷矢量目標(biāo)間是否相交，如果為相交關(guān)系（intersects），則在相交關(guān)系的基礎(chǔ)上進(jìn)行其他拓?fù)潢P(guān)系的計(jì)算。因此，拓?fù)潢P(guān)系計(jì)算的特點(diǎn)為：1）某一矢量目標(biāo)需對(duì)矢量目標(biāo)集中的其它所有對(duì)象判斷是否相交；2）只計(jì)算與其相交的矢量目標(biāo)的拓?fù)潢P(guān)系。

圖2 空間拓?fù)潢P(guān)系之間的聯(lián)系Fig.2 The relation of spatial topological relations

1.4 拓?fù)潢P(guān)系并行計(jì)算數(shù)據(jù)劃分方法的特點(diǎn)

由拓?fù)潢P(guān)系計(jì)算特點(diǎn)1可知：矢量目標(biāo)間的相交計(jì)算會(huì)消耗大部分計(jì)算資源，這是矢量目標(biāo)集劃分算法需重點(diǎn)考慮的。判斷矢量目標(biāo)間是否相交的最簡(jiǎn)單方法是判斷其最小包圍矩形是否相交，因此，任意兩矢量目標(biāo)間判斷相交的計(jì)算量相同。若要使拓?fù)潢P(guān)系并行計(jì)算中各進(jìn)程間計(jì)算矢量目標(biāo)相交狀態(tài)的任務(wù)均衡，則需各進(jìn)程中目標(biāo)矢量數(shù)據(jù)集的對(duì)象數(shù)量達(dá)到均衡。因此，矢量目標(biāo)集劃分算法只需顧及矢量目標(biāo)的數(shù)量，無需顧及矢量目標(biāo)的復(fù)雜性。

由拓?fù)潢P(guān)系計(jì)算特點(diǎn)2可知：基于相交的拓?fù)潢P(guān)系計(jì)算盡管只消耗小部分計(jì)算資源，矢量目標(biāo)集劃分算法也需考慮。單個(gè)矢量目標(biāo)包含的頂點(diǎn)數(shù)可反映其復(fù)雜程度，而矢量目標(biāo)間拓?fù)潢P(guān)系計(jì)算量的大小與矢量目標(biāo)本身復(fù)雜度相關(guān)，復(fù)雜度越高則計(jì)算量越大。同時(shí)，并行計(jì)算中需考慮各進(jìn)程的負(fù)載均衡，矢量目標(biāo)集信息量的大小可以用其所包含的頂點(diǎn)總數(shù)表示。所以，矢量目標(biāo)集劃分算法不僅需要重點(diǎn)考慮矢量數(shù)據(jù)集中對(duì)象數(shù)量的均衡，還需顧及矢量目標(biāo)的復(fù)雜性即進(jìn)程間頂點(diǎn)總數(shù)均衡。

1.5 顧及任務(wù)均衡與負(fù)載均衡的劃分方法

據(jù)此，顧及任務(wù)均衡與負(fù)載均衡的劃分法需要根據(jù)進(jìn)程數(shù)量p將矢量目標(biāo)集（數(shù)量n）均衡地劃分為p份，各進(jìn)程得到n／p個(gè)矢量目標(biāo)集，且在分配過程中保障進(jìn)程間子矢量目標(biāo)集信息的負(fù)載均衡。具體過程是（圖3）：

（1）矢量目標(biāo)集中對(duì)象數(shù)量為n，根據(jù)矢量目標(biāo)集中對(duì)象的頂點(diǎn)數(shù)vi（圖3A中的數(shù)字）按照式（3）計(jì)算各矢量目標(biāo)的權(quán)值wi，各進(jìn)程依據(jù)對(duì)象的權(quán)值采用排序算法對(duì)矢量目標(biāo)集進(jìn)行序列化（如圖3B）。

（2）每次分配的矢量目標(biāo)子集數(shù)量為l（0＜l≤｜n／（k×p）｜，2≤k＜n／p，且k為偶數(shù)），已分配對(duì)象集的次數(shù)為m（0≤m≤k）。

（3）按照矢量目標(biāo)集序列化的順序，每次將p個(gè)數(shù)量為l且序列號(hào)相鄰的子矢量目標(biāo)集Sm｛sm1，sm2，sm3，……，sm（p×l）｝（即p×l個(gè)對(duì)象）分配到不同進(jìn)程：若m為奇數(shù)，則分配的順序是s1→sp×l；若為偶數(shù)，則分配的順序?yàn)閟p×l→s1。此分配方式重點(diǎn)顧及各進(jìn)程中對(duì)象數(shù)目均衡，也顧及到矢量目標(biāo)的幾何復(fù)雜度（頂點(diǎn)數(shù)）均衡（因?yàn)槭噶磕繕?biāo)集是依據(jù)權(quán)值vi排序，奇數(shù)次與偶數(shù)次分配時(shí)順序相反，如式（4）中進(jìn)程p1第m次分配為Smi，第m＋1次分配為S（m＋1）（p×l－i），進(jìn)程p2第m 次分配為Sm（p×l－i），第m＋1次分配為S（m＋1）i，則各進(jìn)程分配的矢量目標(biāo)集幾何復(fù)雜度基本均衡），如圖3C。

（4）將最后不足p個(gè)（1≤l＜p）矢量目標(biāo)集（數(shù)量為n－m×p×l）按照步驟2均衡劃分給各進(jìn)程，直至所有的矢量目標(biāo)都劃分至各進(jìn)程。

圖3 以每次分配兩個(gè)對(duì)象為例的數(shù)據(jù)劃分Fig.3 The example of spatial data partition for allocating two objects in each time

2 性能測(cè)試

2.1 測(cè)試環(huán)境

為測(cè)試本文方法的計(jì)算效率，搭建一個(gè)小型集群的測(cè)試環(huán)境，其由6個(gè)高性能計(jì)算節(jié)點(diǎn)及1個(gè)存儲(chǔ)節(jié)點(diǎn)（12T）構(gòu)成，集群中各節(jié)點(diǎn)的操作系統(tǒng)是Redhat 5.04（64位），消息傳遞采用MPICH2的并行庫，節(jié)點(diǎn)間采用8Gbps的高速交換機(jī)進(jìn)行通信（圖4）。

圖4 實(shí)驗(yàn)集群軟硬件環(huán)境體系結(jié)構(gòu)Fig.4 Architecture of hardware and software environment of the experiment cluster

2.2 測(cè)試數(shù)據(jù)

宗地?cái)?shù)據(jù)是一種典型且重要的地理空間數(shù)據(jù)。造成宗地?cái)?shù)據(jù)不合格的常見原因有：1）宗地地塊間有重疊；2）相鄰宗地間有空隙。宗地拓?fù)錂z查即檢查幾何數(shù)據(jù)中是否存在上述兩種問題并進(jìn)行標(biāo)識(shí)和修改。本實(shí)驗(yàn)的矢量目標(biāo)集（圖5）為某地區(qū)691 442塊宗地（約有4 417 571個(gè)點(diǎn)），其中圖5A為案例中所用宗地塊集，而圖5B顯示宗地塊的復(fù)雜度。

圖5 實(shí)驗(yàn)數(shù)據(jù)集Fig.5 The experimental data set

2.3 測(cè)試結(jié)果

并行計(jì)算時(shí)，同一硬件構(gòu)架中不同計(jì)算節(jié)點(diǎn)對(duì)同一數(shù)據(jù)集進(jìn)行處理的耗時(shí)會(huì)有所不同（各節(jié)點(diǎn)在任務(wù)均衡與負(fù)載均衡的條件下進(jìn)程間耗時(shí)也會(huì)不同，其誤差率會(huì)在某一范圍內(nèi)波動(dòng)）。為了測(cè)試任務(wù)均衡和負(fù)載均衡的程度，實(shí)驗(yàn)獲取在不同進(jìn)程數(shù)下各進(jìn)程的耗時(shí)（表2所示為集群開啟不同數(shù)量進(jìn)程時(shí)各進(jìn)程拓?fù)溆?jì)算的耗時(shí)）。當(dāng)某一進(jìn)程數(shù)下各進(jìn)程耗時(shí)相差不大時(shí)，表示實(shí)現(xiàn)了集群任務(wù)均衡和負(fù)載均衡。如表2所示，集群開啟2個(gè)進(jìn)程進(jìn)行拓?fù)潢P(guān)系計(jì)算時(shí)，進(jìn)程1耗時(shí)為1 893s，進(jìn)程2耗時(shí)為1 909s，差率為0.8%。圖6為在不同進(jìn)程數(shù)下進(jìn)程耗時(shí)的差率，最大不超過6.5%，表明本文方法用于矢量目標(biāo)拓?fù)潢P(guān)系并行計(jì)算可實(shí)現(xiàn)負(fù)載基本均衡與任務(wù)基本均衡。

圖6 拓?fù)潢P(guān)系并行算法各進(jìn)程的耗時(shí)差率Fig.6 The time－consuming rate of each process for parallel algorithm of topological relations

表2 不同進(jìn)程數(shù)條件下各進(jìn)程耗時(shí)Table 2 Time consumption of process at different process number

執(zhí)行時(shí)對(duì)每個(gè)進(jìn)程DataSet中的矢量目標(biāo)與subDataSet矢量目標(biāo)的拓?fù)潢P(guān)系分別進(jìn)行并行計(jì)算，然后回收所有進(jìn)程的結(jié)果并合并統(tǒng)計(jì)，結(jié)果發(fā)現(xiàn)該宗地有53處重疊（圖7）、0處裂縫。圖8中是基于任務(wù)均衡與負(fù)載均衡劃分法的矢量拓?fù)潢P(guān)系并行計(jì)算加速比、并行效率與進(jìn)程數(shù)的統(tǒng)計(jì)關(guān)系，可見：本文方法的并行效率和加速比均與進(jìn)程數(shù)無關(guān)，即并行算法效率基本不隨進(jìn)程數(shù)增加而衰減，基本穩(wěn)定在80%；加速比隨進(jìn)程數(shù)基本呈線性增長(zhǎng)（斜率約為0.8），在12個(gè)進(jìn)程時(shí)達(dá)9.5。

圖7 宗地疊加檢查的結(jié)果Fig.7 The result of parcel overlay

圖8 拓?fù)潢P(guān)系并行算法的加速比和并行效率Fig.8 Speedup rate and parallel efficiency of parallel algorithm of topological relations

3 結(jié)論

本文針對(duì)當(dāng)前大規(guī)?？臻g數(shù)據(jù)拓?fù)潢P(guān)系并行算法進(jìn)行了探索與研究，從空間數(shù)據(jù)劃分方法入手，實(shí)現(xiàn)了拓?fù)潢P(guān)系并行計(jì)算各進(jìn)程的任務(wù)均衡與負(fù)載均衡，加速比隨進(jìn)程數(shù)基本呈線性增長(zhǎng)，算法并行效率基本不隨進(jìn)程數(shù)增加而衰減，穩(wěn)定在80%。通過本實(shí)驗(yàn)也證明了本文方法的可行性，為矢量數(shù)據(jù)并行算法方面的研究與探索提供了一種思路。由于本文測(cè)試是在光纖高速通信網(wǎng)的集群環(huán)境中進(jìn)行的，結(jié)果受I／O影響較??；若在普通的PC集群上進(jìn)行測(cè)試，需考慮集群I／O的時(shí)間消耗。在PC集群上對(duì)大規(guī)模數(shù)據(jù)進(jìn)行劃分和計(jì)算時(shí)，還需考慮計(jì)算節(jié)點(diǎn)的硬件條件，建議采用數(shù)據(jù)流模式對(duì)數(shù)據(jù)進(jìn)行劃分與計(jì)算。

［1］ 趙春宇.高性能并行GIS中矢量空間數(shù)據(jù)存取與處理關(guān)鍵技術(shù)研究［D］.武漢大學(xué)，2006.

［2］ 張林波，遲學(xué)斌，莫?jiǎng)t堯，等.并行計(jì)算導(dǎo)論［M］.北京：清華大學(xué)出版社，2006.

［3］ 蔣艷凰，楊學(xué)軍，易會(huì)戰(zhàn).衛(wèi)星遙感圖像并行幾何校正算法［J］.計(jì)算機(jī)學(xué)報(bào)，2004，27（7）：944－951.

［4］ 胡冰.遙感圖像融合并行算法的研究及實(shí)現(xiàn)［D］.國防科技大學(xué)，2006.

［5］ 史園莉，李海濤，宋朝達(dá)，等.一種基于通用模型的遙感影像并行處理算法——以PCA融合為例［J］.遙感信息，2010（3）：14－18.

［6］ 盧照，師軍.并行最短路徑搜索算法的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（3）：69－71.

［7］ MADDURI K，BADER D A，BERRY J W，et al.Parallel Shortest Path Algorithms for Solving Large Scale Instances［R］.Georgia Institute of Technology，2006.

［8］ WAUGH T C，HOPKINS S.An algorithm for polygon overlay using cooperative parallel processing［J］.Int.J.Geographical In－formation System，1992，6（6）：457－467.

［9］ CHERVENAK A，F(xiàn)OSTER I，KESSELMAN C，et al.The data grid：Towards an architecture for the distributed management and analysis of large scientific datasets［J］.Network and Computer Application，2000，23：187－200.

［10］ http：／／docs.oracle.com／cd／B28359＿01／server.111／b32024／－partition.htm.2012－12－31.

［11］ LIU C W，CHEN H.A hash partition strategy for distributed query processing［A］.The 5th International Conference on Extending Database Technology （EDBT）［C］.1996，1057：371－387.

［12］ GHANDEHARIZADEH S，DEWITT D J.Hybrid－range partitioning strategy：A new declustering strategy for multiprocessor databases machines［A］.Proceedings of the Sixteenth International Conference on Very Large Databases［C］.1990.481－492.

［13］ 王永杰，孟令奎，趙春宇.基于Hilbert空間排列碼的海量空間數(shù)據(jù)劃分算法研究［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2007，32（7）：650－653.

［14］ ZHOU Y，JIANG L.Hilbert curve based spatial data declustering method for parallel spatial database［C］.The 2nd International Conference on Remote Sensing ＆Environment and Transportation Engineering（RSETE），2012.1－4.

［15］ 田光.并行計(jì)算環(huán)境中矢量空間數(shù)據(jù)的劃分策略研究與實(shí)現(xiàn)［D］.中國地質(zhì)大學(xué)，2011.

［16］ ENGHOFER M J，F(xiàn)RANZOSA R D.Point－set topological spatial relations［J］.International Journal of Geographical Information Systems，1991，5（2）：161－174.

［17］ EGENHOFER M J，HERRING J R.Categorizing Binary Topological Relations between Regions，Lines，and Points in Geographic Databases［R］.University of Maine，1991.

［18］ 李成名，朱英浩，陳軍.利用Voronoi圖形式化描述和判斷GIS中的方向關(guān)系［J］.解放軍測(cè)繪學(xué)院學(xué)報(bào)，1998，19（2）：117－120.

［19］ RANDELL D，CUI Z，COHN A.A spatial logical based on regions and connection［A］.Proceedings of 3rd International Conference on Knowledge Representation and Reasoning［C］.1992.165－176.

［20］ CLEMENTINI E，DI FELICE P，VAN OOSTROM P.A small set of formal topological relationships suitable for end－user interaction［A］.Third International Symposium on Large Spatial Databases［C］.LNCS 692，1993.277－295.