柏禄一^1,2, 贾潍佳², 曹杏茹²
1. 东北大学 信息科学与工程学院，辽宁 沈阳 110819;
2. 东北大学秦皇岛分校 计算机与通信工程学院, 河北 秦皇岛 066004
收稿日期：2015-11-19
基金项目：国家自然科学基金资助项目 (61402087);河北省自然科学基金资助项目 (F2015501049);中央高校基本科研业务费专项资金资助项目 (N130323006);河北省教育厅资助项目 (QN2014339);东北大学秦皇岛分校博士基金资助项目 (XNB201428)。
作者简介：柏禄一 (1984-), 男, 辽宁丹东人, 东北大学副教授, 博士。

摘要：研究了基于逆时针有向三角形 (conterclockwisely directed triangle, CDT) 的时空区域拓扑关系的确定方法，尤其对静态时空数据库中基于逆时针有向多边形的时空区域表示方法、简单多边形形状时空区域的三角化方法及静态时空联系下两个简单多边形形状时空区域间拓扑关系的确定方法进行了研究.结果表明：时空区域间的相等、包含、部分覆盖、相离、相接5种基本拓扑关系均可通过基于逆时针有向三角形的方法确定.该方法不仅有效地实现了各种时空数据的表示和操作，而且避免了直接基于边界坐标计算时空数据时对效率的影响.
关键词：逆时针有向三角形简单多边形三角化拓扑关系静态时空联系
CDT-based Determining Method of Topological Relations for Spatiotemporal Regions
BAI Lu-yi^1,2, JIA Wei-jia², CAO Xing-ru²
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Computer and Communication Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
Corresponding author: BAI Lu-yi, E-mail: baily@neuq.edu.cn
Abstract: A CDT-based determining method of topological relations for spatiotemporal regions was investigated. The following contents were especially studied, including CDT-based spatiotemporal region representation in static spatio-temporal database, the method of dividing the spatiotemporal region in simple polygon shape into conterclockwisely directed triangle, and determining method of these spatiotemporal regions in simple polygon shape in static spatiotemporal database. The results showed that five kinds of fundamental topological relations between spatiotemporal regions, i.e., equal, contain, overlap, disjoint and meet, can be determined with CDT. The proposed method not only effectively realizes the variety of spatiotemporal data presentation and operation, but also avoids the effect of spatiotemporal data on efficiency when the spatiotemporal data were calculated on the basis of boundary coordinates directly.
Key Words: conterclockwisely directed trianglesimple polygondividing a polygon into trianglestopological relationstatic spatiotemporal relation
空间实体之间的联系有度量关系、拓扑关系和方位关系等多种类型^[1].其中，空间拓扑关系是指拓扑变换下的拓扑不变量，在空间特征存储、提取、查询、更新等操作中起重要作用.确定性时空区域间拓扑关系的确定方法主要有基于逻辑的公理化拓扑理论和传统的数学拓扑两大类^[2].
在传统拓扑关系查询中，最常用的空间对象表示方法是将数据类型的值转换为最小外包矩形 (minimum bounding rectangle, MBR).以二维坐标表示二维形状 (点、直线、多边形) 的最大范围，即可计算出该二维形状的最小外包矩形^[3].文献[4]指出，MBR只是对空间对象的粗略近似，在查询中具有较大误差.为获得更高的查询精确度，本文采用逆时针有向多边形来近似表示实际空间对象，通过对简单多边形形状的时空区域的三角化分得到基于逆时针有向三角形时空数据拓扑关系的一种确定方法.
1 时空区域的表示方法在静态时空数据库中对对象关系数据进行建模是确定时空数据拓扑关系的基础.基于矢量的空间数据模型存储了空间数据的边界坐标，有利于方便表达空间数据之间的拓扑关系.对象视图为离散实体且具有位置和空间属性时，通常以矢量数据模型表示^[5].因此本文采用矢量模型表示空间对象，其中顶点位置表示为空间坐标，二维区域表示为简单多边形.同时，为避免直接基于顶点坐标序列计算各种空间操作时的复杂性和低效率，本文采用基于逆时针有向三角形的空间数据表示和操作方法，以方便计算二维静态时空联系下两简单多边形形状的空间区域间的拓扑关系.
定义1?简单多边形形状的时空区域Region r可表示为一系列逆时针有序点{V₁(x₁, y₁), V₂(x₂, y₂), V₃(x₃, y₃), …, V_n(x_n, y_n)}，要求这些点分别对应该简单多边形的所有顶点.即Region r为该封闭点序列构成的区域内的所有点.
定义2?三角形T < V₀(x₀, y₀), V₁(x₁, y₁), V₂(x₂, y₂)>当且仅当满足时为逆时针有向三角形.
参照文献[6]中给出的简单多边形三角化规则，由定义1和定义2可推得：一个具有n个顶点的简单多边形形状的时空区域Region r可通过以下步骤，划分为n-2个逆时针有向三角形，得到集合Triangulation (Region r)：
1)?确定一个可构成Region r的具有n(n>3) 个点的序列P，选出P中x值最小的点作为初始考虑点V₀，若符合该条件的点多于1个，则选取x值最小的点中y值也最小的点作为初始考虑点V₀；
2)?设按逆时针方向在V₀之后的点为V₁、在V₀之前的点为V₂，按V₀, V₁, V₂方向构建三角形Tri；
3)?若Tri非逆时针有向三角形或P中存在一点位于Tri内，则舍弃该Tri转去考虑V₂，重复步骤2)；否则将Tri插入到逆时针有向三角形集合Triangulation (Region r) 中，将V₀从P中删除，按顺时针方向继续处理顶点，重复步骤2)；
4)?得到包含n-2个逆时针有向三角形的集合Triangulation (Region r).
为便于理解，本文给出一个将具有6个顶点的简单多边形形状的时空区域Region r_a划分为4个逆时针有向三角形的简单示例, 如图 1所示.
图 1(Fig. 1)

