基于约束狄郎宁三角网技术的多个区域拓扑层叠置分析方法

摘要

本发明公开了一种基于约束Delaunay三角网技术的多个区域拓扑层叠置分析方法；本发明充分利用了Delaunay三角网的点、边以及三角形的邻接性，能从提高自适应性能力的角度有效避免弧段求交生成新弧段和新结点、新结点和新弧段间的拓扑关系建立、孤岛的归属处理以及叠置新区域属性获取时的大量无效判断，从而大大提高处理效率，同时由于本发明在多个区域拓扑层叠置分析的各个过程是维护和操作同一个约束Delaunay三角网，使得计算机内存的利用效率高且管理方便，上述诸多特点提高了多个区域拓扑层叠置分析的效率。

说明书

技术领域

本发明属于地理信息系统(GIS)中二维多个区域拓扑层叠置分析技术领域，特别地，涉及一种基于约束狄郎宁(Delaunay)三角网技术的多个区域拓扑层叠置分析方法。

背景技术

叠置分析是将两个或多个GIS地图要素层进行叠加产生新的要素层，它是GIS中最常用的提取隐含信息的手段之一。叠置分析不仅包含空间关系的比较，还包含属性关系的比较。叠置分析主要包括：视觉信息的叠置；点与区域的叠置；线与区域的叠置；区域之间的叠置；栅格图层叠置等。其中区域之间的叠置是最常用最复杂的叠置分析。区域之间的叠置是指将多个不同区域图层的要素叠合，产生新的区域要素，以解决地理变量的多准则分析、区域多重属性的模拟分析、地理特征的动态变化分析、区域信息提取等。多个区域拓扑层叠置分析涉及计算机图形学、计算几何、拓扑学、地球科学等多个领域，是“数字地球”的核心技术之一，也是GIS领域研究的难点和热点之一。

多个区域拓扑层叠置分析过程可主要归结为：(1)参与叠置分析的所有区域拓扑层的弧段之间求交生成新弧段和新结点；(2)新结点与新弧段之间拓扑关系的建立；(3)叠置新区域边界多边形组织、闭合边界多边形相邻关系和包含关系(孤岛归属)的建立；(4)叠置新区域属性获取等步骤。

目前，在上述各处理环节中，针对参与叠置分析的区域拓扑层的弧段求交生成新弧段前人提出了平面扫描算法和网格化算法等，这些算法虽然在一定程度上提高了弧段求交生成新弧段的效率，但是算法中仍然存在大量的无效求交测试，因此处理大量甚至海量空间数据时的效率仍比较低，另外现有的方法对求交稳定性很少涉及，即使有些算法初步涉及了求交稳定性，也存在计算量大的缺点；针对弧段求交获得的新结点与新弧段之间拓扑关系的建立前人提出了基于结点的旋转角度算法，由于算法中存在大量的浮点运算，故效率较低；而关于孤岛的归属处理前人提出了射线法、累计角度法、编码法以及改进的射线法等，这些算法的处理时间随着孤岛数量和区域数量的递增呈明显的非线性增加(由于GIS管理的空间实体数量往往是巨大的，因此所需的处理时间是难以接受的)，从而降低了叠置分析的效率；对于叠置新区域的属性获取，前人提出了在新区域内生成一个内点，再用射线法、累计角度法、编码法或改进的射线法等确定该内点在各个参与叠置分析的区域拓扑层中所属的区域，进而获取叠置新区域在各个参与叠置分析的区域拓扑层中的属性，这种处理方法存在内点生成计算量大，同时确定内点在各个参与叠置分析的区域拓扑层中所属的区域的处理时间随着区域数量和参与叠置分析的区域拓扑层数的递增呈明显的非线性增加，从而降低了叠置分析的效率。

发明内容

本发明的目的在于针对现有技术的不足，提供一种基于约束Delaunay三角网技术的多个区域拓扑层叠置分析方法，由于充分利用了Delaunay三角网的点、边以及三角形的邻接特性，解决了现有多个区域拓扑层叠置分析时存在的效率不高、求交稳定性和模糊处理能力差的缺点，并能充分利用计算机系统内存资源。

本发明通过以下技术方案来实现该发明目的：一种基于约束Delaunay三角网技术的多个区域拓扑层叠置分析方法，包括以下步骤：

(1)确定有效模糊距离；

(2)由各个参与叠置分析的区域拓扑层的弧段点构建Delaunay三角网；

(3)根据步骤(1)确定的有效模糊距离，对步骤(2)构建的Delaunay三角网进行点与点的模糊归并处理；

