一類帶有互相包含洞的區(qū)域與簡(jiǎn)單區(qū)域間拓?fù)潢P(guān)系的表示

李 健,朱佳斌,趙 慧

(吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院,長(zhǎng)春 130118)

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

1 互相包含洞的區(qū)域與簡(jiǎn)單區(qū)域間拓?fù)淠Ｐ偷慕?/h2>

1.1 區(qū)域?qū)ο蟮亩x

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

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

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

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

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

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

1.2 12-交集模型

RCC理論[6-7]包括RCC-8和RCC-5,二者最大的區(qū)別是前者對(duì)邊界敏感而后者對(duì)邊界不敏感,對(duì)應(yīng)拓?fù)潢P(guān)系的表示如圖4所示.

圖4 兩個(gè)簡(jiǎn)單區(qū)域間的拓?fù)潢P(guān)系Fig.4 Topological relationship between two simple regions

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

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

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

(1)

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

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

其中每個(gè)12-交集矩陣都對(duì)應(yīng)一個(gè)A,B,C,D之間的拓?fù)潢P(guān)系,如圖6所示.16-交集模型解的搜索空間為216,而建立的12-交集模型解的搜索空間僅為212,極大降低了該問題的計(jì)算復(fù)雜性.

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

(2)

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

2 約束條件及其表示

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

約束條件1一個(gè)12-交集矩陣能對(duì)應(yīng)一個(gè)可實(shí)現(xiàn)的6組拓?fù)潢P(guān)系,每組區(qū)域間的兩兩關(guān)系必須滿足RCC5關(guān)系.

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

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

根據(jù)上述約束可得53種12-交集矩陣,這53種拓?fù)潢P(guān)系如圖7所示.

圖7 53種可實(shí)現(xiàn)的拓?fù)潢P(guān)系Fig.7 53 Topological relations and their schematics

定理1所有12-交集模型給出的帶有互相包含洞的區(qū)域與一個(gè)簡(jiǎn)單區(qū)域間可實(shí)現(xiàn)的53種拓?fù)潢P(guān)系是兩兩互斥且完備的.

證明：因?yàn)橛?2-交集模型給出的帶有互相包含洞的區(qū)域與一個(gè)簡(jiǎn)單區(qū)域間的212種拓?fù)潢P(guān)系(包括可實(shí)現(xiàn)的和不可實(shí)現(xiàn)的)是兩兩互斥且完備的,所以只需證明其中可實(shí)現(xiàn)的拓?fù)潢P(guān)系有且僅有53種.約束條件1和約束條件2是拓?fù)潢P(guān)系可實(shí)現(xiàn)的必要條件,通過這兩個(gè)約束可得53種可能實(shí)現(xiàn)的拓?fù)潢P(guān)系,而圖7表明可對(duì)這53種拓?fù)潢P(guān)系找到相應(yīng)的具體實(shí)現(xiàn)情形,因此帶有互相包含洞的區(qū)域與一個(gè)簡(jiǎn)單區(qū)域間的可實(shí)現(xiàn)的拓?fù)潢P(guān)系有53種,并為兩兩互斥且完備的.

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

[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.(歐陽繼紅,霍琳琳,劉大有,等.能表達(dá)帶洞區(qū)域拓?fù)潢P(guān)系的擴(kuò)展9-交集模型 [J].吉林大學(xué)學(xué)報(bào):工學(xué)版,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.