图 1 示例：简单多边形形状的时空区域划分为三角形Fig.1 A sample of dividing the spatiotemporal region of simple polygon shape into triangles

首先，给定一个具有6个顶点的简单多边形形状的时空区域Region r_a，在静态时空环境下，选取其中x值最小的点即其最左侧顶点P₁作为初始考虑点V₀，设P₁为V₁, P₆为V₂，按V₀, V₁, V₂方向即P₁, P₂, P₆方向构建三角形Tri₁.经判断，Tri₁符合定义2中对逆时针有向三角形的要求，则将Tri₁插入到集合Triangulation (Region r_a) 中，去掉点P₁并将P₆设置为新的考虑点V₀；按P₆, P₂, P₅方向构建三角形Tri₂，经判断，该Tri₂不符合定义2中对逆时针有向三角形的要求，所以将其舍弃并将P₅设置为新的考虑点V₀；重复步骤2)，得到新的符合定义2的Tri₂，将其插入到集合Triangulation (Region r_a) 中；重复上述步骤，将Tri₃, Tri₄插入到逆时针有向三角形集合中，最终得到包含4个逆时针有向三角形的集合Triangulation (Region r_a).
2 时空数据拓扑关系的确定方法空间拓扑操作用于判断两个空间数据之间存在的空间拓扑关系，作用于两个空间数据之上并返回TRUE或FALSE^[1].本节提出时空区域间拓扑关系的确定方法.
假设Region r₁和Region r₂为两简单多边形形状的时空区域.将Region r₁的顶点表示为M_i(x_i, y_i)，Region r₂的顶点表示为N_j(x_j, y_j)，则根据定义1，将具有m个顶点的Region r₁表示为{M₁(x₁, y₁), M₂(x₂, y₂), M₃(x₃, y₃), …, M_m(x_m, y_m)}；将具有n个顶点的Region r₂表示为{N₁(x₁, y₁), N₂(x₂, y₂)，N₃(x₃, y₃), …, N_n(x_n, y_n)}.
文献[7]给出了空间拓扑关系的多种形式化表达模型，文献[8-9]分别给出了判断二维区域中点与多边形及线与多边形的拓扑关系的方法.文献[10]给出了时空区域间8种拓扑关系，本文选取其中5种基本拓扑关系 (相等、包含、部分覆盖、相离、相接)，依据点、线与多边形的拓扑关系以及将多边形划分为若干逆时针有向三角形的操作，构造了基于逆时针有向多边形的空间拓扑关系形式化表达方法，给出了时空区域间基本拓扑关系的确定方法.
定义3?对于两个简单多边形形状的时空区域Region r₁和Region r₂，在其共有时间区间内，Region r₁与Region r₂均具有相同顶点数目，且对于Region r₁中任意顶点M_i，Region r₂中均存在一点N_j与之具有相同坐标，同时M_i的后继顶点与N_j的后继顶点也具有相同坐标，则Region r₁与Region r₂相等，记作Equal (Region r₁, Region r₂)：
For Region r₁ and Region r₂, the topological relation is Equal (Region r₁, Region r₂) when T_r1∩T_r2≠?, iff:
图 2为两个简单六边形区域Region r₁和Region r₂相等的例子.首先确定两多边形区域是否具有相同顶点数目，经判断都含有6个顶点，则继续操作.选取Region r₁中任意顶点作为M_i，并按逆时针顺序获得其后继顶点M_i+1，判断是否可以在Region r₂中找到一点与M_i相对应且其后继顶点与M_i+1相对应，经判断，Region r₁和Region r₂满足定义3中对Equal (Region r₁, Region r₂) 的要求，得到Region r₁和Region r₂的拓扑关系:Region r₁与Region r₂相等.
图 2(Fig. 2)