(4)由各个参与叠置分析的区域拓扑层的弧段约束步骤(3)获得的Delaunay三角网实现求交；

(5)由步骤(4)获得的约束Delaunay三角网中的约束边组织新弧段和确定新结点；

(6)利用步骤(4)获得的约束Delaunay三角网构建步骤(5)获得的新结点和新弧段之间的拓扑关系；

(7)根据新结点与新弧段间的拓扑关系组织边界多边形，并确定边界多边形是内多边形还是外多边形，所述外多边形为孤岛；

(8)在步骤(4)获得的约束Delaunay三角网中，利用射线法进行孤岛归属处理；

(9)对经过步骤(8)处理获得的叠置新区域，在步骤(4)获得的约束Delaunay三角网中建立虚拟内点，再由虚拟内点利用射线法从各个参与叠置分析的区域拓扑层获取叠置新区域的属性。

本发明的有益效果是：

(1)通过Delaunay三角网实现点与点、点与边的模糊归并处理，使模糊处理简单高效。模糊处理是多个区域拓扑层叠置分析的重要环节之一，其可以提高叠置分析的健壮性，同时可以满足实际应用时的精度要求。由于模糊处理过程中充分利用了Delaunay三角网的自适应性和点、边以及三角形的邻接特性，因此大大减少了点与点、点与边之间的无效归并判断次数，从而提高了模糊处理的效率。

(2)通过参与叠置分析的各个区域拓扑层的弧段在Delaunay三角网中进行约束快速实现求交生成新弧段和新结点。由于求交过程中充分利用了Delaunay三角网的自适应性和点、边以及三角形的邻接特性，因此大大减少了求交过程中线段与线段之间的无效求交判断次数(因为实际情况是绝大多数线段之间是并不存在交点的)，从而提高了求交的效率，同时求交的结果直接反映在Delaunay三角网中(在Delaunay三角网中插入新的点)，避免了以往求交算法的复杂处理，提高了多个区域拓扑层叠置分析的效率。

(3)以往求交后得到的新结点和新弧段之间拓扑关系的建立是通过结点的匹配和弧段邻接关系的建立这两个步骤来实现的，结点的匹配和弧段邻接关系的建立需要大量的处理时间，从而降低了多个区域拓扑层叠置分析的效率，本发明由于新结点信息和新弧段信息均隐含地存在于约束Delaunay三角网中，因此只需要对约束Delaunay三角网中的点进行一次旋转搜索就可以完成同一结点上弧段与弧段之间拓扑关系的建立，从而提高了效率。

(4)孤岛归属处理也是影响多个区域拓扑层叠置分析效率的重要环节之一，以往都是通过孤岛(外多边形)与内多边形之间包含关系的判断来实现的，算法效率均比较低，本发明通过由参与叠置分析的各个区域拓扑层的弧段点构建约束Delaunay三角网，新弧段的各个线段都隐含地存在于约束Delaunay三角网的约束边中，因此由约束Delaunay三角网中的孤岛的左极点向左引射线，通过射线与约束Delaunay三角网中的约束边的相交情况就可以快速实现孤岛的归属处理。

(5)多个区域拓扑层叠置生成新的区域拓扑层，该区域拓扑层的所有叠置新区域的属性获取效率也是至关重要的，本发明通过叠置新区域在约束Delaunay三角网中的位置，将叠置新区域的最左侧的三角形的重心作为该区域的虚拟内点，再在约束Delaunay三角网中由虚拟内点向左引射线，通过射线与约束Delaunay三角网中的约束边的相交情况，并根据约束边的原约束弧段快速获取虚拟内点在各个参与叠置分析的区域拓扑层的所属区域，进而获取叠置新区域在各个参与叠置分析的区域拓扑层的属性信息。

(6)本发明将多个区域拓扑层叠置分析的各个处理环节统一到了Delaunay三角网的处理和操作中，整个叠置分析的过程都是围绕Delaunay三角网展开的，而且Delaunay三角网的数据结构非常适合大块内存的高效操作，为提高叠置分析效率奠定了基础。

(7)本发明算法结构简单清晰，实现方便。

附图说明

图1是有关定义说明图；

图2是一种实现本发明的技术流程图；

图3～16是基于约束Delaunay三角网技术实现多个区域拓扑层叠置分析的过程示意图；其中，

图3是说明本发明实现过程的区域拓扑层A；

图4是说明本发明实现过程的区域拓扑层B；

图5是区域拓扑层A和B的叠置结果；

图6是由区域拓扑层A和B的弧段点构建的Delaunay三角网；

