以代数曲线为边界的二维形体的Voronoi图

The Voronoi Diagram of Two-Dimensional Shape with Algebraic Curve Boundary

摘要: Voronoi图是计算几何中的重要概念之一。在计算机图形学、计算几何、有限元网格划分、机器人轨迹控制、模式识别、气象学和地质学研究中得到广泛应用，现有的二维Voronoi图算法都是基于平面点集，多边形，或者以参数曲线为边界的二维形体的范围内解决的。由于代数曲线的难操作性，以代数曲线为边界的二维形体的Voronoi图算法一直未得到解决。本文在区间分析和细分算法的基础上，提出了以代数曲线为边界的二维形体的Voronoi图新算法。

Abstract: Voronoi diagram is one of the most important computational geometry concepts. It is applied widely in computer graphics, computation geometry, finite element grid partition, robot trajectory control, pattern recognition, meteorology and geology. Current 2D Voronoi diagram algorithms are constructed under the condition of point set, polygon or 2D shape with parametric curve boundary. Due to the manipulation dif-ficulty of algebra curve, Voronoi diagram of 2D shape with algebraic curve boundary has not yet got solved. Based on interval analysis and subdivision algorithm, a new algorithm to construct the Voronoi diagram of 2D shape with algebraic curve boundary is given in this paper.