一种基于Voronoi图实现湖泊中心点查找算法

摘要

本发明提供一种基于Voronoi图实现湖泊中心点查找的算法。在研究湖泊变化过程中，需要找到最稳定的点作为控制点并进行多期湖泊的配准，而中心点的查找问题可转化为求该多边形最大内圆(内接或内切)的圆心问题。该方法首先分析几种简单多边形的Voronoi图生成算法，再对任意多边形进行二叉树递归，直到化简到几种简单多边形；对含有岛的复杂多边形，首先计算复杂多边形外环内部与内环外部的Voronoi图，再通过分析相应的线段相交次序实现复杂多边形Voronoi图的生成，最后通过遍历相应的交点找到多边形的最大内圆圆心点；通过算法复杂度分析，该算法为目前为止复杂度最低的方法，亦可应用到其他类似多边形最大内圆中。

说明书

技术领域

本发明涉及计算几何及地理信息系统空间分析方法，具体地说，涉及计算几何中的任意复杂多边形的Voronoi图的生成算法，以及在此基础上采用地理信息系统的空间分析技术实现湖泊中心点查找算法，本发明可适用于多期遥感影像湖泊提取后结果的湖泊中心点查找、匹配及变化分析等。 

背景技术

在进行遥感多期长时相湖泊变化与分析过程中，需要对多期的影像及湖泊提取结果进行配准，在此基础上可进行湖泊变化分析等应用，可以采用湖泊的中心点作为多期影像间的配准点来实现，相应的参考文献包括Sheng Y，Shal C A，Smith L C.2008.Automated image registration for hydrologic change detection in the lake-rich Arctic.IEEE Geosci.Remote Sens.Lett.，5(3)：414-418、Shah C A，Sheng Y W，Smith L C.2008.Automated Image Registration Based on Pseudo invariant Metrics of Dynamic Land-Surface Features.IEEE Transactions on Geoscience and Remote Sensing，46：3908-3916等。 

对于湖泊来说，可将其表示为首尾依次连接的多边形，而湖泊的中心点就是湖泊内部距离各个边(湖岸)最远处的点，从计算几何角度来看就是求任意多边形的最大内圆(内接或内切)圆心问题。对于矢量多边形的最大内圆圆心点的计算方法，目前已有文献中大多是针对凸多边形或特定多边形的最大内圆问题的求解，而对任意多边形的最大内圆求解问题研究不多，相应的参考文献见Berman P，Lingas A.1997.A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon.Theoretical Computer Science，174：193-202、Ramamurthy R，Farouki R T.1999.Voronoi diagram and medial axis algorithm for planar domains with curved boundaries I.Theoretical foundations.Journal of Computational and Applied Mathematics，102：119-141。另有针对任意多边形的最大内圆查找方法是基于迭代法进行查找，但这种方法存在两个问题：一是部分情况下仅能迭代到局部的极大值而非最大值，另一点则是由于迭代而产生的效率不高的问题，相应的参考文献包括：郑梅生，陈宁，宋超.计算任意多边形最大内圆的一种算法.机械设计与制造，2003，5：84-85、蒋梅艳，文绘基于最优化理论的任意多边形最大内圆的求解方法，装备制造技术，2010，6：144-145等。 

采用计算构成湖泊多边形的Voronoi图则是另一种解决思路。Voronoi能够刻画多边形骨 架，可在多边形的Voronoi图的基础上查找该多边形的最大内圆。Voronoi图可通过数学方法进行计算，不再需要进行迭代，最大内圆圆心点一定是这些Voronoi图的某个交点，因此，可以通过计算相应多边形的Voronoi图求解多边形的最大内圆问题，相应的参考文献见Lee D T.1982.Medial Axis Transformation of a Planar Shape.IEEE Transactions on Pattem Analysis and Machine Intelligence，4(4)：363-369、Kirkpatrick D G1979.Efficient computation of continuous skeletons.Proc.20th Annu.Symp.Found.Computer Sci，18-27等。 

在针对任意多边形的最大内圆查找方面，特别是采用数学方法针对任意多边形的最大内圆的快速查找问题，目前可见专利/文献并不多，相应的少量文献也无法解决大批量的湖泊最大内圆的快速查找问题。 

发明内容

本发明的目的是提供一种基于Voronoi图实现湖泊中心点查找算法，特别是针对大批量的湖泊多边形来说，需要快速查找到所有多边形的最大内圆问题，本发明则主要是针对此问题进行解决。 

本发明的思路为：对于一个湖泊多边形的最大内圆求取问题，首先计算该多边形的Voronoi图，进而通过该多边形的Voronoi图的交点进行遍历求得。该方法通过分析几种简单多边形的Voronoi图生成算法，再对较复杂多边形进行二叉树方法递归，从而化简至该几种简单多边形的Voronoi图生成算法；进一步地，对于含有岛屿的湖泊来说，其对应的复杂多边形也同样含有岛，该算法首先计算复杂多边形多环的内部Voronoi图与内环的外部Voronoi图，再分析相应的Voronoi图的相交顺序情况完成复杂多边形的Voronoi图的构造过程，并通过遍历相应的Voronoi图的交点找到复杂多边形的最大内圆圆心点，并对算法的复杂度进行了分析，该算法为目前为止复杂复杂度最低的Voronoi图构造方法，亦可应用到其他类似的复杂多边形的最大内圆的查找应用中。 

