李 健,朱佳斌,趙 慧

(吉林農業(yè)大學 信息技術學院,長春 130118)

空間推理[1-2]在地理信息系統(tǒng)(GIS)[3]等領域應用廣泛.拓撲關系作為基本的空間關系,其相關表示直接影響空間分析和查詢等應用中獲取的信息量及有效性.拓撲關系的形式化描述主要包括4-交模型[4]、D9-交模型[5]、區(qū)域連接演算模型[6]和區(qū)域間拓撲關系的層次表達法等,其中具有典型性的是區(qū)域連接演算(region connection calculus,RCC)和交集模型.上述模型描述的空間對象多為兩個簡單區(qū)域,表達能力相對有限,而現(xiàn)實世界中的空間對象情況較復雜,對于帶多個洞的區(qū)域與簡單區(qū)域間的拓撲關系目前研究報道較少.本文提出一類帶有互相包含洞的區(qū)域與簡單區(qū)域間拓撲關系的表示可視為4個區(qū)域的應用.

1 互相包含洞的區(qū)域與簡單區(qū)域間拓撲模型的建立

1.1 區(qū)域對象的定義

定義1若區(qū)域A包含區(qū)域B,則稱B是A的洞,如圖1所示.

定義2若區(qū)域A包含簡單區(qū)域B,區(qū)域B又包含簡單區(qū)域C,則稱區(qū)域A,B,C構成一類帶有互相包含洞的區(qū)域,如圖2所示.

圖1 簡單帶單洞區(qū)域Fig.1 Region with a hole

圖2 一類帶有互相包含洞的區(qū)域Fig.2 Region with holes of mutual inclusion

圖3 一類帶有互相包含洞的區(qū)域與一個簡單區(qū)域Fig.3 Region with holes of mutual inclusion and a simple region

根據(jù)上述定義,本文對此類帶有互相包含洞的區(qū)域與一個如圖3所示簡單區(qū)域間的拓撲關系進行研究,并將其劃分為區(qū)域A,B,C,D四部分.由定義2可知,A包含B,B包含C,即A,B,C構成一類相互包含的洞,因此區(qū)域A和區(qū)域B,C間的拓撲關系是固定的.

1.2 12-交集模型

RCC理論[6-7]包括RCC-8和RCC-5,二者最大的區(qū)別是前者對邊界敏感而后者對邊界不敏感,對應拓撲關系的表示如圖4所示.

圖4 兩個簡單區(qū)域間的拓撲關系Fig.4 Topological relationship between two simple regions

研究表明,16-交集模型[8]是一類基于RCC5的處理4個區(qū)域間拓撲關系的模型,而對于16-交集模型所定義的0/1矩陣,其中有些位置上的元素取值不變,表現(xiàn)恒為0或恒為1,這是由固定拓撲關系導致的.由于區(qū)域A包含區(qū)域B和C,因此A的外部與B的內部或C的內部交集都為空,即A1∩B0和A1∩C0恒成立,如圖5所示.

無論區(qū)域D的位置如何變動,區(qū)域A和區(qū)域B,C間的拓撲關系并不影響表示模型的區(qū)分,即下列情形都成立：A1∩B0∩C0∩D0=0,A1∩B0∩C0∩D1=0,A1∩B0∩C1∩D0=0,A1∩B0∩C1∩D1=0.因此可將16-交集模型進行改進,使之在滿足能完備表示并區(qū)分一類帶有互相包含洞的區(qū)域與簡單區(qū)域間拓撲關系的條件下,減少矩陣元素個數(shù),降低計算復雜度,實現(xiàn)模型優(yōu)化.

本文將12-交集矩陣定義為

(1)

圖5 交集情形Fig.5 Condition of regional intersections

圖6 可實現(xiàn)的12-交集矩陣Fig.6 Realizable 12-intersection matrix

其中每個12-交集矩陣都對應一個A,B,C,D之間的拓撲關系,如圖6所示.16-交集模型解的搜索空間為216,而建立的12-交集模型解的搜索空間僅為212,極大降低了該問題的計算復雜性.

雖然理論上有212個12-交集矩陣,但并不是所有的矩陣都可實現(xiàn).例如

(2)

