4

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)

Community
  • 1
  • 1
Am1rr3zA
  • 7,115
  • 18
  • 83
  • 125
  • possible duplicate of [What's an efficient way to find if a point lies in the convex hull of a point cloud?](http://stackoverflow.com/questions/16750618/whats-an-efficient-way-to-find-if-a-point-lies-in-the-convex-hull-of-a-point-cl) – kkuilla Feb 11 '14 at 10:10
  • @kkuilla if read my question carefully you will see that I put the link of that question, and mention that this question was not solving my problem. – Am1rr3zA Feb 11 '14 at 10:39
  • Yes, I noticed that after I flagged it. You are actually saying that "it's solving my problem". I think it could be a duplicate because that question solved your problem. – kkuilla Feb 11 '14 at 10:43
  • It looks like a decent number of the answers on that other question address your question (ex http://stackoverflow.com/a/16751168/380231 which uses `scipy.spatial.ConvexHull`) and are independent of how you found your convex hull. – tacaswell Feb 13 '14 at 02:20
  • @tcaswell read the comment below the specific answer you will find the error I have read that answer so many times before – Am1rr3zA Feb 13 '14 at 07:20
  • A quick look shows that scipy.spatial.ConvexHull uses QHULL to solve, which is more suited towards higher dimensional convex hulls. If you a higher dimensional convex hull, then you probably should have said so. Otherwise, you probably shouldn't be using that algorithm. Determining if a point is inside of an N-Dimensional convex hull seems like it might be tricky. That being said, I'm thinking ray tracing (the method suggested) still works, as you just need to test every facet, and in 2D, an edge is a facet if I recall right. – Nuclearman Feb 18 '14 at 09:42

1 Answers1

5

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.

Cunningham
  • 178
  • 2
  • 10
  • It works under most cases. I found however if I select a point which is used as a vertex for the convex hull it returns false. Any idea why? – Watchdog101 Jul 19 '19 at 01:52
  • This is giving ValueError: operands could not be broadcast together with shapes (7,) (7,2) – saibhaskar Oct 23 '20 at 02:13
  • 2
    @saibhaskar I know it's old, but to clarify: P is expecting a list of points. If you only have one point, then just wrap the single point [x, y] in brackets again so [[x, y]] – Brian Jan 26 '22 at 17:34