Research On Generation Algorithm Of Mixed Partitioned Weighted Voronoi Graph

As a very important research direction in computer geometry,the Voronoi diagram plays an important role in many application fields and is a basic research work.The partitioned weighted Voronoi diagram is the most complex and representative Voronoi diagram.Because the partitioned weighted Voronoi diagram is a new type of graph,its generation algorithm is the focus and difficulty of the research.The classical partition-weighted Voronoi diagram generation algorithm includes three methods: point-by-point scanning,discrete construction method and circle expansion scanning.This paper analyzes and compares these three methods and finds that these three algorithms have some defects.Point-by-point scanning method has the advantages of accurate generation results,but the disadvantage is that the calculation volume is large;the advantage of the discrete construction method is that it can dynamically simulate the generation process,but it cannot generate a continuous multi-block partitioned weighted Voronoi region;the circle expansion scan method will be scanned point by point The combination of the method and the discrete construction method improves the speed and accuracy of the algorithm,but the efficiency of the algorithm depends on the construction speed of the Delaunay triangulation and there is a certain degree of instability.At the same time,the method of using point-by-point scanning to determine the point-of-occurrence in the overlapping region is correct,but there is some redundancy,which affects the efficiency of the algorithm.In order to solve the above problems,this paper carries out a series of research work and proposes a hybrid partitioned weighted Voronoi diagram generation algorithm.The core steps of the algorithm are the following two aspects: First,at the stage of generating meta-sector preprocessing,a sector-based padding algorithm is designed to replace the step of constructing the Delaunay triangulation in the circle expansion scan method,thereby improving The filling rate of the one-step expansion region of the generated meta-sector is obtained.Secondly,it is found through experiments that for the grid in the overlap region,there is actually no need to use a point-by-point scanning method to determine which of the generated meta-sectors it belongs to.It is only necessary to compare between the generated meta-sectors that have covered the raster.Through this discovery,the computational complexity of point-by-point scanning is greatly reduced.At the end of this paper,the correctness of the algorithm is verified by a large number of experiments.Compared with the existing partitioned weighted Voronoi diagram generation algorithm,the efficiency is greatly improved.