改进的限定Voronoi图梯形检测带细分算法

Improved Subdivision Algorithm of Trapezium Examining Strip for Constraint Voronoi Diagram Generation

针对已有的限定Voronoi图生成算法在一些复杂约束条件下不能收敛的问题,通过引入控制因子,给出一种改进的限定Voronoi图梯形检测带细分算法。在计算初始Voronoi生长元的过程中,引入外部和内部限定线段端点保护圆半径控制因子,控制限定线段两端点附近的Voronoi边的尺寸;在细分梯形检测带的过程中,引入外部和内部限定线段尺寸控制因子,控制位于限定线段上的Voronoi边的尺寸。实验结果表明,本算法对于内部边界约束、线束约束条件以及不规则区域均可以得到质量较好、满足约束条件的限定Voronoi图。

Aiming at the problem that existing constraint Voronoi diagram generation algorithm may not converge when the constraints are complex, this paper proposed an improved subdivision algorithm of trapezium examining strip for constraint Voronoi diagram by introducing several control factors. External and internal constraint line endpoint protec- tion radius control factors are used to control the size of the constraint line near the end points of the Voronoi edge dur- ing calculating the initial Voronoi growth process. External and internal constraint segment size control factors are used to control in the size of the constraint line on the Voronoi edge during the process of subdivision examining strip. Experi- mental results show the proposed algorithm can get satisfied results even in the complex domain including internal boundary constraints, pencil of lines constraints and irregular areas.