Point test convex hull

[Robert Gates]

Dear Julia Users,

does anyone know of a package capable of computing whether a point lies inside or outside of a (3D) convex hull?

I know that the solution to this problem is rather trivial, however, before I reinvent the wheel, I figured some code might already be out there. I checked the Julia interface to qhull (CHull.jl) but was unable to find a quick fix in the qhull manual. I know that the GeometricalPredicates package provides this functionality for triangles and tetrahedra, however, I was looking for something more general.

Best regards,

Robert

[Miles Lubin]

There are certainly more efficient specialized solutions for low dimensions like 3D, but you can test whether a point is contained in the convex hull by solving a linear programming feasibility problem:

x = [1,1,1] # test point
Z = [1 0  # points along columns
     0 1
     0 0]
using JuMP
m = Model()
@defVar(m, 0 <= lambda[j=1:size(Z,2)] <= 1)

@addConstraint(m, inhull[i=1:length(x)], x[i] == sum{Z[i,j]*lambda[j], j = 1:size(Z,2)})
@addConstraint(m, sum(lambda) == 1)
status = solve(m)
# Infeasible means not in the hull, Optimal means in the hull