平面上可相交凸多边形的Voronoi图

摘要：

传统的多边形的Voronoi图存在不能相交的问题,以至于无法将其应用于计算机视觉、生态学等领域中的多边形相交情况.为了解决多边形相交情况下的最邻近空间划分问题,提出了可相交凸多边形的Voronoi图.首先定义可相交凸多边形的Voronoi图;然后阐述相交多边形特有的Voronoi边的区域化现象,证明了其发生的充要条件,进一步揭示了相交多边形与不相交多边形之间的关系;最后提出Voronoi图的生成算法,并用代码实现.实验结果表明,该算法能够有效地解决多边形相交的问题,突破了不能相交的限制,为计算机视觉、生态学等领域的实际应用提供了理论基础.

关键词：相交多边形、Voronoi图、Voronoi边区域化、矢量生成算法

所属期刊栏目：31

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金61762061,61663027;江西省自然科学基金20161ACB20004,20181BAB211019

在线出版日期：2019-11-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1609-1616