一种多边形场景拓扑关系表达方法

摘要

一种多边形场景拓扑关系表达方法，其用于对多边形场景的拓扑结构进行表述，其包括如下步骤。步骤A，将所述多边形场景进行拓扑同胚变化并生成拓扑同胚图，步骤B，对步骤A生成的拓扑同胚图生成对偶图，然后提取所述对偶图中多边形间的邻近关系，步骤C，根据步骤B所获得的多边形间的邻近关系，建立多边形形状集合，并采用K阶邻近对多边形进行排序，生成多边形的K阶邻近编码字符串来表述多边形场景的拓扑结构。本发明所提供的一种多边形场景拓扑关系表达方法，可使用简单的字符串来表示多边形场景拓扑关系，提高了多边形场景拓扑同胚的判断的效率。

说明书

技术领域

本发明涉及一种对空间场景进行表达和判断的算法，特别是一种多边形场景拓扑关系表达方法。

背景技术

空间场景包括空间目标集合及其空间布局。其在GIS、空间认知及纺织、建筑设计等领域有着广泛的应用。在GIS中，空间场景的查询、推理是对传统的基于SQL的空间查询的扩展，这也是近年来GIS研究的热点(Egenhofer，1994；Clare,2000；Nedas et al，2008)。GIS中空间场景查询的核心问题是空间场景拓扑一致性比较，其难点在于如何确定查询场景和数据库数据集中目标及其空间关系的映射关系。针对这一学术问题，Egenhofer等(1994)在其提出的四交模型的基础上增加了维、交类型、部件次序等，以判断两面目标拓扑相等，但其难以扩展到对大范围多目标的空间场景间拓扑结构的相似或相等的判断。Paiva(1998)根据图论的思想，采用联系图标示多边形场景的拓扑关系，给出了空间场景拓扑关系的表达和相似性判断方法，但其对空间场景匹配，特别是基于联系图的最大子图提取的效率不高。Nedas et al(2008)提出了一种基于认知和领域知识的方法进行空间场景匹配和相似性评价，从概念层次上研究了空间数据库的相似性操作，但其缺乏空间场景表达和判断的实用算法。

图1为一种多边形场景的结构示意图，如图1所示，多边形场景是一种特殊的空间场景，其是由相接不含洞的多边形构成的连续铺盖，是一种有向简单图。多边形场景中多边形之间的关系主要是邻接关系，其是一种网状关系，而非树形关系。

图2为两个待比对拓扑一致性的多边形场景的结构示意图，如图2所示的两个多边形场景的拓扑一致性比较实际上是多边形场景图的拓扑同胚的判 断，核心是对多边形场景的图结构的描述，需要重点解决多边形的布局和排序问题。利用现有的联系图虽然可以表达多边形场景的网状关系，但其不利于对多边形场景的拓扑关系的整体布局的表达和认知，采用递归算法判断多边形场景的拓扑相等关系，需要建立不同多边形场景中单个多边形间的映射关系，计算效率不高。目前，寻找一种简单而有效的方法对多边形场景的拓扑同胚进行描述，从而可对不同的多边形场景进行判断，仍然是一个函待解决的问题。

发明内容

本发明要解决的技术问题是提供一种多边形场景拓扑关系表达方法，以减少或避免前面所提到的问题。

为解决上述技术问题，本发明提供了一种多边形场景拓扑关系表达方法，其用于对多边形场景的拓扑结构进行表述，所述多边形场景是由相接不含洞的多边形集合构成的连续铺盖，是一种有向简单图，多边形之间既不能有裂隙，也不能有叠置；多边形间只有两种关系：相离和相接；特殊地，如果两个多边形只有一个接点，没有公共边，按相离关系处理，其包括如下步骤，

步骤A，将所述多边形场景进行拓扑同胚变化并生成拓扑同胚图，

步骤B，对步骤A生成的拓扑同胚图生成对偶图，然后提取所述对偶图中多边形间的邻近关系，

步骤C，根据步骤B所获得的多边形间的邻近关系，采用形状文法理论对多边形进行组合表达，建立多边形形状集合，并采用K阶邻近对多边形进行排序，生成多边形的K阶邻近编码字符串来表述多边形场景的拓扑结构。

优选地，步骤B中的所述邻近关系包括每一个多边形ID、次数及其一阶邻近多边形ID。

优选地，所述多边形ID为3位编码。

优选地，步骤C中的编码字符串采用7位编码，其中：1-2位01-99标示邻近阶数，3-4位01-99标示该多边形边数，5-7位000-999标示上一阶多边 形的标示码；

