Power Figure Scan Generation Algorithm

Voronoi Diagram is an important branch of the computational geometry . Power Diagram is one kind of important extension of Voronoi Diagram. It is one kind of weighted Voronoi Diagram that extend from Euclidean distance to Power distance, and has the very great practical value. This paper gives one kind of new algorithm generating Power Diagram—Scanning Production Algorithm on the base of Power Diagram theory. The algorithm subordinates to the discrete generating method. It makes use of the diffraction grating characteristic of the screen to calculate Power distance between each picture element and the generator on the screen. Comparing and sorting were done, Thus it draws Power boundary and constructs Power Diagram according to this characteristic of equal Power distance from point on Power boundary to some two generators .Compared with other algorithms, this algorithm has not only clear mentality and simple program design, but also does not need the complex contributory data structure, and also saved the massive pretreatment time and the storage time, and may extend to the higher order Power Diagram situation.As the application example, we use Power Diagram by this algorithm to analyze the region-covering questions of CNC to pass the selling area on some area in the Shijiazhuang, and have carried on the discussion about its distribution rationality.