即為不可實現(xiàn)的12-交集矩陣.式(1)中第12個元素A1∩B1∩C1∩D1,即4個區(qū)域的外部相交為空,這對于有界區(qū)域是不可能的.

2 約束條件及其表示

對于所有可實現(xiàn)的12-交集矩陣,必須滿足如下約束條件.

約束條件1一個12-交集矩陣能對應一個可實現(xiàn)的6組拓撲關系,每組區(qū)域間的兩兩關系必須滿足RCC5關系.

約束條件2對于簡單有界區(qū)域,(AC)0∩(BC)0∩(CC)0∩(DC)0非空,即M1111=1.

約束條件3對于該類帶有互相包含洞的區(qū)域與一個簡單區(qū)域的4個部分A,B,C,D,有A包含B,B包含C,即B,C是區(qū)域A的洞,同時C是B的洞.

根據(jù)上述約束可得53種12-交集矩陣,這53種拓撲關系如圖7所示.

圖7 53種可實現(xiàn)的拓撲關系Fig.7 53 Topological relations and their schematics

定理1所有12-交集模型給出的帶有互相包含洞的區(qū)域與一個簡單區(qū)域間可實現(xiàn)的53種拓撲關系是兩兩互斥且完備的.

證明：因為由12-交集模型給出的帶有互相包含洞的區(qū)域與一個簡單區(qū)域間的212種拓撲關系(包括可實現(xiàn)的和不可實現(xiàn)的)是兩兩互斥且完備的,所以只需證明其中可實現(xiàn)的拓撲關系有且僅有53種.約束條件1和約束條件2是拓撲關系可實現(xiàn)的必要條件,通過這兩個約束可得53種可能實現(xiàn)的拓撲關系,而圖7表明可對這53種拓撲關系找到相應的具體實現(xiàn)情形,因此帶有互相包含洞的區(qū)域與一個簡單區(qū)域間的可實現(xiàn)的拓撲關系有53種,并為兩兩互斥且完備的.

綜上所述,本文通過對16-交集矩陣進行改進得到了適合表示一類帶有互相包含洞的區(qū)域與簡單區(qū)域間拓撲關系的12-交集矩陣,給出了約束條件并得到了一類帶有互相包含洞的區(qū)域與一個簡單區(qū)域間的53種可實現(xiàn)的拓撲關系及53種拓撲關系圖,進一步驗證了53種拓撲關系矩陣都是可實現(xiàn)的,并證明了12-交集模型中基本關系是互斥且完備的.

[1] WANG Sheng-sheng,LIU Da-you.Knowledge Representation and Reasoning for Qualitative Spatial Change [J].Knowledge-Based Systems,2012,30:161-171.

[2] WANG Sheng-sheng,LIU Da-you.An Efficient Method for Calculating Qualitative Spatial Relations [J].Chinese Journal of Electronics,2009,18(1):42-46.

[3] Scott J,Lee L H.Designing the Low-Power M*CORETM Architecture [C]//IEEE Power Driven Microarchitecture Workshop.Piscataway:IEEE Computer Society,1998:29-33.

[4] Egenhofer M J,Franzosa R D.Point-Set Topological Spatial Relation [J].International Journal of Geographical Information System,1991,5(2):161-174.

[5] OUYANG Ji-hong,HUO Lin-lin,LIU Da-you,et al.Extended 9-Intersection Model for Description of Topological Relations between Regions with Holes [J].Journal of Jilin University:Engineering and Technology Edition,2009,39(6):1595-1600.(歐陽繼紅,霍琳琳,劉大有,等.能表達帶洞區(qū)域拓撲關系的擴展9-交集模型 [J].吉林大學學報:工學版,2009,39(6):1595-1600.)

[6] Clarke B L.A Calculus of Individuals Based on “Connection” [J].Notre Dame Journal of Formal Logic，1981,22(3):204-218.

[7] Randell D,Cohn A.Modelling Topological and Metrical Properties in Physical Processes [C]//Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning.San Francisco:Morgan Kaufmann Publishers Inc,1989:357-368.

[8] LI Jian,OUYANG Ji-hong,WANG Zhen-xin.Representation for Topological Relations of Four Simple Regions [C]//The 2012 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD’12).Piscataway:IEEE Computer Society,2012:2961-2965.