A New Convex Hull Algorithm for Planar Sets 论文
1977ACM Transactions on Mathematical Software引用 288
Markov Chains and Monte Carlo MethodsMachine Learning and AlgorithmsComputational Geometry and Mesh Generation
摘要
A new algorithm, CONVEX, that determines which points of a planar set are vertices of the convex hull of the set is presented. It is shown that CONVEX operates in a fashion similar to the sorting algorithm QUICKERSORT. Evidence is given which indicates that in some situations CONVEX is preferable to earlier algorithms. A Fortran implementation, intended to minimize execution time, is presented and an alternative, which minimizes storage requirements, is discussed.