Algorithm Research And Application Of Voronoi Diagram For Polygons In The Plane

With the development of technology and the progress of society,computer-aided design and computer graphics have played an increasingly important role,and play a huge role in the fields of engineering product design,virtual reality,and movies.Voronoi diagrams have been favored by scholars as part of the research content in the field of computer-aided design and computer graphics.This thesis aims to analyze and study some problems existing in the traditional Voronoi diagram.One is that in computer vision,for video captured by a camera,if polygons are used to represent pedestrians,the polygons may intersect.In ecology,there may be multiple populations in the same area.At this time,polygons are used to represent the survival area of the population,and the polygons will intersect.For the intersection of such polygons,if the Voronoi diagram needs to be applied to this scene,the traditional Voronoi diagram cannot solve the problem.The second is that in the foreground detection,when a part of the moving target is similar to the background,the same target will be separated into two.At this time,multiple polygons need to be used to represent the same target.In ecology,the same population may be distributed in two places,in which case multiple polygons are needed to represent the same target.For this problem of using multiple polygons to represent the same target,if the Voronoi diagram needs to be applied to the scene,the traditional Voronoi diagram cannot solve the problem.Aiming at the intersection of polygons,this thesis proposes Voronoi diagram for intersecting convex polygons.First,the Voronoi diagram is defined,and its properties are studied on the basis of it.Under the condition of intersection,the strength and weakness of Voronoi edges are divided.The mechanism of Voronoi edge regionalization in a specific state is expounded,and the necessary and sufficient conditions for its occurrence are proved.In addition,the relationship between disjoint and intersecting polygons is studied,and the mutual transformation of the two is revealed.Finally,Voronoi diagram generation algorithms under the condition of polygon intersection are proposed.For the problem that multiple polygons represent the same target,this thesis proposes Voronoi diagram of a set of sets of polygons.Starting from the problem,the Voronoi diagram is derived.Then,the Voronoi diagram is simplified,and the simplified form of the Voronoi diagram of a set of sets of polygons is proposed.After the simplified form is studied,it is further generalized on this basis.The points are generalized to polygons,and back to the Voronoi diagram of a set of sets of polygons.The conclusion drawn from the simplified form can be further generalized to become the conclusion of the Voronoi diagram.The two Voronoi diagrams are defined,and then the combination of Voronoi units is studied,and the core theorem of the generation algorithm is proposed and proved.Finally,the theorem is used to derive two generating algorithms of Voronoi diagram.This thesis has conducted experiments on the above methods.The experimental results show that the method in this thesis effectively solves the problem of polygon intersection and multiple polygons representing the same target.The method breaks through the limitation of polygons that cannot intersect and the limitation of single polygons,and provides a theoretical basis for ecological and computer vision applications.