Convex Hulls in Python

In this tutorial, we will walk through the implementation of a different and unique clustering approach with the help of convex hulls. But it’s always important to understand the concept before jumping right into the code! So let’s understand what convex hulls are.

Introduction to Convex Hulls

A Convex object is an object which has no interior angles that are greater than 180 degrees. A Hull implies the exterior of the shape of the object. A convex hull encloses a set of points and it acts as a cluster boundary which helps in determining all the points within a cluster. Here’s a simple real-life illustration of a convex hull in a cow. You can see that the outside hull encloses the whole cow inside the hull.

Code Implementation of Convex Hull

We will start off by creating the sample dataset for the tutorial with the help of the sci-kit learn library. We will be making use of the make_blobs function. We will be creating data for 5 different clusters. Look at the code below.

import numpy as np
from sklearn.datasets import make_blobs

# center points for the clusters
centers = [[0, 1, 0], [1.5, 1.5, 1], [1, 1, 1],[1,1,3],[2,2,2]]
# standard deviations for the clusters
stds = [0.13, 0.12, 0.12,0.15,0.14]

# create dataset using make_blobs - assign centers, standard deviation and the number of points
X, labels_true = make_blobs(n_samples=1000, centers=centers, cluster_std=stds, random_state=0)
point_indices = np.arange(1000)

Overall we generated 1000 data points assigned to five different clusters. Next, we will attempt to visualize the data. Since our dataset is in 3-dimensional form, we will be plotting a 3D plot for the data. Observe the code below. We will be plotting all the data points along with assigning colors to the plot to represent clusters. Look how amazing the plot turned out to be!

Also Read: 3-Dimensional Plots in Python Using Matplotlib

import matplotlib.pyplot as plt
plt.style.use('seaborn')

x,y,z = X[:,0],X[:,1],X[:,2]

fig = plt.figure(figsize = (20,10),facecolor="w") 
ax = plt.axes(projection="3d") 

list_colours = ["red", "green", "blue","magenta","brown"]
cluster_colors = [list_colours[i] for i in labels_true]

scatter_plot = ax.scatter3D(x,y,z,c =cluster_colors,marker ='o')
plt.title("Scatter plot of the dataset",fontsize=30) 
ax.set_xlabel('X_values', fontweight ='bold')  
ax.set_ylabel('Y_values', fontweight ='bold') 

plt.show()

We will be importing the ConvexHull and convex hull plotting function from the spatial module of scipy. We will be assigning the convex hull points for the dataset that we generated.

from scipy.spatial import ConvexHull, convex_hull_plot_2d
rng = np.random.default_rng()
hull = ConvexHull(X)

Let’s visualize the convex hull in space using the code below. We will be using the simplices function of the hull object created to plot the boundaries of the convex hull.

fig = plt.figure(figsize = (20,10),facecolor="w") 
ax = plt.axes(projection="3d") 
for simplex in hull.simplices:
    ax.plot3D(X[simplex, 0], X[simplex, 1],X[simplex, 2], 's-')

Have a look at how amazing the convex hull looks in the 3D space.

To make things a little more interesting, let us plot both the clusters as well as the hull together in one plot using the code mentioned below.

fig = plt.figure(figsize = (20,10),facecolor="w") 
ax = plt.axes(projection="3d") 
scatter_plot = ax.scatter3D(x,y,z,c =cluster_colors,marker ='o')
for simplex in hull.simplices:
    ax.plot3D(X[simplex, 0], X[simplex, 1],X[simplex, 2], 's-')

Looks AMAZING right?!

Conclusion

Congratulations! Now you know how to plot these amazing convex hull boundaries for your plots. I hope you enjoyed the tutorial and found this informative and interesting as well! If you loved this tutorial, I would recommend you these tutorials :

Happy coding and plotting! 😃