图7是基于Delaunay三角网实现弧段点的模糊归并处理；

图8～12是由参与叠置分析的区域拓扑层的弧段对Delaunay三角网进行约束求交处理过程；

图11和图12是基于Delaunay三角网的点与边的模糊归并处理过程；

图13是基于约束Delaunay三角网的新弧段组织、新结点确定以及新边界多边形组织；

图14是基于约束Delaunay三角网的孤岛归属处理；

图15是基于约束Delaunay三角网获取叠置新区域的属性；

图16是最后叠置分析后的新区域拓扑层。

图中，R是区域编号，a是弧段编号，V是弧段点编号，N是弧段结点编号(是特殊的弧段点)，L是虚拟内点编号，G是孤岛编号，I是交点。在图6～15中的三角网中，虚线为普通三角网边，实线为约束三角网边。

具体实施方式

下面以两个区域拓扑层的叠置分析为例，根据附图详细说明本发明，本发明的目的和效果将变得更加明显。

为方便下面的描述，特做如下定义：

定义1.边界多边形：由于弧段均被其左右两个区域所共用，以弧段的某一侧搜索其后续弧段直至封闭，便构成了一个围绕这一侧区域的多边形，称为边界多边形(如附图1中弧段a₁右侧以及弧段a₂左侧即构成了围绕区域R₁的边界多边形)。

定义2.内多边形：如果边界多边形所包围的区域在边界多边形的内部，则称该边界多边形为内多边形(如附图1中弧段a₁右侧以及弧段a₂左侧所构成的边界多边形)。

定义3.外多边形(孤岛)：如果边界多边形所包围的区域在边界多边形的外部，则称该边界多边形为外多边形(如附图1中弧段a₆左侧和弧段a₅左侧所构成的边界多边形以及弧段a₁、a₃、a₄左侧所构成的边界多边形均为外多边形)。

定义4.拓扑正向边界多边形：对于边界多边形，当沿其前进时(前进方向即为边界多边形坐标点的记录次序)，边界多边形所包围的区域始终在前进方向的左侧，则称该边界多边形是具有拓扑正向的边界多边形。

一个区域的边界可以由多个边界多边形构成(如附图1中的区域R₂，其边界是由弧段-a₂、-a₄、-a₃构成的边界多边形和弧段a₅、a₆构成的边界多边形构成的，其中-a₂、-a₄、-a₃中的“负号”是为了满足拓扑正向边界多边形的需要)，且其中只有一个内多边形，其余都是外多边形，由于外多边形与内多边形之间没有直接的连通关系，为了正确描述区域的边界，必须确定外多边形与哪个内多边形(处于工作区边界的外多边形没有包含它的内多边形)共同构成某区域的边界，这即为孤岛的归属问题。

本发明基于约束Delaunay三角网技术的多个区域拓扑层叠置分析方法，包括以下步骤：

本发明方法的第一步为确定有效模糊距离，有效模糊距离是由坐标表示方法确定坐标数据的有效位数，结合参与叠置分析的各个区域拓扑层的弧段点的坐标范围确定工作区的小数点后的有效位数，当给定的模糊距离小于该有效位数时，取该有效位数为有效模糊距离，否则原模糊距离就是有效模糊距离。例如：当用户给定模糊距离为0.00000001，空间数据的坐标范围为：左下角(40345301.43，3327000.5)右上角(40745301.43，3347000.7)，且空间数据坐标以八字节的双精度浮点数存储时，有效模糊距离计算方法为：由于八字节双精度浮点数的有效位数为16位，而空间数据坐标最大值为40745301.43，此时八字节双精度浮点数表示的坐标在小数点后的有效位数为7位，又用户给定的模糊距离为小数后8位，以选择大的为原则，最后的有效模糊距离为0.0000001。

本发明方法的第二步为由参与叠置分析的各个区域拓扑层的弧段点建立Delaunay三角网。具体建立Delaunay三角网的过程如下：首先将各个区域拓扑层的弧段点进行排序，然后从中剔除重复点形成Delaunay点集，再获得各个区域拓扑层的弧段点在Delaunay点集中的位置(目的是建立各个区域拓扑层的弧段点与Delaunay点集的对应关系，方便后面的约束处理)，最后由Delaunay点集构建Delaunay三角网，附图3和附图4为两个区域拓扑层，附图5为剔除了重复点的各个区域拓扑层的弧段点构成的Delaunay点集，附图6为由Delaunay点集构成的Delaunay三角网。