；本发明所提供的一种多边形场景拓扑关系表达方法，可使用简单的字符串来表示多边形场景拓扑关系，因此可将多边形场景拓扑同胚的判断转化为简单的字符串比较，这样就不需要对多边形进行一对一的匹配，从而提高多边形场景拓扑同胚的判断的效率。

附图说明

以下附图仅旨在于对本发明做示意性说明和解释，并不限定本发明的范围。其中，

图1为一种多边形场景的结构示意图；

图2为两个待比对拓扑一致性的多边形场景的结构示意图；

图3为根据本发明的一个具体实施例的一种多边形场景拓扑关系表达方法的对多边形进行拓扑同胚变化的原理示意图；

图4为图1所示的多边形场景经过拓扑同胚变化前后的对比示意图；

图5为图4中拓扑同胚图生成的对偶图的示意图；

图6为根据本发明的一个具体实施例的一种多边形场景拓扑关系表达方法的一个简单多边形场景的编码转换示意图

具体实施方式

为了对本发明的技术特征、目的和效果有更加清楚的理解，现说明本发明的具体实施方式。

本发明提供了一种多边形场景拓扑关系表达方法，其用于对多边形场景的拓扑结构进行表述，所述多边形场景是由相接不含洞的多边形集合构成的连续铺盖，是一种有向简单图，多边形之间既不能有裂隙，也不能有叠置；多边形间只有两种关系：相离和相接；特殊地，如果两个多边形只有一个接点，没有公共边，按相离关系处理，其包括如下步骤，

步骤A，将所述多边形场景进行拓扑同胚变化并生成拓扑同胚图，

参见图1所示，多边形场景是由相接不含洞的多边形集合{Poly₁,Poly₂,Poly₃……Poly_n}构成的连续铺盖，是一种有向简单图，可记为G＝{Poly₁,Poly₂,Poly₃……Poly_n}。

多边形场景图形的拓扑性质体现了多边形场景整体结构上的特性。拓扑不变量是几何图形在拓扑变换下保持不变的性质。在本发明中，将拓扑不变量归结为：多边形类型(type)、多边形数量(number)、多边形关系(relation)、多边形排列(order)四种。

在本发明中，对多边形场景进行拓扑同胚变化的目的是在保持多边形场景拓扑性质的条件下，将多边形场景进行简化，去掉不必要的二度节点，从而将对多边形场景拓扑性质的研究转化为对简化后的拓扑同胚图拓扑性质的研究，提高计算效率。

拓扑同胚变化包括，挤压、拉伸、扭曲，只要不发生撕裂、粘连，从而破坏其整体结构，拓扑性质就保持不变(尤承业，2008)。针对多边形场景拓扑同胚变化，主要采用两种方法：1)拉伸法(去点法)，从直观上相当于将两结点间的折线拉直，实际操作中是去掉度数为2的节点，保留结点；2)结点搜索法，采用平面扫描算法搜索度数大于2的结点，重新生成多边形。每个内部多边形至少有三个结点，对于边界多边形，如果只有两个结点，则可在该多边形两结点连线的外侧的边界上任取一点作为伪结点，构成多边形。

图3为根据本发明的一个具体实施例的一种多边形场景拓扑关系表达方法的对多边形进行拓扑同胚变化的原理示意图，参见图3所示，在采用结点搜索法时，可将左侧多边形场景拓扑同胚变换为右侧的多边形场景。这样可方便后继对多边形场景进行进一步简化及数据化表达。

经过拓扑同胚变化后，多边形场景的多边形类型、数量，多边形间拓扑关系，多边形排列顺序等拓扑不变量保持不变，变化前后各个拓扑不变量是一对一映射关系。经过拓扑同胚变化，将多边形简化，生成简化的拓扑同胚图，维持多边形间拓扑性质不变，便于进行多边形拓扑关系计算。

图4表示的是图1所示的多边形场景经过拓扑同胚变化前后的对比示意 图，参见图4所示，图1所示的多边形场景拓扑同胚变化前后，其同胚图仍然是多边形场景。也就是说，经过拓扑同胚变化后，对应多边形满足以下条件：

1)各种类型的多边形数量不变

设G₁，G₂为两个多边形场景，有Poly(i)∈G₁，Poly(i)∈G₂，

Num₁(Poly(i)),Num₂(Poly(i))，(i≥3)分别表示G₁，G₂中对应Poly(i)的数量，则对于任意i≥3，恒有Num₁(Poly(i))＝Num₂(Poly(i))。

2)对应多边形间拓扑关系不变