本发明的技术方案提供了一种基于Voronoi图实现湖泊中心点查找算法，其特征在于包括以下的实施步骤： 

1)，计算五种基本线段的Voronoi图，包括：一条线段、一条线段和一个点、两条不相交线段、两条相交线段(相交角为锐角)、两条相交线段(相交角为钝角)五种情况； 

2)，判断湖泊多边形内部是否有岛，并分别按步骤3或步骤4进行处理； 

3)，对于无岛多边形来说，根据构成该多边形的边的个数，按照本发明的二分递归算法进行逐级分解，直到每个叶节点都为步骤1中所述情况之一，按本发明的Voronoi图合并规则进行合并，完成其Voronoi图的生成过程； 

4)，对于有岛多边形来说，需要分别计算其外环的内部Voronoi图与内环的外部Voronoi图，再按照算法合并规则合成生成复杂多边形的Voronoi图； 

5)，对相应构成Voronoi图的线段(抛物线)的交点进行遍历，找到距离湖泊多边形所有边最远的点，即为该湖泊的中心点。 

上述实施步骤的特征在于： 

步骤1)中需要首先分析几种简单Voronoi图的生成算法，以便后面步骤3按此生成算法进行二叉树的合并过程。 

步骤2)对待计算Voronoi图的多边形进行分类，并分别按步骤3或步骤4进行判断。 

步骤3)对无岛多边形的Voronoi图生成过程进行定义。 

步骤4)对有岛多边形的Voronoi图生成过程进行定义。 

步骤5)则是对已经生成Voronoi图的多边形的最大内圆查找方法进行定义。 

本发明与现有技术相比具有如下特点：采用二叉树递归的分裂-合并方法实现无岛多边形的Voronoi图生成过程的任务简化一结果合并的过程；对于含有岛的多边形的Voronoi生成过程来说，采用计算外环内部Voronoi图与内环外部Voronoi图的方法分别计算，并采用逐点判断法完Voronoi图的生成过程；对于最大内圆的查找过程，判断所有Voronoi图的交点距其他边的距离，选择其中最大距离的即为最大内圆半径，该点则对应着最大内圆圆心点。 

附图说明

图1是基于Voronoi图实现湖泊多边形最大内圆查找方法示意图 

图2是几种基本的Voronoi图的计算结果，其中： 

(a)为一条线段的Voronoi计算方法(b)为一个点A与一条线段的Voronoi计算方法(c)为两条线段的Voronoi计算方法(d)为两条线段的Voronoi计算方法(∠ABC为锐角)(e)为两条线段的Voronoi计算方法(∠ABC为钝角) 

图3是基于二叉树原理的简单多边形Voronoi图生成算法 

图4是复杂多边形Voronoi图的生成及最大内圆的计算方法 

图5是多边形最大内圆搜索伪代码示意图 

图6是基于Voronoi图的湖泊最大内圆圆心点估计效果图 

具体实施方式

图1示意了本发明的主要实现思路。对于一个任意多边形来说，首先通过分析任意多边形的Voronoi图的性质，得出该多边形的最大内圆圆心点一定在其Voronoi图的交点上，进而 可以通过计算该多边形的Voronoi图的交点再进行遍历求得。该方法通过分析几种简单多边形的Voronoi图生成算法，再对较复杂多边形进行二叉树方法递归，从而化简至该几种简单多边形的Voronoi图生成算法；进一步地，对于含有岛屿的湖泊来说，其对应的复杂多边形也同样含有岛，该算法首先计算复杂多边形多环的内部Voronoi图与内环的外部Voronoi图，再分析相应的Voronoi图的相交顺序情况完成复杂多边形的Voronoi图的构造过程，并通过遍历相应的Voronoi图的交点找到复杂多边形的最大内圆圆心点，并对算法的复杂度进行了分析，该算法为目前为止复杂复杂度最低的Voronoi图构造方法，亦可应用到其他类似的复杂多边形的最大内圆的查找应用中。 

1几种基本的Voronoi图生成算法 

图2示意了几种简单多边形的基本Voronoi图生成方法，这是后续Voronoi图生成的基础。图中，(a)为一条线段的Voronoi计算结果，分别为直线与他们与线段垂直，本文表示为及(b)为一个点A同一条线段的Voronoi计算结果，根据Voronoi的定义，该Voronoi图由射线及抛物线构成，其中分别为线段的中垂线，表示为抛物线的焦点为A，准线为本文表示为(c)为两个线段的Voronoi计算结果，分别是射线线段及两条抛物线其中为线段构成角的角平分线，表示为同样，另两段抛物线表示为(d)、(e)示意了矢量多边形中的两条边所构成锐角、钝角时的Voronoi生成情况，其中(d)是当∠ABC为锐角时，内部的Voronoi结果为该角的角平分线表示为外部的Voronoi结果为对应两线段的垂线(e)则是当∠ABC为钝角时的结果，与(d)的内部与外部情况相反。 