本发明方法的第三步为基于Delaunay三角网的点与点的模糊归并处理，模糊处理有提高系统稳定性和满足实际精度要求两种作用，在Delaunay三角网中实现点与点的模糊归并处理是以点为着眼点进行的，逐个扫描Delaunay三角网中的点，再利用Delaunay三角网的邻接关系在当前点的周围寻找小于有效模糊距离的点，邻近的点在Delaunay三角网中是有边连接的(参见附图6中的和点)，若存在小于有效模糊距离的点则将该点从Delaunay三角网剔除。参见附图6，由于和点之间的距离小于有效模糊距离，故需要进行模糊归并处理(参见附图7，在搜索点时，点被模糊归并了)。

本发明方法的第四步由参与叠置分析的各个区域拓扑层的弧段约束Delaunay三角网实现求交及点与边的模糊归并。

约束求交的具体过程为：(1)当弧段的线段本身就是Delaunay三角网的边，如附图6中线段是Delaunay三角网的边，此时只需直接置该Delaunay三角网的边为约束边(见附图8)；(2)当弧段的线段不是Delaunay三角网的边，且与该线段相交的Delaunay三角网边均不是约束边，如附图6所示，线段不是Delaunay三角网的边，与之相交的Delaunay三角网的边是、和，且上述三条三角网的边不是约束边，此时只需对与相交的所有的Delaunay三角网的边不断进行对角线交换，直至线段是Delaunay三角网的边为止，再置约束标志，如附图9所示；(3)当弧段的线段不是Delaunay三角网的边，且与该线段相交的Delaunay三角网边中存在约束边，如附图9所示，线段不是Delaunay三角网的边，且与之相交的Delaunay三角网的边中是约束边，此时计算线段与Delaunay三角网约束边的交点，并将交点插入到Delaunay三角网中，最后对被分割的线段(两条)分别再进行约束处理即可，如附图10就是插入交点I后，分别再对线段和进行约束的结果。

约束实现点与边的模糊处理的具体过程为：(1)当由弧段的线段对Delaunay三角网约束时，若线段本身就是Delaunay三角网的边，置该Delaunay三角网的边为约束边，并计算共用该边的两个三角形的第三点与该边的距离，若距离小于有效模糊距离，则将约束信息进行移动，并且该过程是递归的，约束信息移动后，对非约束Delaunay三角网边再进行优化处理；(2)当由弧段的线段对Delaunay三角网约束时，若线段不是Delaunay三角网的边，且与线段相交的Delaunay三角网边均不是约束边，此时只需对与线段相交的所有的Delaunay三角网的边不断进行对角线交换，直至线段是Delaunay三角网的边为止，再置约束标志，并计算共用该边的两个三角形的第三点与该边的距离，若距离小于有效模糊距离，则将约束信息进行移动，并且该过程是递归的，约束信息移动后，对影响域内非约束Delaunay三角网边再进行优化处理，附图11为区域拓扑层A的线段约束后的结果，由于线段与点的距离小于模糊距离，所以将的约束信息转移到和上，见附图12，之后再进行优化，得到的结果见附图10；(3)当由弧段的线段对Delaunay三角网约束时，若线段不是Delaunay三角网的边，且与线段相交的Delaunay三角网边中存在约束边，此时计算线段与Delaunay三角网约束边的交点，再计算该交点与Delaunay三角网中的点的距离，进一步处理如下：①若距离大于有效模糊距离，则在Delaunay三角网中插入该交点，对被分割的线段(两条)分别再进行约束及点与边的约束模糊处理即可；②若距离小于有效模糊距离，则把与交点距离小于有效模糊距离的Delaunay三角网中的点作为分割线段的点，再对被分割的线段(两条)分别再进行约束及点与边的约束模糊处理即可。

本发明方法的第五步由约束Delaunay三角网组织新弧段和新结点，具体过程是：(1)首先从有三条(含)以上约束边的Delaunay三角网点(作为当然结点)开始搜索弧段，如附图13，由点N₁可以搜索出弧段a₁(由点V₃和V₁构成)、a₂(由点V₁和V₄构成)、a₃(由点V₂和V₁构成)；(2)再由Delaunay三角网中未被弧段使用过的有约束边通过的点(有两条约束边通过的Delaunay三角网点)开始搜索弧段，此时均为自封闭的弧段，如附图13，由点N₆可以搜索出弧段a₉。另外为了方便下面建立新结点与新弧段拓扑关系，对于N₆这样的结点在Delaunay三角网中要给予特别的标志，以区别于普通的只有两条约束边通过的点。

