The Crystal Growth Of Voronoi Diagrams With Obstacles

A novel algorithm called crystal growth is presented to construct Voronoi diagrams with obstacles. In its fundamental idea, generators of Voronoi diagrams are regarded as vegetated points, then the crystal growth begins from them with 4-point template and 8-point template. Once the growth meets with obstacles, the borders of the obstacles will also be regarded as vegetated points and continue the growth. Finally, the boundaries of the different crystal regions construct the Voronoi diagrams with obstacles. With this method we can obtain three kinds of Voronoi diagrams with three different distances, that is, the City Zone Distance, the Chessboard Distance and the Euclid Distance. The method is used for the construction of Voronoi diagrams with 2-dimension obstacles of any plane area. It has simple data structure and has been realized in Visual C++ on computer. In the end, a practical model is given to plot out the area of some place to solve the problem of the children's entrance to the nearest schools.