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

摘要

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