Research On Voronoi Graph With Obstacls

Voronoi graph is a basic data structure in space partition. As one of the important branches of computational geometry, more and more attention is paid on its applications. In recent years, it is applied in many fields related to geometric information. With the spreading and development of computer technique, the application fields of Voronoi graph are inceasingly expanded.Traditional Voronoi graph is an ideal model for space partition under the condition that no obstacles exist. However there are many man-made and natural obstacles in real life so that there is no direct path to take between two targets, which make the traditional Voronoi graph invalid. In order to expand the applications of Voronoi graph further, the Voronoi graph with obstacles need to be studied, which gives the research contents of this paper.Beginning with the definition of general Voronoi graph, its properties and classic generation algorithms are systematically summed up. The adding point construction algorithm of Voronoi graph is presented on the basis of further research on generation algorithms of Voronoi graph. The algorithm is the improvement and perfection for the increasing quantity algorithm of constructing Voronoi graph, meanwhile the flow diagram of the algorithm is given. The new algorithm has simple logical process and the treatment for special positions of new added points in constructing Voronoi graph is avoided.Based on the dual relation between Voronoi graph and Delaunay triangulation of scattered point set, Voronoi graph-based triangulation algorithm is proposed, which sculptures the classic algorithms of constructing Delaunay triangulation deeply. The point-by-point insertion algorithm of constructing Delaunay triangulation is improved, in which the efficiency of the whole algorithm is enhanced by optimizing kernel algorithm. The kernel algorithm is the determination algorithm of the position relation between a point and a simple polygon, in which the problem is analysed through introducing a ray to reduce the complexity of the whole algorithm by taking limit idea, and the importance is that the ray is not needed to be stored when the algorithm is implemented in code.Then the Voronoi graph is studied when obstacles are segments. Some nice properties for segment obstacle Voronoi graph are given. Generation algorithms for segment obstacle Voronoi graph are discussed, some of which can be generalized to the situation that obstacles are arbitrary geometrical shapes. And more, a semi-plane intersection algorithm for constructing Voronoi graph with obstacles is proposed, which is unique construction algorithm of Voronoi graph with obstacles now. Finally, some application examples for Voronoi graph are presented.