search

augustt198 / Quickhull.jl

MIT License
18 stars 2 forks source link

readme

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.

Related Packages