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

Voronoi Diagram for Intersecting Convex Polygons in the Plane

传统的多边形的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.