The Quickhull algorithm for convex hulls
The Quickhull algorithm for convex hulls
复制标题
DOI：
10.1145/235815.235821
复制
发表时间：
1996-12-01
影响因子：
2.7
通讯作者：
Huhdanpaa, H
中科院分区：
文献类型：
--
作者：
Barber, CB;Dobkin, DP;Huhdanpaa, H
点集的凸船体是包含这些点的最小凸集。本文将二维快速船体算法与一般维的Beneath-Beyond算法相结合，提出了一种实用的凸船体算法。它类似于凸船体和Delaunay三角剖分的随机增量算法。我们提供的经验证据表明，该算法运行速度更快，当输入包含非极值点，它使用更少的内存。计算几何算法传统上假设输入集是良好的。当使用浮点运算实现算法时，此假设可能导致严重错误。我们简要地描述了这个问题的解决方案时，计算凸船体在两个，三个或四个维度。输出是一组“厚”面，包含输入的所有可能的精确凸包。一个变量在五个或更多维度上有效。
The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quick-hull Algorithm with the general-dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and Delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it uses less memory. Computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating-point arithmetic, this assumption can lead to serious errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of ''thick'' facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.