2简单多边形的Voronoi图生成算法 

对于简单多边形的Voronoi图生成算法来说，可以通过类似于二叉树的方法将其逐渐划分到几种基本的Voronoi生成算法，其原理如图3所示。对于一个具有n条边的简单多边形来说，其Voronoi计算过程可分为如下几个步骤：首先将该多边形按其边数平均分为2个部分，类似图3中的(a)、(b)部分，各部分分别计算相应的Voronoi，再通过(c)的合并过程实现最后 (d)的Voronoi计算结果；同样地，图2中的(a)、(b)部分还可以继续划分，直到每个小部分的仅剩余1条或2条边时为止，便可应用图2中的几种基本Voronoi生成结果并进行结果合并实现，整个过程类似于一个二叉树的“分叉一计算一合并”过程。 

当需要将图3中的(a)、(b)图进行合并时，将产生(c)，计算步骤为：首先从两个部分相交的点开始计算，即图中的点1或点5，这里我们从点5开始计算，判断点5两侧边的夹角(即∠456)，如果为锐角即计算该角的平分线(原理同图2(d))，如果是钝角则分别计算两条边的垂线(同图2(e))，本例中是计算∠456的平分线记录的两条边来源，本文中记录为 沿开始向下搜索，计算同点4与点6的Voronoi线的相交情况，并取先相交的点(本例中先同线相交于N点，后同线相交)。更新相应的Voronoi源(更新为)，再沿此点继续计算并记录新的Voronoi图来源，记录为类似于图2(c)的线段中的一段。按同样方法继续搜索，得出即点4同线段生成的抛物线。继续上面的过程，直到搜索到点1截止，分别得出搜索结束。 

3复杂多边形的Voronoi生成算法 

对于内部含有岛的复杂多边形的Voronoi图的生成算法问题，需要分别计算多边形的外环的内部Voronoi图及内环的外部Voronoi，再计算外环同内环之间的Voronoi图分界，如图4所示。图4(a)为一个简单多边形的Voronoi图，图4(b)为增加了一个岛的情况，其Voronoi图的计算过程是首先对岛计算其外部Voronoi图(结果为(b)中的射线)，同时需要对外环计算其内部Voronoi图，再分别计算外环与内环的Voronoi边界。 

首先选取内环上的某个点(如图4(b)的a点)，找出外环上距此点距离最近的线段(图中线段)，通过a点外部Voronoi与线段内部Voronoi计算中间Voronoi边界，可得到(b)中边界点g及抛物线(这里实际上结果为抛物线其中的段由于同线相交而没有表现出来)，表示为此时g点分别沿两个方向搜索，并在搜索遇到已有Voronoi线时更新搜索源，即首先在顺时针方向得到此时遇到更新搜索源为继续得到此时遇到更新搜索源为继续分别得到反过来看从g点开始的逆时针搜索，依次得出两边相交于点k，搜索结束。 

图4(c)为增加两个岛的示意图，图4(d)为增加三个岛的示意图。其中(b)的岛并没有对最终的最大内圆的位置产生影响，而(c)中又增加的岛致使最大内圆半径变小，(d)又增加了一个岛最大内圆的半径进一步变小，而且新增加的岛对原来已经存在的岛的Voronoi图的结果产生了改变。因此，在增加一个新的岛时，还需要考虑此岛同其他已存在岛的关系，如图4(d)所示，岛的增加使岛原有的Voronoi图的形状发生了改变，需要在算法搜索近距离边时予以考虑，区别在于还需要考虑该点同已有其他岛的最短距离，取二者中最短的边即可。 

4最大内圆圆心点查找算法 

根据Voronoi图的定义，图3(d)中的点N到线段与的距离均相等，因此以N点为圆心，以N到线段的距离为半径的圆将与线段及相切或相接。因此求任意多边形的最大内圆的问题也即转化为以该多边形Voronoi图的交点为圆心的最大内圆遍历的问题，其查找步骤的伪代码如图5所示。相应的伪代码的主要思路即遍历所有的Voronoi线的交点，找出它与所有边的最短距离，如果其大于已有距离，更新相应的最大半径变量maxRadius并记录该点point(j)，最后便可得出该多边形的最大内圆的圆心与半径。图4中的Voronoi线的交点代表需要遍历的Voronoi交点，相应的圆即为本文算法所得的最大内圆，O₁，O₂，O₃点为对应的圆心点。 

5应用实例分析 

应用本文上述算法对北美阿拉斯加地区遥感影像湖泊提取结果的矢量多边形进行了中心点的查找实验，效果如图6所示。进一步地，对整个有已经提取出来的197020个湖泊进行湖泊最大内圆圆心点估计，采用本发明的方法耗时264.77分钟，能够满足对此地区湖泊最大内圆圆心处的计算需求，同时在此基础上进行的影像配准效果也较好。 

本发明的实例在PC平台上实现，经实验证明，本发明能够得到较好为理想的最大内圆 查找结果，并且较常规方法有着较大程度的效率改进。本发明中所提及方法可广泛应用于基于湖泊中心点的多期影像匹配等应用。