# Filtering points appearing in list of convex hull polygons

I have two DataFrames `df` & `df1`:

`df`: containing latitude, longitude, and binary cluster (0 or 1)

``````latitude    Longitude    cluster
30.400091   -100.722830   0
30.500091   -100.762830   0
30.600091   -100.792830   1
...
``````

`df1`:

``````latitude    Longitude
31.400091   -100.722830
32.501091   -101.862830
32.600091   -100.792830
...
``````

For `df`, I applied a convex hull in order to obtain two polygons (the two polygons are separated no crossing zone between them) for each cluster 0 and 1 with the following code:

``````z=[] #HULL simplices coordinates will be appended here

for i in range (0,num_clusters):
dfq=df[df['cluster']==i]
Y = np.array(dfq[['Latitude', 'Longitude']])
hull = ConvexHull(Y)
plt.plot(Y[:, 1],Y[:, 0],  'o')
z.append(Y[hull.vertices,:].tolist())
``````

I would like to know if is possible to filter/conserve `df1` points that strictly appear in one of the `df` polygons. This solution is quite similar but does not work for a list of polygons like in my case.

Here is a possible solution using shapely.

It generates a shapely Polygon for each cluster hull. Then, it checks each point in a given dataframe (df1) is within at least one of the hulls. Plots shows the cluster points (red/blue/orange/cyan), the cluster hulls (dashed lines, same colors), the datapoints to test in black (out of cluster hull) and green (inside cluster hull).

Modules versions:

``````Python 3.9.13 (tags/v3.9.13:6de2ca5, May 17 2022, 16:36:42) [MSC v.1929 64 bit (AMD64)]

pandas 1.4.1
shapely 1.7.1
numpy 1.22.3
matplotlib 3.5.1
scipy 1.8.1
``````

Matplotlib:

``````import sys
from typing import List

import matplotlib
import numpy as np
import pandas as pd
import scipy
import shapely
from matplotlib import pyplot as plt
from scipy.spatial import ConvexHull
from shapely.geometry import Point, Polygon

print("Python", sys.version)
for m in [pd, shapely, np, matplotlib, scipy]:
print(m.__name__, m.__version__)

def generate_random(n: int,
low_lat: int, high_lat: int,
low_lon: int, high_lon: int,
cluster_id: int):
cols = ["latitude", "longitude"]
if cluster_id:
cols.append("cluster")
df = pd.DataFrame(columns=cols)
df.latitude = np.random.uniform(low=low_lat, high=high_lat, size=(n,))
df.longitude = np.random.uniform(low=low_lon, high=high_lon, size=(n,))
if cluster_id:
df.cluster = cluster_id
return df

def coords_to_shapely_point(x: np.ndarray, y: np.ndarray) -> List[Point]:
return list(map(Point, x.tolist(), y.tolist()))

def generate_random_inputs():
nb_clusters_to_generate = 4
df_clusterrs = []
for i in range(nb_clusters_to_generate):
lat_offset = int(np.random.choice(a=[-25, -20, -15, 15, 20, 25], size=(1,)))
lon_offset = int(np.random.choice(a=[-25, -20, -15, 15, 20, 25], size=(1,)))
df_clutser_i = generate_random(n=100, cluster_id=i + 1,  # stort from 1, 0 = no cluster
low_lat=30 + lat_offset, high_lat=50 + lat_offset,
low_lon=-100 + lon_offset, high_lon=-50 + lon_offset)
df_clusterrs.append(df_clutser_i)
df = pd.concat(df_clusterrs)
df1 = generate_random(n=1000, cluster_id=0, low_lat=0, high_lat=89, low_lon=-179, high_lon=180)
return df, df1

df, df1 = generate_random_inputs()

cluster_geoms = []
for color, cluster_id in zip(["red", "blue", "orange", "cyan"],
df.cluster.unique().tolist()):
dfq = df[df["cluster"] == cluster_id]
df_cluster_coords = dfq[["latitude", "longitude"]]
Y = df_cluster_coords.to_numpy()
# plot cluster data
plt.plot(Y[:, 1], Y[:, 0], 'o', color=color)
# compute hull
hull = ConvexHull(Y)
# hull.vertices gives indexes of the hull points
hull_vertices = df_cluster_coords.iloc[hull.vertices].to_numpy()
_hull_X = hull_vertices[:, 1]
_hull_Y = hull_vertices[:, 0]
# close shape
_hull_X = np.append(_hull_X, _hull_X[0])
_hull_Y = np.append(_hull_Y, _hull_Y[0])
plt.plot(_hull_X, _hull_Y, "x", color=color, ls="--")
cluster_geoms.append(Polygon(coords_to_shapely_point(x=_hull_X, y=_hull_Y)))

def is_in_clusters(row, clusters: List[Polygon]) -> bool:
p = Point(row.longitude, row.latitude)
is_in_cluster = False
for c_geom in clusters:
is_in_cluster |= c_geom.contains(p)
return is_in_cluster

df1["in_cluster"] = df1.apply(is_in_clusters, axis=1, clusters=cluster_geoms)

for latitude, longitude, in_cluster in df1.itertuples(index=False):
plt.plot(longitude, latitude, "x", color="green" if in_cluster else "black")
plt.show()
``````