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

作者：卢嘉豪; 熊鹏文; 闵卫东^*; 廖艳秋

来源：计算机辅助设计与图形学学报, 2019, 31(09): 1609-1616.

• 相交多边形
• Voronoi图
• Voronoi边区域化
• 矢量生成算法

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

• 单位
  南昌大学信息工程学院; 南昌大学软件学院