设G₁，G₂为两个多边形场景，对任意多边形Poly(i₁)∈G₁，Poly(j₁)∈G₁，有Poly(i₁)∈G₂，Poly(j₁)∈G₂与其对应，用Topo₁(Poly(i₁),Poly(j₁))、Topo₂(Poly(i₁),Poly(j₁))分别表示G₁，G₂场景中对应多边形间的拓扑关系，则有Topo₁(Poly(i₁),Poly(j₁))＝Topo₂(Poly(i₁),Poly(j₁))。

3)对应多边形排列顺序不变

按照某种规则对多边形进行标号和排序后，对应多边形排列顺序不变。

步骤B，对步骤A生成的拓扑同胚图生成对偶图，然后提取所述对偶图中多边形间的邻近关系，

为了能够进一步将图形数据化，在完成步骤A，生成拓扑同胚图后，计算同胚图中每一个多边形的质心坐标，连接相邻多边形质心，这样就可以构成多边形场景的对偶图，从而可确定同胚图中多边形的邻近关系。按照顺时针方向对每一个多边形的邻近多边形进行排序。记录每一个多边形ID(可采用3位标识码)、次数及其一阶邻近多边形ID，从而可以获得邻近关系表(Adj_table)。

图5为图4中拓扑同胚图生成的对偶图的示意图，参见图5所示，生成对偶图后，更有利于提取所述对偶图中多边形间的邻近关系，也就是更有利于图形的数据化。

步骤C，根据步骤B所获得的多边形间的邻近关系，采用形状文法理论 对多边形进行组合表达，建立多边形形状集合，并采用K阶邻近对多边形进行排序，生成多边形的K阶邻近编码字符串来表述多边形场景的拓扑结构。

多边形场景是一个空间铺盖，多边形场景中不存在裂隙和重叠多边形，因此，相邻多边形间只可能是相接关系，不相邻的多边形间一定是相离关系，因此如果按照多边形的邻接关系对多边形进行排序并编码表达，实际上隐含了多边形间的拓扑关系类型，同样，多边形的数量可以通过排序和编码隐性表达。因此表达多边形场景的拓扑结构，实际上是按照一定的规则，将多边形进行顺序排列，来表达多边形间的邻近关系。问题的关键是如何对多边形进行排序表达。本发明采用形状文法理论对多边形组构进行标示，并采用K阶邻近对邻接的多边形进行排序，生成多边形的K阶邻近编码字符串来表述多边形场景的拓扑结构。

形状文法是George Stiny在1972年基于符号语言(formal language)所提出。其主要目的是要找寻出隐藏的形状(包括建筑物)组构规则。利用规则区别类型，便于计算机编程产生出许多同一类型的形状(建筑物)。

陈军等(2004)利用欧氏距离定义k阶邻近。本发明关心的是多边形间的邻近程度，这种邻近程度取决于多边形在平面图上的空间布局，也就是多边形间相隔的多边形的个数，将其定义为邻近距离。本发明利用两个多边形间最小邻近距离定义k阶邻近。

假设目标集合G＝{Poly₁,Poly₂,Poly₃……Poly_n}为平面上n个多边形，共同构成平面多边形铺盖，如果两个多边形Poly_i,Poly_j重合，则其邻近距离为d(Poly_i,Poly_j)＝0，如果具有公共边，则其邻近距离为d(Poly_i,Poly_j)＝1，如果Poly_i,Poly_j之间间隔多边形的个数为m,则d(Poly_i,Poly_j)＝m+1。k阶邻近N(Poly_i,Poly_j)定义为：

