Getting points in convex hull

Question

I have two overlapping sets of points T and B.

I want to return all points from T that are within the convex hull of B I compute the convex hulls as follows

from scipy.spatial import Convexhull
import numpy as np
T=np.asarray(T)
B=np.asarray(B)

Thull = ConvexHull(T)
Bhull = ConvexHull(B)

How do I do the spatial query?

Possible duplicate of [What's an efficient way to find if a point lies in the convex hull of a point cloud?](https://stackoverflow.com/questions/16750618/whats-an-efficient-way-to-find-if-a-point-lies-in-the-convex-hull-of-a-point-cl) — user8408080, Nov 10 '18 at 02:13
nearly, but not quite, I don't want a true/false response. I want to add all points from T that are inside convexhull B to a new object. — Spatial Digger, Nov 10 '18 at 07:38

user8408080 · Answer 1 · 2018-11-19T16:37:56.573

Here is an example of what you want using the function defined in the other question I posted in the comments:

from scipy.spatial import Delaunay
import numpy as np
import matplotlib.pyplot as plt

def in_hull(p, hull):
    """
    Test if points in `p` are in `hull`

    `p` should be a `NxK` coordinates of `N` points in `K` dimensions
    `hull` is either a scipy.spatial.Delaunay object or the `MxK` array of the 
    coordinates of `M` points in `K`dimensions for which Delaunay triangulation
    will be computed
    """
    if not isinstance(hull,Delaunay):
        hull = Delaunay(hull)

    return hull.find_simplex(p)>=0

T = np.random.rand(30,2)
B = T + np.array([[0.4, 0] for i in range(30)])

plt.plot(T[:,0], T[:,1], 'o')
plt.plot(B[:,0], B[:,1], 'o')


new_points = T[in_hull(T,B)]

plt.plot(new_points[:,0], new_points[:,1], 'x', markersize=8)

This finds all points of T in the hull of B and saves them in new_points. I also plot it, so you see the result

Getting points in convex hull

1 Answers1