Subdivision Algorithm For Voronoi Diagram

Voronoi diagram is an important computational geometry concept. It is applied widely in geology, robot trajectory control, meteorology and other fields. So it is very important to construct Voronoi diagram. Voronoi diagram generation methods consist of vector and grid algorithms. Vector algorithms usually have high accuracy, but in multidimensional space case, the surfaces or more complex geometric objects will be decomposed into points and lines, so the integrity of the growth elements will be destroyed, and the data storage structure is very complex. Grid algorithms have no limit on growth elements and space type. However, the quality of Voronoi diagrams generated are low and need more time.In chapterl, the research background is given. Then, in chaper2, some theories of Voronoi diagram are introduced. Based on quadtree data structure and interval arithmetic technique, a new subdivision algorithm for Voronoi diagram of a planar point set is proposed in chapter3. A comparison of this subdivision algorithm with the incremental algorithm and grid expansion method is conducted. Test results show that the subdivision algorithm is more efficient. Meanwhile, the time complexity of the subdivision algorithm is estimated theoretically. A new subdivision algorithm for Voronoi diagram of planar polygon is given in chapter4. We then improved the algorithm, test results show that the improved algorithm is much better in both accuracy and efficiency. In recent years, with the development of computing ability, algebraic curves and algebraic surfaces are widely used in geometrical modeling and graphics, to meet this demand, a new subdivision algorithm for constructing the Voronoi diagram of2D shape with algebraic curve boundary is given in chapter5, some test examples are given to show the effectiveness of the algorithm. Finally, in chapter6, we make a conclusion and point out the direction of the future research.