Algorithm Research And Application Of Multi-core Voronoi Diagram In The Plane

With the continuous improvement of science and technology,computational geometry plays an increasingly important role,and has broad application prospects in the fields of computer graphics,machine vision,geographic information systems,vehicle navigation,industrial design,and integrated circuit design.As a very important branch of computational geometry,Voronoi diagram is also quite popular among scholars.This dissertation aims to analyze and expand some of the limitations of the traditional Voronoi diagram.On the one hand,the traditional point set Voronoi diagram is to divide the nearest field around each point of the plane.The number of Voronoi cells is equal to the number of point sets.When the number of point sets is too large,Voronoi divided cells will also increase,and the plane space will also be over-divided.At this time,the meaning of plane division will be much weaker.Moreover,when there are too many target objects,we need to consider the relationship between the target and the target,the relationship between the target group and the target group,instead of the traditional Voronoi diagram which only considers the single point-to-point distance relationship.If the Voronoi diagram is applied to the microbial space division and the surface fire space division,the existing methods are not very effective.For this,we need to solve the problem of generating the Voronoi diagram when the number of points is too large.On the other hand,polygonal Voronoi diagrams can be used in foreground detection,scene segmentation and other fields.The Voronoi diagram of the most primitive polygon is to divide the nearest area for the vertices and boundaries of each polygon on the plane.It treats each polygon as an independent individual,but when there is a many-to-one collective relationship between the target and the target,the original Voronoi diagram of the polygon is no longer applicable.In the actual situation,more complicated situations will arise.We often need to use multiple polygons to represent a certain type of group,so as to divide the space between groups and groups.Therefore,it is necessary to broaden the application range of the polygonal Voronoi diagram,so that it can be applied to the detection or segmentation problem when multiple polygons represent the same group.Aiming at the traditional Voronoi diagram only considering that each point is independent of each other and ignoring the connection between the point set and the point set,this dissertation proposes a Voronoi diagram based on DBSCAN clustering.Firstly,define and prove the cluster Voronoi diagram,and study its properties.Then DBSCAN clustering is performed on the point set,and the two parameters of DBSCAN clustering are generated by an adaptive algorithm.Secondly,divide the original point set into several subsets,and finally use each subset as the Voronoi core to make the Voronoi diagram.Aiming at the limitation of the traditional polygonal Voronoi diagram that only uses a single polygon as the core of Voronoi,this dissertation proposes a Voronoi diagram of a set of polygons.First study the definition and properties of the Voronoi diagram of traditional polygons,and then define and prove the Voronoi diagram of the polygon set.The Voronoi diagram covers the set of convex polygons,concave polygons,and the set of convex and concave polygons coexisting,and study its properties.Finally,the Voronoi diagram generation algorithm is proposed and applied to foreground detection and other fields,which proves the reliability of the algorithm.This dissertation conducts experiments on the above methods.The experimental results show that the method in this dissertation effectively solves the problem of generating Voronoi diagrams from large-scale point sets and the problem of multiple polygons representing the same target group,providing a theory for microbiology and computer vision applications basis.