专利详情

专利名称	一种基于Voronoi图实现湖泊中心点查找算法
申请号	CN201310144336.0	专利类型	发明专利
公开（公告）号	CN103310470A	公开（授权）日	2013.09.18
申请（专利权）人	中国科学院遥感与数字地球研究所	发明（设计）人	沈占锋;盛永伟;骆剑承;胡晓东
主分类号	G06T7/60(2006.01)I	IPC主分类号	G06T7/60(2006.01)I
专利有效期	一种基于Voronoi图实现湖泊中心点查找算法至一种基于Voronoi图实现湖泊中心点查找算法	法律状态	实质审查的生效
说明书摘要	本发明提供一种基于Voronoi图实现湖泊中心点查找的算法。在研究湖泊变化过程中，需要找到最稳定的点作为控制点并进行多期湖泊的配准，而中心点的查找问题可转化为求该多边形最大内圆(内接或内切)的圆心问题。该方法首先分析几种简单多边形的Voronoi图生成算法，再对任意多边形进行二叉树递归，直到化简到几种简单多边形；对含有岛的复杂多边形，首先计算复杂多边形外环内部与内环外部的Voronoi图，再通过分析相应的线段相交次序实现复杂多边形Voronoi图的生成，最后通过遍历相应的交点找到多边形的最大内圆圆心点；通过算法复杂度分析，该算法为目前为止复杂度最低的方法，亦可应用到其他类似多边形最大内圆中。