Research On Convex Hull Algorithm And Its Application

The convex hull has a wide application in the area of pattern recognition, image processing and graphics. Many practical problems can be resorted to the convex hull problem. We research on the calculation of the convex hull and convex hull diameter, and advance the related algorithms. Meanwhile, we also discuss the application of convex hull on contour matching and high density point set collision detection. Theoretical analysis or experimental results have proved that the proposed methods are feasible and effective. This thesis develops itself mainly from the following six aspects.(1) Real time algorithm of convex hull.Due to the limitation that the tangent algorithm needs to be numbered to add in a real time point, it is of significance importance to advance an improved real time algorithm of convex hull. The point set is divided into several regions by extreme points. According to the regions of the real time point, we determined the influenced monotonous segments and recalculate the acme of them by tangent algorithm. The numbering for each newly added point as abscissa has been realized. Ultimately, we gain the convex hull by the updated monotone segments.(2) An algorithm for determining the convex hull of a given planar point set.The tangent algorithm is applied to the calculation of the convex hull of a given planar point set. We define monotone segments of the convex hull by the extreme points. And the point set is divided into several regions. For each point,if it is in the area formed by several monotone segments, then this point must not be the convex point, otherwise it is computed with the former monotone segments of the region in which it falls to update the monotone segment, and then the entire convex hull is obtained accordingly.(3) An algorithm for convex polygon diameter based on properties of convex polygon vertexs distance.Diameters problems in planar point sets can be transferred into the problem of determining the diameter of convex polygon. This thesis studies convex polygon diameter calculation, educes some properties about distance relation of convex polygon acmes, and advances an algorithm for calculating diameters of convex polygons based on properties of vertexs distance. Making use of these properties can reduce great deal of computation.(4) An algorithm for convex polygon diameter based on the monotony of distances between the point sequences of convex polygon and its edges.This thesis studies the properties of convex polygon according to the monotony of distances between the point sequences of convex polygon and its edges. According the monotony, we search the first antipodal pair by using the bisearch algorithm and find a quick approach to calculate the algorithm for convex polygon diameter.(5) The study on convex hull and its application in contour matching.Contour matching is an important topic in computer vision research. This thesis also studies contour matching under the translation-rotation-scale transformation, and comes to the conclusion that barycenter is an invariant under translation rotation and stretching. According to the invariant barycenter, calculate the translation, rotation and scale factor and realize contour matching.(6) The study on convex hull and its application in high density point set in collision detection. The virtual environment has become an important research domain of computer science, and collision detection between virtual objects is one of the key problems. This thesis is on the research of collision detection of two-dimensional objects. Convex hull is applied to high density point set of collision detection. We bring an algorithm for high density point set in collision detection based on encircling box of convex full. Firstly, calculate convex hull of the await collision detection point set, and then calculate intersection of the convex hulls, if they disjoint, then the two point sets don't collide; if they intersect, we search for the collision point set in the intersection set region between the two convex hulls.These algorithms obtain some results as follows:(1) By using real time algorithm of convex hull, the automatic numbering for each newly added point has been realized and only two monotonous segments need to be computed when a real time point is added in. So the algorithm improves the efficiency.(2) As for the calculation of the static convex hull, for each point,out of the area formed by several monotone segments, then it is only computed with the former monotone segment of the region in which it falls. So it reduces a lot of computation and improves algorithm's execution speed.(3) The usage of distance relation among vertex accelerate the computation speed, with a high memory efficiency of O(n).(4) We search the first antipodal pair using the bisearch algorithm. Its time complexity is O(logn). And the aided space of the whole algorithm is constant. It's better than others on both time and space complexity. So the algorithm is an efficient, reliable, and practicable method.(5) Both time and space complexity of the algorithm of contour matching are O(n), it achieves matching reliable, efficiency and practicality.(6) The algorithm of high density point set in collision detection is simple, applicable and reliable.