本发明方法的第六步由约束Delaunay三角网建立新结点与新弧段拓扑关系，即通过搜索Delaunay三角网中的所有点来快速建立新结点与新弧段之间的拓扑关系，具体过程如下：当搜索的Delaunay三角网中的点是结点时(通过该点的约束边大于等于三条，或该点是在弧段组织时特别标注的有两条约束边通过的点)，逆时针绕该点搜索Delaunay三角网边，若Delaunay三角网边有弧段通过，则获得弧段端点的结点信息及通过该结点的弧段信息，并且在搜索过程中建立弧段之间的邻接关系。如附图13所示，有四条Delaunay三角网边与结点N₅相连接，其中有三条边有弧段通过，在绕结点N₅搜索后即可获得：(1)弧段a₈、-a₇、-a₆以结点N₅为弧段的端点(-a₇、-a₆表示该弧段的终止端点为结点N₅)；(2)a₈弧段在结点N₅上的逆时针邻接弧段为-a₇、顺时针邻接弧段为-a₆(同理也可获得弧段-a₇、-a₆的邻接弧段)。

本发明方法的第七步是组织边界多边形并识别孤岛，具体是以弧段为着眼点，利用结点与弧段拓扑关系，由弧段的两侧分别进行搜索组织边界多边形，其中弧段左侧搜索时，是顺着弧段的方向进行的，弧段右侧搜索时，是逆着弧段的方向进行的，这种搜索约定可以保证搜索的边界多边形具有以下特点：(1)内多边形均为逆时针的，其积分面积为负；(2)外多边形(孤岛)均为顺时针的，其积分面积为正。如附图13，从弧段a₈的左侧顺着弧段方向搜索的结果是弧段a₈、-a₅、a₇构成的边界多边形(其中-a₅表示边界多边形的方向与弧段方向相反)，由于这个边界多边形是逆时针的，所以是内多边形，从弧段a₈的右侧逆着弧段方向搜索的结果是弧段-a₈、-a₆、a₃、-a₁构成的边界多边形，由于这个边界多边形是顺时针的，是外多边形(孤岛)。

本发明方法的第八步是由约束Delaunay三角网进行孤岛的快速归属处理，具体是搜索孤岛的极点(这里以左极点为例)，并在约束Delaunay三角网中由该点向左侧引射线，根据射线与约束Delaunay三角网中的约束边(其构成新弧段)的相交情况以及交点的远近确定其归属关系，如附图14，弧段-a₉构成的孤岛，其左极点为G₂，其向左的射线与约束Delaunay三角网中组成弧段a₇的Delaunay三角网约束边相交，并且G₂点位于弧段a₇的左侧，因此弧段-a₉构成的孤岛归属于弧段a₈、-a₅、a₇构成的内多边形，并与其共同构成新区域R_A2-B2的边界(如附图16)，而新弧段-a₈、-a₆、a₃、-a₁构成的孤岛其左极点G₁向左的射线未与任何Delaunay三角网约束边相交，这样的孤岛构成整个工作区的边界。

本发明方法的第九步是由约束Delaunay三角网快速获得叠置后形成的各个新区域的属性。具体是首先确定新生成区域的虚拟内点，即由第八步生成的各个新区域，在约束Delaunay三角网中确定包含在新区域中的最左侧的三角形，以此三角形的重心作为新区域的虚拟内点；其次由虚拟内点向左引射线，根据射线与约束Delaunay三角网中的约束边(约束该边的原区域拓扑层的弧段)的相交情况以及交点的远近确定虚拟内点被各个参与叠置分析的区域拓扑层中的哪个区域包含，并把在相应区域拓扑层中的属性转移给当前的新区域。如附图16中新区域R_A2-B2对应的约束Delaunay三角网(附图15)中的最左侧的三角形的重心为L₃，由L₃向左引射线，其与约束Delaunay三角网中组成弧段a₇和弧段a₆的Delaunay三角网约束边V₄V₆和V₂V₅相交，而约束边V₄V₆是由附图4的弧段约束而得，约束边V₂V₅是由附图3的弧段和附图4的弧段约束而得，并且L₃点位于弧段a₇的左侧，也就是L₃点位于附图4中的弧段的左侧，因此可以将区域拓扑层B的弧段左侧的区域属性(即区域的属性)转移到新区域中，同时L₃点位于弧段a₆的左侧，也就是L₃点位于附图3中的弧段的左侧，因此可以将区域拓扑层A的弧段左侧的区域属性(即区域的属性)转移到新区域中(因区域R_A2-B2的区域拓扑层B的属性已经获取，故无须再处理附图4的弧段约束情况了)，这样便获得了新区域R_A2-B2的属性。

上述实施例用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。