Study On Generating Algorithm For Divisional Weighted Voronoi Diagram

Voronoi diagram is an important branch of computational geometry.It has often been used to simulate base stations,substations,radar and other facilities.The grid algorithms can be divided into point by point scanning method and discrete constructing method.The point-by-point scanning method has high precision,but the complexity is high.The discrete constructing method is fast,but the precision is poor.The main work of this paper includes:Firstly,a point to point scanning method of divisional weighed Voronoi is proposed based on the scanning method of Voronoi.Secondly,we find that discrete constructing method has error and low efficiency.We improve the discrete constructing method by changing the expanding termination condition,and then we change angle increment,which greatly improves efficiency.Finally,we present a circular expansion scanning method by combining advantages of point-by-point scanning method and discrete constructing method.Based on the principle of discrete constructing method,generators firstly draw sector areas by weight.Then intersecting areas use Delaunay to determine the adjacent relationship of generators,and the remaining blank areas are colored by point-by-point scanning method.The algorithm ensures the correctness and has higher efficiency than point-by-point scanning method and discrete constructing method.