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

摘要

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

主权项

一种基于Voronoi图实现湖泊中心点查找算法，其特征在于包括以下几个步骤：步骤1，计算五种基本线段的Voronoi图，包括：一条线段、一条线段和一个点、两条不相交线段、两条相交线段(相交角为锐角)、两条相交线段(相交角为钝角)五种情况；步骤2，判断湖泊多边形内部是否有岛，并分别按步骤3或步骤4进行处理；步骤3，对于无岛多边形来说，根据构成该多边形的边的个数，按照本发明的二分递归算法进行逐级分解，直到每个叶节点都为步骤1中所述情况之一，按本发明的Voronoi图合并规则进行合并，完成其Voronoi图的生成过程；步骤4，对于有岛多边形来说，需要分别计算其外环的内部Voronoi图与内环的外部Voronoi图，再按照算法合并规则合成生成复杂多边形的Voronoi图；步骤5，对相应构成Voronoi图的线段(抛物线)的交点进行遍历，找到距离湖泊多边形所有边最远的点，即为该湖泊的中心点。