Abstract: Aiming at the problem that existing constraint Voronoi diagram generation algorithm may not converge when the constraints arc 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- lion 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 ex<}rnining 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.

Key words: Constraint Voronoi diagram, hrapezium examining strip, Refinement algorithm, Control factor, Computational geometry algorithms library