一種凹形區域和簡單寬邊界區域間的拓撲關系表示模型

王立君,富 倩

(1. 長春工業大學 信息傳播工程學院,長春 130012;2. 吉林大學 地球科學學院,長春 130061)

空間推理[1]就是運用空間理論與人工智能技術和方法對空間對象進行建模、 描述和表示,并對其空間關系進行分析和處理的過程. 它在地理信息系統(GIS)、 圖形圖像處理、 模式識別、 機器人導航和空間數據庫等領域應用廣泛[2-3]. 空間關系模型研究是空間推理的基本內容,其中大多數為拓撲關系模型研究[4-8]. 現有空間拓撲關系模型大多數針對簡單對象和確定性對象,對于現實世界中普遍存在的復雜對象及不確定性對象的處理能力較弱. 本文針對二維空間中的平面區域,基于空間拓撲關系模型中經典的區域連接演算(RCC)理論,提出一種凹形區域和寬邊界區域間的拓撲關系表示模型,能對復雜對象和不確定性對象中較簡單情況進行有效處理.

1 凹形區域

定義1[9]取平面區域P中任意兩點做連線,若連線上的任意點總在區域P中,則稱P為凸形區域.

定義2[9]取平面區域P中任意兩點做連線,若連線上存在某一點不在區域P中,則稱P為凹形區域.

定義3[4]平面內包含區域P的最小凸形區域,稱為P的凸殼,記為Pch.

定義4[4]凹形區域P的凸殼與P自身做差得到的部分,稱為P的內側,記為Pi.

如圖1所示,Pi為凹形區域P的內側,P∪Pi即為P的凸殼.

2 寬邊界區域

寬邊界區域[10-12]是一種用于處理不確定性對象的表示方法. 寬邊界區域通常由內、 外區域組成,內區域表示寬邊界一定存在的范圍,外區域表示寬邊界可能存在的范圍. 內、 外區域之差即為寬邊界,它具有一定的寬度和面積.

定義5令A為寬邊界區域,由兩個簡單區域A1和A2組成,且滿足A1?A2,則A1稱為A的內區域,A2稱為A的外區域,內、 外區域之差即為A的寬邊界,記為ΔA=A2-A1.

如圖2所示,A為寬邊界區域,A1,A2分別為A的內、 外區域,ΔA為A的寬邊界.

圖1 Pi為凹形區域P的內側Fig.1 Pi inside concave region P

圖2 寬邊界區域A及其各組成部分Fig.2 Broad boundary region A and its composite parts

3 凹形區域和寬邊界區域的拓撲關系表示模型

3.1 空間區域劃分 令X,Y分別為二維空間中的凹形區域和寬邊界區域,考慮X,Y的4個組成部分,即X的內側、X自身和Y的內、 外區域,分別記為Xi,X,Y1,Y2,如圖3所示.

圖3 凹形區域X和寬邊界區域Y的空間劃分Fig.3 Space partitions of concave region X and broad boundary region Y

令X為凹形區域,Y為簡單寬邊界區域,則X,Y間的拓撲關系可通過考慮各子部分間的相交情況進行描述,形式化表示為如下的4×4交集矩陣：

若每項的交集非空,則取值為1；否則,若每項的交集為空,則取值為0. 取遍所有不同的0/1組合,共有216個不同的矩陣. 考慮到現實世界中的空間對象,216個矩陣中包含了許多實際不存在的情況. 為了去掉這些實際不存在的拓撲關系,下面將給出拓撲關系生成的約束條件.

3.3 拓撲關系生成的約束條件 下面給出3個約束條件,用于得到凹形區域和簡單寬邊界區域間所有實際存在的拓撲關系.

約束條件1對于凹形區域X和簡單寬邊界區域Y的4個部分Xi,X,Y1,Y2,每部分的外部必相交,即XOO∩YOO= 1.

因為Xi,X,Y1,Y2的外部均為無限區域,而無限區域之間交集必非空,因而約束條件1合理.

