Research On Two-dimensional Convex Hull Algorithm In Street Containment System

As one of the basic units of computational geometry,convex hulls are widely used in various fields,especially in the field of street crime containment.Each point on the convex hull is equivalent to every intersection in the street,so you can set the containment ring according to the apex on the convex hull.In the street crime containment,the formation of convex hull on the encirclement set is timely,plays an important role.So how to quickly generate convex hulls become a key problem in the field of street crashes.Today's convex hull generation algorithm has a large problem in dealing with the point set in the plane,and the solution to this problem is still being perfected.There are still some computational errors,such as the shelving of special vertices,in the present convex hull generation method.This paper focuses on the rapid generation of two-dimensional convex hulls.The research contents are as follows:(1)Firstly,the research on the theoretical knowledge used in the process of the convex hull and the related technical points used in the system application is studied.(2)Aiming at the problem of the formation of convex hull in the street containment system,the traditional convex hull generation scheme is studied,and the problems in the traditional convex hull algorithm are analyzed.(3)In this paper,an improved scheme based on Graham algorithm is proposed in the Graham convex hull generation algorithm for the existence of errors in the process of calculating the polar angle in the process of large processing and vertex sorting.The improved algorithm is used to deal with the plane point set from the pretreatment and the acquisition phase.In the pretreatment stage,the vertex of the convex hull is removed and the size of the convex hull is reduced.In the seeking stage,the error is avoided and the special The collinearity of the set of points.(4)The experimental results are obtained by experimentally validating the improved algorithm and the traditional algorithm,and the results are analyzed.The improved convex hull generation algorithm is explained.The size of the reduced set is reduced and the error of the size is avoided,To solve the collinearpoint set and other aspects of the treatment is correct and effective.Finally,the optimized convex hull generation algorithm is applied to the street containment system,and the convex hull is formed quickly,which improves the rate of encirclement generation.For the future in the street crime in the encirclement generation problem provides a new fast and efficient solution.