Fast Three-dimensional Convex Hull Algorithm And Improvements

A fast new algorithm for three-dimensional convex hull construction is investigated in the paper. In the past few decades made convex hull algorithm for a series of advances, such as two-dimensional Graham scan algorithm, Javis volume package (wrapping) algorithm, etc. this algorithm were based on the sorting and average time complexity is O (nlogn). In the field of three-dimensional convex hull algorithm , there are the classic algorithm of Clarkson and Shor, and the Quick Hull algorithm. In essence, these algorithms are based on randomized incremental algorithm, adding the external point to the hull structure gradually, the advantage is easy to understand operations, and the time complexity is still the lower limit of hull structure O (nlogn). According to the large amount of statistical data show that for any point set of a sufficiently large, the vast majority is not the ultimate point of the convex hull of the vertices. Therefore, this paper based on the studying detailed the randomness of the two algorithms , further introduce non-random fact into the hull to accelerate the Quick Hull algorithm.The main content of this paper is focus on:1 ) A novel approach for three-dimensional convex hull was presented in the paper,this algorithm absorb the idea of QuickHull that selecting the extremal-point in each round, and improve the thinking. Comparing with the QuickHull method , the quadratic extremal-point was selected to construct the convex hull in the method, and this algorithm combined with"conflict graph"which is bipartite graph to update the topological relations between the points outside the convex hull and the current convex hull .The experimental results show that the algorithm is more efficient when compared with the QuickHull algorithm. 2)Using Visual C++ and OpenGL language as a tool to design a complete experimental platform, including STLViewer.exe and five dynamic link library. From the data generation, collection, processing, algorithm implementation, to the representation of final results , the platform is in full accordance with the standard CAD software design patterns. This character makes this platform has a certain practicality and maneuverability.3 ) Complete the processing of experimental data and comparison.Comparing with QuickHull , the efficiency has increased by 20% averagely.