图 2 Equal (Region r1, Region r2) 示例Fig.2 A sample of Equal (Region r1, Region r2)

定义4?对于两个简单多边形形状的时空区域Region r₁和Region r₂，在其共有时间区间内，Region r₁与Region r₂均不相等，且对于Region r₂中的任意顶点N_j，均存在三角形Tri∈TTri包含N_j或与N_j相接，则Region r₁包含Region r₂，记作Contain (Region r₁, Region r₂)：
For Region r₁ and Region r₂, the topological relation is Contain (Region r₁, Region r₂) when T_r1∩T_r2≠?, iff:
1.Not Equal (Region r₁, Region r₂);
2.For ?N_j(x_j, y_j)∈Region r₂，?Tri∈TTri，N_j is contained by Tri ∪ N_j is meet with Tri;
图 3为一个简单六边形区域Region r₁包含一个简单四边形区域Region r₂的例子.首先判断两区域是否相等，判断为不相等，则执行下一操.由N₀开始判断：是否与Region r₁中的某一三角形存在相接或被包含关系.经判断，其中N₀包含于Tri₁，N₁包含于Tri₂，N₂, N₃与Tri₂相接，满足定义4中对于Contain (Region r₁, Region r₂) 的要求，得到Region r₁和Region r₂的拓扑关系：Region r₁包含Region r₂.
图 3(Fig. 3)

图 3 Contain (Region r1, Region r2) 示例Fig.3 A sample of Contain (Region r1, Region r2)

定义5?对于两个简单多边形形状的时空区域Region r₁和Region r₂，在其共有时间区间内，Region r₁与Region r₂不相等且不存在包含与被包含关系，并存在三角形Tri∈TTri和tri∈Ttri使得Tri与tri具有重叠一致部分，则Region r₁与Region r₂部分覆盖，记作Overlap (Region r₁, Region r₂)：
For Region r₁ and Region r₂, the topological relation is Overlap (Region r₁, Region r₂) when T_r1∩T_r2≠?, iff:
1.Not (Equal (Region r₁, Region r₂) or Contain (Region r₁, Region r₂) or Contain (Region r₂, Region r₁));
2.?Tri∈TTri，?tri∈Ttri，Overlap (Tri, tri) or Equal (Tri, tri) or Contain (Tri, tri) or Contain (tri, Tri);
图 4为一个简单四边形区域Region r₁与一个简单六边形区域Region r₂部分覆盖的例子.首先判断两区域是否满足不为相等关系且不存在包含与被包含关系，经判断满足该条件，则由Tri1开始判断：是否与Ttri中任一三角形具有重叠一致部分.经判断，其中T₁与t₁完全覆盖，T₂包含t₄，T₂与t₂，t₃部分覆盖，满足定义5中对于Overlap (Region r₁, Region r₂) 的要求，得到Region r₁和Region r₂的拓扑关系：Region r₁与Region r₂部分覆盖.
图 4(Fig. 4)

