2017, Vol. 38
2. 东北大学秦皇岛分校 计算机与通信工程学院, 河北 秦皇岛 066004
2. School of Computer and Communication Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
空间实体之间的联系有度量关系、拓扑关系和方位关系等多种类型[1].其中，空间拓扑关系是指拓扑变换下的拓扑不变量，在空间特征存储、提取、查询、更新等操作中起重要作用.确定性时空区域间拓扑关系的确定方法主要有基于逻辑的公理化拓扑理论和传统的数学拓扑两大类[2].
在传统拓扑关系查询中，最常用的空间对象表示方法是将数据类型的值转换为最小外包矩形 (minimum bounding rectangle, MBR).以二维坐标表示二维形状 (点、直线、多边形) 的最大范围，即可计算出该二维形状的最小外包矩形[3].文献[4]指出，MBR只是对空间对象的粗略近似，在查询中具有较大误差.为获得更高的查询精确度，本文采用逆时针有向多边形来近似表示实际空间对象，通过对简单多边形形状的时空区域的三角化分得到基于逆时针有向三角形时空数据拓扑关系的一种确定方法.
1 时空区域的表示方法在静态时空数据库中对对象关系数据进行建模是确定时空数据拓扑关系的基础.基于矢量的空间数据模型存储了空间数据的边界坐标，有利于方便表达空间数据之间的拓扑关系.对象视图为离散实体且具有位置和空间属性时，通常以矢量数据模型表示[5].因此本文采用矢量模型表示空间对象，其中顶点位置表示为空间坐标，二维区域表示为简单多边形.同时，为避免直接基于顶点坐标序列计算各种空间操作时的复杂性和低效率，本文采用基于逆时针有向三角形的空间数据表示和操作方法，以方便计算二维静态时空联系下两简单多边形形状的空间区域间的拓扑关系.
定义1 简单多边形形状的时空区域Region r可表示为一系列逆时针有序点{V1(x1, y1), V2(x2, y2), V3(x3, y3), …, Vn(xn, yn)}，要求这些点分别对应该简单多边形的所有顶点.即Region r为该封闭点序列构成的区域内的所有点.
定义2 三角形T < V0(x0, y0), V1(x1, y1), V2(x2, y2)>当且仅当满足
参照文献[6]中给出的简单多边形三角化规则，由定义1和定义2可推得：一个具有n个顶点的简单多边形形状的时空区域Region r可通过以下步骤，划分为n-2个逆时针有向三角形，得到集合Triangulation (Region r)：
1) 确定一个可构成Region r的具有n(n>3) 个点的序列P，选出P中x值最小的点作为初始考虑点V0，若符合该条件的点多于1个，则选取x值最小的点中y值也最小的点作为初始考虑点V0；
2) 设按逆时针方向在V0之后的点为V1、在V0之前的点为V2，按V0, V1, V2方向构建三角形Tri；
3) 若Tri非逆时针有向三角形或P中存在一点位于Tri内，则舍弃该Tri转去考虑V2，重复步骤2)；否则将Tri插入到逆时针有向三角形集合Triangulation (Region r) 中，将V0从P中删除，按顺时针方向继续处理顶点，重复步骤2)；
4) 得到包含n-2个逆时针有向三角形的集合Triangulation (Region r).
为便于理解，本文给出一个将具有6个顶点的简单多边形形状的时空区域Region ra划分为4个逆时针有向三角形的简单示例, 如图 1所示.
|
图 1 示例：简单多边形形状的时空区域划分为三角形 Fig.1 A sample of dividing the spatiotemporal region of simple polygon shape into triangles |
首先，给定一个具有6个顶点的简单多边形形状的时空区域Region ra，在静态时空环境下，选取其中x值最小的点即其最左侧顶点P1作为初始考虑点V0，设P1为V1, P6为V2，按V0, V1, V2方向即P1, P2, P6方向构建三角形Tri1.经判断，Tri1符合定义2中对逆时针有向三角形的要求，则将Tri1插入到集合Triangulation (Region ra) 中，去掉点P1并将P6设置为新的考虑点V0；按P6, P2, P5方向构建三角形Tri2，经判断，该Tri2不符合定义2中对逆时针有向三角形的要求，所以将其舍弃并将P5设置为新的考虑点V0；重复步骤2)，得到新的符合定义2的Tri2，将其插入到集合Triangulation (Region ra) 中；重复上述步骤，将Tri3, Tri4插入到逆时针有向三角形集合中，最终得到包含4个逆时针有向三角形的集合Triangulation (Region ra).
2 时空数据拓扑关系的确定方法空间拓扑操作用于判断两个空间数据之间存在的空间拓扑关系，作用于两个空间数据之上并返回TRUE或FALSE[1].本节提出时空区域间拓扑关系的确定方法.
假设Region r1和Region r2为两简单多边形形状的时空区域.将Region r1的顶点表示为Mi(xi, yi)，Region r2的顶点表示为Nj(xj, yj)，则根据定义1，将具有m个顶点的Region r1表示为{M1(x1, y1), M2(x2, y2), M3(x3, y3), …, Mm(xm, ym)}；将具有n个顶点的Region r2表示为{N1(x1, y1), N2(x2, y2)，N3(x3, y3), …, Nn(xn, yn)}.
文献[7]给出了空间拓扑关系的多种形式化表达模型，文献[8-9]分别给出了判断二维区域中点与多边形及线与多边形的拓扑关系的方法.文献[10]给出了时空区域间8种拓扑关系，本文选取其中5种基本拓扑关系 (相等、包含、部分覆盖、相离、相接)，依据点、线与多边形的拓扑关系以及将多边形划分为若干逆时针有向三角形的操作，构造了基于逆时针有向多边形的空间拓扑关系形式化表达方法，给出了时空区域间基本拓扑关系的确定方法.
定义3 对于两个简单多边形形状的时空区域Region r1和Region r2，在其共有时间区间内，Region r1与Region r2均具有相同顶点数目，且对于Region r1中任意顶点Mi，Region r2中均存在一点Nj与之具有相同坐标，同时Mi的后继顶点与Nj的后继顶点也具有相同坐标，则Region r1与Region r2相等，记作Equal (Region r1, Region r2)：
For Region r1 and Region r2, the topological relation is Equal (Region r1, Region r2) when Tr1∩Tr2≠∅, iff:
|
图 2为两个简单六边形区域Region r1和Region r2相等的例子.首先确定两多边形区域是否具有相同顶点数目，经判断都含有6个顶点，则继续操作.选取Region r1中任意顶点作为Mi，并按逆时针顺序获得其后继顶点Mi+1，判断是否可以在Region r2中找到一点与Mi相对应且其后继顶点与Mi+1相对应，经判断，Region r1和Region r2满足定义3中对Equal (Region r1, Region r2) 的要求，得到Region r1和Region r2的拓扑关系:Region r1与Region r2相等.
|
图 2 Equal (Region r1, Region r2) 示例 Fig.2 A sample of Equal (Region r1, Region r2) |
定义4 对于两个简单多边形形状的时空区域Region r1和Region r2，在其共有时间区间内，Region r1与Region r2均不相等，且对于Region r2中的任意顶点Nj，均存在三角形Tri∈TTri包含Nj或与Nj相接，则Region r1包含Region r2，记作Contain (Region r1, Region r2)：
For Region r1 and Region r2, the topological relation is Contain (Region r1, Region r2) when Tr1∩Tr2≠∅, iff:
1.Not Equal (Region r1, Region r2);
2.For ∀Nj(xj, yj)∈Region r2，∃Tri∈TTri，Nj is contained by Tri ∪ Nj is meet with Tri;
图 3为一个简单六边形区域Region r1包含一个简单四边形区域Region r2的例子.首先判断两区域是否相等，判断为不相等，则执行下一操.由N0开始判断：是否与Region r1中的某一三角形存在相接或被包含关系.经判断，其中N0包含于Tri1，N1包含于Tri2，N2, N3与Tri2相接，满足定义4中对于Contain (Region r1, Region r2) 的要求，得到Region r1和Region r2的拓扑关系：Region r1包含Region r2.
|
图 3 Contain (Region r1, Region r2) 示例 Fig.3 A sample of Contain (Region r1, Region r2) |
定义5 对于两个简单多边形形状的时空区域Region r1和Region r2，在其共有时间区间内，Region r1与Region r2不相等且不存在包含与被包含关系，并存在三角形Tri∈TTri和tri∈Ttri使得Tri与tri具有重叠一致部分，则Region r1与Region r2部分覆盖，记作Overlap (Region r1, Region r2)：
For Region r1 and Region r2, the topological relation is Overlap (Region r1, Region r2) when Tr1∩Tr2≠∅, iff:
1.Not (Equal (Region r1, Region r2) or Contain (Region r1, Region r2) or Contain (Region r2, Region r1));
2.∃Tri∈TTri，∃tri∈Ttri，Overlap (Tri, tri) or Equal (Tri, tri) or Contain (Tri, tri) or Contain (tri, Tri);
图 4为一个简单四边形区域Region r1与一个简单六边形区域Region r2部分覆盖的例子.首先判断两区域是否满足不为相等关系且不存在包含与被包含关系，经判断满足该条件，则由Tri1开始判断：是否与Ttri中任一三角形具有重叠一致部分.经判断，其中T1与t1完全覆盖，T2包含t4，T2与t2，t3部分覆盖，满足定义5中对于Overlap (Region r1, Region r2) 的要求，得到Region r1和Region r2的拓扑关系：Region r1与Region r2部分覆盖.
|
图 4 Overlap (Region r1, Region r2) 示例 Fig.4 A sample of Overlap (Region r1, Region r2) |
定义6 对于两个简单多边形形状的时空区域Region r1和Region r2，在其共有时间区间内，任意三角形Tri∈TTri和tri∈Ttri均相离且不存在包含与被包含关系，则Region r1与Region r2相离，记作Disjoint (Region r1, Region r2)：
For Region r1 and Region r2, the topological relation is Disjoint (Region r1, Region r2) when Tr1∩Tr2≠∅, iff:
1.Disjoint (Tri，tri);
2.Not (Contain (Tri, tri) or Contain (tri, Tri));
图 5为两个简单四边形区域Region r1和Region r2相离的例子.将两多边形区域三角化后得到逆时针有向三角形集合TTri和Ttri，由Tri1开始判断：是否存在三角形Tri∈TTri和Ttri中任意三角形不相离.经判断Tri1与tri1, tri2，Tri2与tri1, tri2均相离，满足定义6中对于Disjoint (Region r1, Region r2) 的要求，得到Region r1和Region r2的拓扑关系：Region r1与Region r2相离.
|
图 5 Disjoint (Region r1, Region r2) 示例 Fig.5 A sample of Disjoint (Region r1, Region r2) |
定义7 对于两个简单多边形形状的时空区域Region r1和Region r2，在其共有时间区间内，Region r1与Region r2无重叠一致部分，且存在其中一个多边形的顶点与另一个多边形相接，则Region r1与Region r2相接，记作Meet (Region r1, Region r2)：
For Region r1 and Region r2, the topological relation is Meet (Region r1, Region r2) when Tr1∩Tr2≠∅, iff:
1.Not (Equal (Region r1, Region r2) or contain (Region r1, Region r2) or contain (Region r2，Region r1) or overlop (Region r1, Region r2));
2.∃Mi(xi, yi)∈Region r1，meet (Mi, Region r2) or ∃Nj(xj, yj)∈Region r2，meet (Nj, Region r1);
图 6为一个简单六边形区域Region r1与一个简单六边形区域Region r2相接的例子.首先判断两区域是否相等或部分覆盖、是否存在包含与被包含关系，经判断不存在上述关系，则由M0开始判断：是否与Region r2中任一三角形相接；继而由N0开始判断：是否与Region r1中任一三角形相接.经判断，其中N0, N1与Tri2相接，M4与tri3相接，满足定义7中对于Meet (Region r1, Region r2) 的要求，得到Region r1和Region r2的拓扑关系：Region r1与Region r2相接.
|
图 6 Meet (Region r1, Region r2) 示例 Fig.6 A sample of Meet (Region r1, Region r2) |
本文采用逆时针有向简单多边形近似表示实际空间对象，较以往采用最小外包矩形表示具有更高的准确度.同时采用基于逆时针有向三角形的时空数据表示和操作方法，提出了确定性时空区域空间拓扑关系的判定方法，并给出了相关具体示例.该方法有效地实现了各种复杂空间操作，避免了直接基于边界坐标计算各种空间复杂操作的值时对效率的影响.
| [1] |
吴长彬, 闾国年.
空间拓扑关系若干问题研究现状的评析[J]. 地球信息科学学报, 2010, 12(4): 524–531.
( Wu Chang-bin, Lyu Guo-nian. Spatial topological relationships:an overview and analysis[J]. Journal of Geo-information Science, 2010, 12(4): 524–531. ) |
| [2] |
张驰伟. 空间拓扑查询[D]. 长沙: 中南大学, 2007.
( Zhang Chi-wei.Spatial topological query[D].Changsha:Central South University, 2007. ) |
| [3] | Chaudhuri D, Samal A. A simple method for fitting of bounding rectangle to closed regions[J]. Pattern Recognition, 2007, 40(7): 1981–1989. DOI:10.1016/j.patcog.2006.08.003 |
| [4] | Lin P L, Tan W H. An efficient method for the retrieval of objects by topological relations in spatial database systems[J]. Information Processing & Management, 2003, 39(4): 543–559. |
| [5] | Brown D G, Riolo R, Robinson D T. Spatial process and data models:toward integration of agent-based models and GIS[J]. Journal of Geographical Systems, 2005, 7(1): 25–47. DOI:10.1007/s10109-005-0148-5 |
| [6] | Tsai C, Liu C. A triangle neighbors approach to intrusion detection[J]. Pattern Recognition, 2010, 43(1): 222–229. DOI:10.1016/j.patcog.2009.05.017 |
| [7] | Claramunt C, Jiang B. An integrated representation of spatial and temporal relationships between evolving regions[J]. Journal of Geographical Systems, 2001, 3(4): 411–428. DOI:10.1007/s101090100066 |
| [8] |
陈金林, 刘谢进, 李宁.
点与简单多边形位置关系判别新算法[J]. 淮南师范学院学报, 2012, 14(5): 120–122.
( Chen Jin-lin, Liu Xie-jin, Li Ning. New algorithm for determining position relation between simple polygon and point[J]. Journal of Huainan Teachers College, 2012, 14(5): 120–122. ) |
| [9] | Erwig M, Schneider M. Spatio-temporal predicates[J]. IEEE Transactions on Knowledge & Data Engineering, 2002, 14(4): 881–901. |
| [10] | Pelekis N, Theodoulidis B, Kopanakis I. Literature review of spatio-temporal database models[J]. The Knowledge Engineering Review, 2004, 19(3): 235–274. |