一种复杂多边形最大内圆的快速查找算法

A Fast Algorithm to Find the Largest Inner Circle of a Complex Polygon

任意多边形的最大内圆的快速查找在多个领域有着重要的应用。首先给出了任意多边形的Voronoi图的生成方法,以及基于Voronoi图实现该多边形的最大内圆的寻找算法,在此基础上分别采用中线简化及并行化处理对算法进行了效率方面的改进,并重点研究了矢量数据并行化过程中的数据分配策略,给出了其最优数据划分策略——算法复杂度均衡法。最后对北美阿拉斯加地区的多个湖泊进行了最大内圆的查找实验,相应的实验结果表明,改进的方法能够很大程度地提高最大内圆的查找效率。

It is necessary to find the largest inner circle of a complex polygon in many applications. The present paper develops a method for finding the largest inner circle of a polygon based on Voronoi diagram, and then improves the algorithm by medial axis simplification （MAS） and parallel computing. Data partition is a key issue in parallel computing of vector data. The algorithm complexity equalization strategy （ACES） is then presented. By several experimental tests of large quantity of lakes in Alaska we conclude that the approach developed in this paper performs effectively and efficiently by using MAS and ACES methods.