Research Of Voronoi Diagram With Barries

The Voronoi diagram is a fundamental data structure about space partitioning. Voronoi diagram is an important branch of computational geometry and its application has attracted more and more attentions. It has been employed in a variety of geometry-related fields since 1900s. With the popularity and development of computing technology, the area of its applications is still being widened each year.Generally, Voronoi diagrams are separations of plane, based on Euclid distance (L2 Metrics). In the real world, there is little probability to cross straightly between two objects. Usually, it is necessary to detour some barriers.In order to expand the applications of voronoi diagrams, this paper discusser voronoi diagrams, and presents definitions and properties of Voronoi diagrams with barriers.Voronoi diagrams for general figures are difficult to construct because of their uncertain shapes. In this paper, a constructing method based on discreted boundary, i.e. select based points on boundaries of every generaors first, then use constructing method of voronoi diagram with limited barriers based on points as generators. We get voronoi diagram with limited barriers whose generators are arbitrary planar figures. Traditional algorithms need discuss the irregular figures of the boundaries and uncertain Voronoi regions, and can not avoid computing a lot of data and considering error. This algorithm does not consider the geometric figures of generators and computing is not complex.Our method can get over all kinds of shortcoming that we have just mentioned. So it is more useful and effective than traditional algorithms. The results show that this algorithm is both simple and useful and it is of high potential value in practice.