Quickhull.jl

The quickhull algorithm in pure Julia for finding convex hulls, Delaunay triangulations, and Voronoi diagrams in N dimensions.

julia> using Quickhull

julia> hull = quickhull(randn(3, 500))
Hull of 500 points in 3 dimensions
  - 31 Hull vertices: Int32[297, 438  …  147, 376]
  - 58 Hull facets: TriangleFace{Int32}[TriangleFace(139, 249, 243)  …  TriangleFace(104, 147, 243)]

julia> using GLMakie, GeometryBasics
julia> wireframe(GeometryBasics.Mesh(hull))
julia> scatter!(points(hull), color=:black)

julia> tri = delaunay(rand(2, 100));
julia> f = Figure()
julia> wireframe!(Axis(f[1,1]), GeometryBasics.Mesh(tri))
julia> linesegments!(Axis(f[1,2]), voronoi_edge_points(tri), color=:red)

Qhull Comparison

Quickhull.jl is competitive with Qhull's performance even when exact arithmetic is used, although it has fewer features.

Robustness

quickhull can be run with various hyperplane kernels. A hyperplane kernel is a method of calculating hyperplane-point distances. By default, an exact kernel is used (i.e. the sign of the distance is always correct) to ensure robustness. Robustness can be traded for speed by choosing an inexact kernel, for instance:

quickhull(pts, Quickhull.Options(kernel = Quickhull.HyperplaneKernelInexact))

It should be noted that if an inexact kernel is used – particularly on inputs with coplanar or nearly coplanar points – the topology of the hull can become corrupted, and an error will probably occur.

Parallelism

quickhull can be run with multithreading by setting the subdivide option to Quickhull.ParallelSubdivide(), or using the shorthand quickhull_parallel. In some cases this can achieve a speedup almost linear in the number of threads.

julia> Threads.nthreads()
8

julia> pts = rand(3, 2_000_000);

julia> @btime quickhull($pts);
  141.327 ms (2331 allocations: 25.96 MiB)

julia> @btime quickhull_parallel($pts);
  23.656 ms (14629 allocations: 29.39 MiB)

Related Packages

• QHull.jl, DirectQHull.jl – wrappers for Qhull
• DelaunayTriangulation.jl – 2D Delaunay triangulation and Voronoi tesselation with many features
• TetGen.jl – wrapper for 3D Delaunay tetrahedralization library TetGen