Points in convex hull and assign True/False to the dataframe

Question

Here's my starting point, I have the following two point datasets

data1 = {'x': [580992.9581, 580992.9111, 580993.3539, 580993.4957, 580991.9780],
         'y': [4275268.7194, 4275267.6678, 4275267.2215, 4275268.1749, 4275267.6297]}

df1 = pd.DataFrame(data1)

data2 = {'x': [580992.7155, 580993.4258, 580992.7421, 580991.7034, 580992.7554, 580993.5837, 580993.0002, 580993.8348, 580991.2176, 580992.0536],
         'y': [4275267.2733, 4275267.7455, 4275266.7449, 4275268.8644, 4275266.4493, 4275267.5785, 4275268.5525, 4275268.9687, 4275267.6972, 4275267.7937]}

df2 = pd.DataFrame(data2)

I'm wanting to, in the most efficient way, calculate the Convex Hull of each of the dataframes, then determine which points are in the convex hull of the other dataframe.

So create the hull_of_df1 and the hull_of_df2.

To do this either Scipy's `ConvexHull(df1)' or in Shapely, let's use scipy.

from scipy.spatial import ConvexHull
hull_of_df1 = ConvexHull(df1)
hull_of_df2 = ConvexHull(df2)

Now, I need to assign True to any points from df1 that are in hull_of_df2.

The long way to do this would be something like:

for point in df1:
    if point.within(hull_of_df2):
        df1['in_hull'] = True
    else:
        df1['in_hull'] = False

And repeat for the other dataframe and other convex hull.

Ideally I just want to generate a new column and append it to the end of the df1 dataframe. So for those indexes which are within df1 assign in_hull == True. I do not want to delete any points in the dataframes, just record which points are and arn't in the opposite convex hull.

It's unclear to me what your current method is and whether it gives you the desired result. Can you post a working code snippet and the correct result? Then it's easier for us to think about more efficient solutions. — Bill, Feb 16 '22 at 22:23
This question seems related. Are any of the answers here relevant? [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) — Bill, Feb 16 '22 at 22:48
[This answer](https://stackoverflow.com/a/16898636/1609514) from above linked question works with your data: `df1['in_hull'] = in_hull(df1, df2)` gives `[True, True, False, True,True]`. I haven't checked to see how efficient it is on a larger set of points. — Bill, Feb 16 '22 at 22:59

score 1 · Accepted Answer · answered Feb 17 '22 at 18:57

You can use the hull equations do determine if the point is inside the hull

def in_hull(points, hull):
    A = hull.equations
    dist = np.array(points[['x', 'y']]) @ A[:,:2].T + A[:,2]
    return np.all(dist < 0, axis=1)

df1['within'] = in_hull(df1, hull_of_df2);
df2['within'] = in_hull(df2, hull_of_df1);

With some plotting to be more convincing

plt.plot(df1['x'], df1['y'], '.r')
for r in hull_of_df1.simplices:
    plt.plot(df1['x'][r], df1['y'][r], '-r')
plt.plot(df2['x'], df2['y'], '.g')
for r in hull_of_df2.simplices:
    plt.plot(df2['x'][r], df2['y'][r], '-g')

df1['within'] = in_hull(df1, hull_of_df2);
mr = df1['within']
plt.plot(df1['x'][mr], df1['y'][mr], 'xg')

df2['within'] = in_hull(df2, hull_of_df1);
mr = df2['within']
plt.plot(df2['x'][mr], df2['y'][mr], 'xr')

Points in convex hull and assign True/False to the dataframe

1 Answers1

Linked