由定義4可知,凹形區域的內部與其內側的內部必不相交,凹形區域的外部與其內側的內部必相交,凹形區域的內部與其內側的外部必相交,因而約束條件2合理.

由定義5可知,簡單寬邊界區域的內、 外區域,它們的內部必相交,內區域的內部和外區域的外部必不相交,內區域的外部和外區域的內部必相交,從而約束條件3合理.

3.4 拓撲關系表示 根據上述3個約束條件,從216個不同矩陣中刪掉二維平面中實際不存在的情況,最終得到凹形區域和簡單寬邊界區域間的67種拓撲關系,并給出每種關系對應的示意圖,如圖4所示.

綜上所述， 本文針對空間中一類較簡單的復雜區域和不確定區域， 基于交集矩陣表示方法， 提出了一種凹形區域和簡單寬邊界區域間的拓撲關系表示模型， 給出了約束條件， 通過去掉二維平面中所有不可實現的情況， 最終得到實際存在的67種拓撲關系， 并給出了其拓撲關系示意圖. 該模型可用于空間查詢等應用領域， 在一定程度上增強了對復雜區域和不確定區域的處理能力.

[1] Cohn A G,Hazarika S M. Qualitative Spatial Representation and Reasoning: An Overview [J]. Fundamental Informatics,2001,46(1/2): 1-29.

[2] LIU Ya-bin,LIU Da-you. A Review on Spatial Reasoning and Geographic Information System [J]. Journal of Software,2000,11(12): 1598-1606. (劉亞彬,劉大有. 空間推理與地理信息系統綜述 [J]. 軟件學報,2000,11(12): 1598-1606.)

[3] LIU Da-you,HU He,WANG Sheng-sheng,et al. Research Progress in Spatio-Temporal Reasoning [J]. Journal of Software,2004,15(8): 1141-1149. (劉大有,胡鶴,王生生,等. 時空推理研究進展 [J]. 軟件學報,2004,15(8): 1141-1149.)

[4] Clementini E,Billen R. Modeling and Computing Ternary Projective Relations between Regions [J]. IEEE Transactions on Knowledge and Data Engineering,2006,18(6): 799-814.

[5] Roussopoulos N,Faloutsos C,Sellis T. An Efficient Pictorial Database System for PSQL [J]. IEEE Transactions on Software Engineering,1988,14(5): 639-650.

[6] Cohn A G,Bennett B,Gooday J,et al. Qualitative Spatial Representation and Reasoning with the Region Connection Calculus [J]. GeoInformatica,1997,1(3): 275-316.

[7] LI San-jiang. A Complete Classification of Topological Relations Using the 9-Intersection Method [J]. International Journal of Geographical Information Science,2006,20(6): 589-610.

[8] Roy A J,Stell J G. Spatial Relations between Indeterminate Regions [J]. International Journal of Approximate Reasoning,2001,27(3): 205-234.

[9] Egenhofer M J,Vasardani M. Spatial Reasoning with a Hole [C]//Conference on Spatial Information Theory (COSIT-07). Berlin: Springer,2007: 303-320.

[10] 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. (歐陽繼紅,霍琳琳,劉大有,等. 能表達帶洞區域拓撲關系的擴展9-交集模型 [J]. 吉林大學學報: 工學版,2009,39(6): 1595-1600.)

[11] OUYANG Ji-hong,FU Qian,LIU Da-you. A Model for Representing Topological Relations between Simple Concave Regions [J]. Journal of Jilin University: Science Edition,2007,45(3): 427-431. (歐陽繼紅,富倩,劉大有. 一種簡單凹形區域間拓撲關系的表示模型 [J]. 吉林大學學報: 理學版,2007,45(3): 427-431.)

[12] Clementini E,DiFelice P. An Algebraic Model for Spatial Objects with Indeterminate Boundaries [C]//Geographic Objects with Indeterminate Boundaries. London: Taylor &Francis,1996: 155-169.