Checking If A Point Is In Convexhull?

I am having trouble understanding how to compute whether an n-dimensional point is within an n-dimensional ConvexHull. A very similar question (the same) was asked here: What's an

Solution 1:

It seems to be an edge case problem with the find_simplex method of the Delaunay object for almost flat simplex (triangle).

Here is a code to find and plot a faulty case with only 3 points:

import matplotlib.pylab as plt
from scipy.spatial import Delaunay
from scipy.spatial import delaunay_plot_2d

for _ inrange(5000):
    cloud = np.random.rand(3, 2)

    tri = Delaunay(cloud)

    if np.any( tri.find_simplex(cloud)<0 ):
        print('break at', _)

        delaunay_plot_2d(tri);
        id_break = np.where(tri.find_simplex(cloud)<0)
        plt.plot( *cloud[id_break].ravel(), 'or' );
        break

The other method proposed here seems to work well:

hull = ConvexHull(cloud)

def point_in_hull(point, hull, tolerance=1e-12):
    return all(
        (np.dot(eq[:-1], point) + eq[-1] <= tolerance)
        for eq in hull.equations)

[ point_in_hull(point, hull) for point in cloud ]
# [True, True, True]