Quickhull

释义 Definition

Quickhull 是一种用于计算点集凸包（convex hull）的算法，常用于二维或三维计算几何中。它的思想类似 Quicksort（快速排序）：通过选择边界点将点集分割为子问题，递归地“找最外层”的点来构建凸包。（也常写作 QuickHull。）

发音 Pronunciation (IPA)

/ˈkwɪkˌhʌl/

例句 Examples

Quickhull can compute the convex hull of these points quickly.
Quickhull 可以快速计算这些点的凸包。

In computational geometry, Quickhull is often used to build a 3D convex hull by recursively partitioning points and discarding those inside the current hull.
在计算几何中，Quickhull 常用于构建三维凸包：通过递归划分点集，并丢弃位于当前凸包内部的点来完成计算。

词源 Etymology

Quickhull 这个名称由 **Quick-**（“快速的”，借用 quicksort 的思路与命名方式）与 hull（“外壳、包围层”，在几何中指“凸包/包络”）组合而来，强调它用“快速分治”的方式求出点集的最外层边界。

相关词 Related Words

• Convex Hull
• Quicksort
• Divide-and-Conquer
• Computational Geometry
• Delaunay
• Voronoi
• Graham Scan
• Gift Wrapping

文学与著作出现 Notable Works

• Barber, Dobkin & Huhdanpaa (1996), “The Quickhull algorithm for convex hulls”（介绍并推广 Quickhull，影响了许多工程实现）
• Mark de Berg et al., Computational Geometry: Algorithms and Applications（计算几何经典教材，讨论凸包等基础问题，常在相关章节提及 Quickhull 及对比方法）
• Joseph O’Rourke, Computational Geometry in C（凸包算法常见参考书之一，在凸包主题中与其他方法并列出现/被讨论）