CODEWITHSUNDEEP
numpyconvex-hull
Am1rr3zA
Am1rr3zA

Reputation: 7441

How can I find if a point lies inside or outside of ConvexHull?

I have array of points in numpy and I compute their ConvexHull by (scipy.spatial.ConvexHull not scipy.spatial.Delaunay.convex_hull), now I wanna know if I add new point to my array is this point lies inside the convexhull of the point cloud or not? what is the best way to do it in numoy?

I should mention that I saw this question and it's not solving my problem (since it's using cipy.spatial.Delaunay.convex_hull for computing ConvexHull)

Upvotes: 4

Views: 3217

Answers (1)

Cunningham
Cunningham

Reputation: 188

I know this question is old, but in case some people find it as I did, here is the answer: I'm using scipy 1.1.0 and python 3.6

def isInHull(P,hull):
    '''
    Datermine if the list of points P lies inside the hull
    :return: list
    List of boolean where true means that the point is inside the convex hull
    '''
    A = hull.equations[:,0:-1]
    b = np.transpose(np.array([hull.equations[:,-1]]))
    isInHull = np.all((A @ np.transpose(P)) <= np.tile(-b,(1,len(P))),axis=0)

Here we use the equations of all the plan to determine if the point is outside the hull. We never build the Delaunay object. This function takes as insput P mxn an array of m points in n dimensions. The hull is constrcuted using 

hull = ConvexHull(X)

where X is the pxn array of p points that constitute the cloud of points on which the convex hull should be constructed.

Upvotes: 5

Related Questions