N(Poly_i,Poly_j)＝{k|k＝min(d(Poly_i,Poly_j)}

在获得步骤B的邻近关系表，即每个多边形ID数据后，可确定一个初始多边形。根据需要，初始多边形可以指定任意多边形。初始多边形选定后，即可对多边形场景中的每个多边形进行标号，标号规则为：

(1)按照多边形边界线段流方向对所有多边形的结点排序

将每个多边形按照线段流方向对结点进行排序，在本发明中，规定每一个多边形线段流的方向均为顺时针方向。

(2)将每一阶邻近多边形按照目标多边形结点顺序顺时针排序

(3)将邻近多边形编码，采用7位编码，其中：

1-2位01-99标示邻近阶数(纵向关系)，当然，根据需要可以适当扩展。

3-4位01-99标示该多边形边数(多边形类型)

5-7位000-999标示上一阶多边形的标示码(纵向关系)

至此，即可完成对一个多边形场景的编码转换，也就是说，可以用一串数字编码来表述一个多边形场景。

图6为一个简单多边形场景的编码转换示意图，参见图6所示，按照本发明步骤C的编码方法，图6的五边形及其一阶顺序排列的邻近多边形可用编码010700101080010106001010600101050010106001表示。

为了简化行文，本发明所提供的基于形状文法+K阶邻近描述多边形场景的方法可称作Shape-K-Order(简称SKO)描述法。

如前所述，多边形场景的同胚图也必然是多边形场景。如果两个多边形场景的同胚图相等，则两个多边形场景拓扑相等。如果两个多边形场景中所有对应类型的多边形数目相等且排列顺序一致，则两个多边形场景必然拓扑同胚。因此判断两个多边形场景拓扑同胚，可首先判断对应类型的多边形数目是否相等，如果不相等，则可直接判断为非拓扑同胚，如果相等，分别按照本发明步骤A-C所提供的方法对其进行SKO编码描述，将多边形场景拓扑同胚的判断转化为简单的字符串比较，这样就不需要对多边形进行一对一的匹配，从而提高多边形场景拓扑同胚的判断的效率。

采用SKO编码方法判断两个多边形场景拓扑同胚，必须保证两个多边 形场景的初始多边形是一一对应。初始多边形选择可采用以下方法：首先统计多边形场景中各种类型多边形的数量，找出数量最少的多边形类型，然后比较两个多边形场景中该类型多边形中每一个多边形的一阶SKO编码，如果两个多边形场景中有且只有一对多边形一阶SKO编码相等，则该两个多边形是一一对应的，可作为初始多边形，分别计算其SKO编码，比较并判断两个多边形场景是否拓扑同胚；如果两个多边形场景中没有一对多边形一阶SKO编码相等，则该两个多边形场景非拓扑同胚；如果两个多边形场景中有多(m)对多边形一阶SKO编码相等，则在其中选择一个属于多边形场景A的多边形(a)，计算其SKO编码，对于属于多边形场景B的多边形(b₁,b₂…b_m)分别计算其二阶SKO编码，与多边形(a)的二阶SKO编码比较，以此类推，直到在多边形场景B中找到与多边形(a)的第k阶SKO编码相等的唯一的多边形(b)，计算其全部SKO编码，与多边形(a)的SKO编码，比较二者是否拓扑相等，从而判断两个多边形场景拓扑同胚。

本发明所提供的一种多边形场景拓扑关系表达方法，可使用简单的字符串来表示多边形场景拓扑关系，因此可将多边形场景拓扑同胚的判断转化为简单的字符串比较，这样就不需要对多边形进行一对一的匹配，从而提高多边形场景拓扑同胚的判断的效率。

本领域技术人员应当理解，虽然本发明是按照多个实施例的方式进行描述的，但是并非每个实施例仅包含一个独立的技术方案。说明书中如此叙述仅仅是为了清楚起见，本领域技术人员应当将说明书作为一个整体加以理解，并将各实施例中所涉及的技术方案看作是可以相互组合成不同实施例的方式来理解本发明的保护范围。

以上所述仅为本发明示意性的具体实施方式，并非用以限定本发明的范围。任何本领域的技术人员，在不脱离本发明的构思和原则的前提下所作的等同变化、修改与结合，均应属于本发明保护的范围。

本发明中所引用的参考文献包括：

Chen Jun,Zhao Renliang,and Li Zhilin,2004,Voronoi-based k-orderneighbour relations for spatial analysis,ISPRS>Remote>,60-72

Clare E.H,2000,Geometric symmetry in patterns and tilings，TextileInstitute woodhead publishing limited

Paiva J,1998,Topological equivalence and similarity in multi-representation geographic databases，USA:The Graduate School University ofMaineEgenhofer M,1994,Deriving the composition of binary topologicalrelations.Journal of Visual Languages and Computing 5(2):133-149

Egenhofer M 1996,Multi-modal spatial querying.In M-J Kraak andMMolenaar(Eds.),Seventh International Symposium on Spatial Data Handling(SDH'96),Delft,The Netherlands,785-799

Egenhofer M,1997,Query processing in Spatial-Query-by-Sketch.Journalof Visual Languages and Computing 8(4):403-424

Haarslev V and Wessel M,1997,Querying GIS with animated spatialsketches.In Proceedings of Symposium on Visual Languages(VL'97),Capri,Italy,IEEE Computer Society Press,197-204

Nedas A,and Egenhofer M,2008,Spatial-Scene Similarity Queries，Transactions in GIS 12(6),661-681

尤承业，2008，基础拓扑学讲义，北京：北京大学出版社

孙惠泉，2004，图论及其应用，北京：科学出版社。

去获取专利，查看全文>