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

Voronoi Diagram for Intersecting Convex Polygons in the Plane

作　　者：卢嘉豪 熊鹏文[1] 闵卫东 廖艳秋 Lu Jiahao;Xiong Pengwen;Min Weidong;Liao Yanqiu(School of Information Engineering,Nanchang University,Nanchang 330031;School of Software,Nanchang University,Nanchang 330047)

机构地区：[1]南昌大学信息工程学院,南昌330031 [2]南昌大学软件学院,南昌330047

出　　处：《计算机辅助设计与图形学学报》2019年第9期1609-1616,共8页Journal of Computer-Aided Design & Computer Graphics

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

摘　　要：传统的多边形的Voronoi图存在不能相交的问题,以至于无法将其应用于计算机视觉、生态学等领域中的多边形相交情况.为了解决多边形相交情况下的最邻近空间划分问题,提出了可相交凸多边形的Voronoi图.首先定义可相交凸多边形的Voronoi图;然后阐述相交多边形特有的Voronoi边的区域化现象,证明了其发生的充要条件,进一步揭示了相交多边形与不相交多边形之间的关系;最后提出Voronoi图的生成算法,并用代码实现.实验结果表明,该算法能够有效地解决多边形相交的问题,突破了不能相交的限制,为计算机视觉、生态学等领域的实际应用提供了理论基础.The traditional polygonal Voronoi diagram does not allow intersections among polygons and henceforth is hard to be applied to the fields of computer vision and ecology where polygons may intersect each other.In order to solve the problem of the nearest neighbor partitions under situations with polygon intersection,a novel Voronoi diagram for intersecting convex polygons is proposed.Firstly,the Voronoi diagram for intersecting convex polygons is defined.Then the unique regionalization feature of Voronoi edges is described,followed by the proof of the necessary and sufficient condition for its occurrence.Moreover,the relation between intersecting polygons and disjoint polygons is demonstrated.Finally,the generation algorithm of the polygonal Voronoi diagram is proposed and implemented.Experimental results show that the algorithm breaks through the constraint of having no intersecting polygons and effectively solves the problem of intersection in the polygonal Voronoi diagram,which provides the theoretic foundation for practical applications in the fields of computer vision and ecology.

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

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]