A handcrafted collection of 3D convex hull implementations, slides and papers with some theory and explanations.
C/C++
- C++ implementation of the 3D QuickHull algorithm. Header-only, public-domain C++11 library. Uses the QuickHull approach with average-case O(n log n) complexity and worst-case O(n²). Suitable for inclusion in performance-critical projects.
- CGAL library 3D convex hull based on quickhull. Highly robust and exact implementation based on the underlying triangulation framework. Time complexity O(n log n) in 3D. Requires CGAL installation; static linking yields significantly better performance than dynamic (e.g., 1.63s vs 9.50s for 1M points).
- CDT included in CoACD ex V-HACD. A comprehesive set of packages (beyond convex hull) in C++ with Python wrappers supporting multiple mesh formats.
- S-hull: a fast sweep-hull routine for Delaunay triangulation in C++. Although primarily designed for Delaunay triangulation, it can be adapted for convex hulls. Claims O(n log n) average performance. Requires building the library from source.
- Qhull. Mature, widely used library for convex hulls, Delaunay triangulations, Voronoi diagrams, etc. Based on the QuickHull algorithm. Average-case O(n log n); worst-case O(n²). Performance is “balanced” in practice—typical inputs behave close to average case. Read more: http://www.qhull.org/html/qh-code.htm#performance.
- 3D Convex Hull in C. Header-only C implementation of the 3D QuickHull algorithm. Compatible with C++ compilers and MSVC. Inherits the standard QuickHull complexity: average O(n log n), worst-case O(n²).
- GEOS. C/C++ library for computational geometry which has some function to compute convex hull over Geometry objects.
- Fast-Quick-hull Described as a “fast C++ multi-threaded algorithm for computing convex hulls” using QuickHull. May be useful for large-scale point clouds.
Python
- SciPy - quickhull Built on top of Qhull. Supports 2D–N-D convex hulls. Time complexity inherits Qhull’s O(n log n) average case.
- Pyhull Pure Python wrapper around Qhull for convex hull, Delaunay, and Voronoi computations.
- Quickhull for Convex hull in Python Pure python - for education only.
JAVA
- QuickHull3D: A Robust 3D Convex Hull Algorithm in Java. Implements the 3D QuickHull algorithm. Average-case time complexity O(n log n); worst-case O(n²). Works with double-precision coordinates and handles degenerate cases robustly.
- Maven: A Robust 3D Convex Hull Algorithm In Java Packaged version of QuickHull3D available via Maven Central. Based on the original Barber–Dobkin–Huhdanpaa paper and Qhull’s design. More: https://mvnrepository.com/artifact/com.github.quickhull3d/quickhull3d/1.0.0
- [QuickHull-3D] (https://github.com/diwi/QuickHull-3D) Processing/PeasyCam dependencies for visualization. Educational or interactive 3D graphics projects. Hasn't been updated for years.
- Covex hull algorithms in 3D. Complexity analysis, details and pseudocode for gift wrapping, divide and conquer, incremental algorithm
- 3D convex hulls. Basics, complexity, naive, explanation of gift wrapping, divide and conquer, incremental approaches
- Convex Hulls in 2d and 3d. Visual explanation, complexity analysis and pseudocode for gift wrapping, Graham scan, incremental, divide and conquer, Chan’s algoritms for 2D case and same for gift wrapping and divide and conquer for 3D case.
- Convex hull in 3 dimensions. Complexity analysis in 2D and 3D, details on Graham scan, gift wrapping, divide and conquer, quick hull, Chan's, online algoritms: Preparata's and Overmars & van Leeuven in 2D. Gift wrapping, divide and conquer, incremental and conflict graph in 3D.
- A Minimalist’s Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm. Good for educational purposes
- 3D fast convex-hull-based evolutionary multiobjective optimization algorithm. Incremental convex hull with average time complexity reduced to O(n log(n)).