图 4 Overlap (Region r1, Region r2) 示例Fig.4 A sample of Overlap (Region r1, Region r2)

定义6?对于两个简单多边形形状的时空区域Region r₁和Region r₂，在其共有时间区间内，任意三角形Tri∈TTri和tri∈Ttri均相离且不存在包含与被包含关系，则Region r₁与Region r₂相离，记作Disjoint (Region r₁, Region r₂)：
For Region r₁ and Region r₂, the topological relation is Disjoint (Region r₁, Region r₂) when T_r1∩T_r2≠?, iff:
1.Disjoint (Tri，tri);
2.Not (Contain (Tri, tri) or Contain (tri, Tri));
图 5为两个简单四边形区域Region r₁和Region r₂相离的例子.将两多边形区域三角化后得到逆时针有向三角形集合TTri和Ttri，由Tri₁开始判断：是否存在三角形Tri∈TTri和Ttri中任意三角形不相离.经判断Tri₁与tri₁, tri₂，Tri₂与tri₁, tri₂均相离，满足定义6中对于Disjoint (Region r₁, Region r₂) 的要求，得到Region r₁和Region r₂的拓扑关系：Region r₁与Region r₂相离.
图 5(Fig. 5)

图 5 Disjoint (Region r1, Region r2) 示例Fig.5 A sample of Disjoint (Region r1, Region r2)

定义7?对于两个简单多边形形状的时空区域Region r₁和Region r₂，在其共有时间区间内，Region r₁与Region r₂无重叠一致部分，且存在其中一个多边形的顶点与另一个多边形相接，则Region r₁与Region r₂相接，记作Meet (Region r₁, Region r₂)：
For Region r₁ and Region r₂, the topological relation is Meet (Region r₁, Region r₂) when T_r1∩T_r2≠?, iff:
1.Not (Equal (Region r₁, Region r₂) or contain (Region r₁, Region r₂) or contain (Region r₂，Region r₁) or overlop (Region r₁, Region r₂));
2.?M_i(x_i, y_i)∈Region r₁，meet (M_i, Region r₂) or ?N_j(x_j, y_j)∈Region r₂，meet (N_j, Region r₁);
图 6为一个简单六边形区域Region r₁与一个简单六边形区域Region r₂相接的例子.首先判断两区域是否相等或部分覆盖、是否存在包含与被包含关系，经判断不存在上述关系，则由M₀开始判断：是否与Region r₂中任一三角形相接；继而由N₀开始判断：是否与Region r₁中任一三角形相接.经判断，其中N₀, N₁与Tri₂相接，M₄与tri₃相接，满足定义7中对于Meet (Region r₁, Region r₂) 的要求，得到Region r₁和Region r₂的拓扑关系：Region r₁与Region r₂相接.
图 6(Fig. 6)

图 6 Meet (Region r1, Region r2) 示例Fig.6 A sample of Meet (Region r1, Region r2)

3 结论本文采用逆时针有向简单多边形近似表示实际空间对象，较以往采用最小外包矩形表示具有更高的准确度.同时采用基于逆时针有向三角形的时空数据表示和操作方法，提出了确定性时空区域空间拓扑关系的判定方法，并给出了相关具体示例.该方法有效地实现了各种复杂空间操作，避免了直接基于边界坐标计算各种空间复杂操作的值时对效率的影响.
参考文献

[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.