Computational geometry often sounds like a highly academic field, but many of its concepts are incredibly practical for developers working across diverse domains. One such fundamental concept is the Convex Hull.
If you’ve ever needed to find the “outline” of a set of points, detect collisions, or filter data, you’ve likely brushed shoulders with the problem the Convex Hull solves. This post cuts through the theoretical fluff to show you what it is, why it matters, and how to use it with practical examples.
What is a Convex Hull?
Imagine you have a scatter of points on a flat surface. Now, imagine stretching a rubber band around all these points and letting it snap tight. The shape formed by the stretched rubber band is the Convex Hull of those points.
More formally, the convex hull of a set of points is the smallest convex polygon (in 2D), or convex polyhedron (in 3D and higher dimensions), that contains all the points.
Key Characteristics:
- Convex: Any line segment connecting two points inside the hull must lie entirely within the hull. Think of a circle or a square – they are convex. A star shape is not, because you can draw a line between two points in its “arms” that passes outside the star.
- Smallest: It’s the tightest possible “wrap” around the points.
- Contains all points: No point from the original set is left outside the hull.
- Vertices are original points: The vertices (corners) of the convex hull are always some subset of the original points.
Why Do Developers Care About Convex Hulls? Practical Applications
The Convex Hull isn’t just an abstract geometric concept; it has powerful applications in various fields:
- Collision Detection: In game development, robotics, or simulations, objects are often simplified to their convex hulls for faster collision detection. If the convex hulls don’t intersect, the actual objects definitely don’t.
- Image Processing: Used for shape analysis, object recognition, and feature extraction. For instance, finding the hull of an object’s pixels can give a simplified outline.
- Pattern Recognition & Machine Learning: Identifying clusters of data points or outliers. The convex hull can define the boundary of a cluster.
- Geographic Information Systems (GIS): Determining the boundary of a region defined by a set of GPS coordinates, or finding the smallest area enclosing a set of locations.
- Optimization: Finding the extreme points of a feasible region in linear programming.
- Data Analysis: Visualizing the spread of data points, especially in higher dimensions, or simplifying complex datasets.
Algorithms for Computing the Convex Hull
While the focus of this post is on using the Convex Hull, it’s good to be aware that there are several algorithms to compute it. Some of the most well-known include:
- Graham Scan: A common and efficient 2D algorithm that sorts points by angle around a pivot point and then uses a stack to build the hull.
- Jarvis March (Gift Wrapping): An intuitive algorithm that starts with an extreme point and “wraps” around the set of points, finding the next point on the hull by picking the one with the smallest angle. It’s simpler to understand but often less efficient for very large datasets than Graham Scan.
- Monotone Chain (Andrew’s Algorithm): Divides the problem into finding the upper and lower hulls, often more efficient than Graham Scan.
- Quickhull: A divide-and-conquer algorithm, similar in spirit to Quicksort.
Most practical applications leverage highly optimized libraries that implement these algorithms (or variations thereof) efficiently.
Practical Example: Computing Convex Hull with Python (SciPy)
For Python developers, the scipy.spatial module provides a highly optimized and easy-to-use implementation of the Convex Hull. This is typically what you’ll reach for in real-world projects.
First, ensure you have the necessary libraries installed:
pip install numpy scipy matplotlibExample 1: Simple 2D Convex Hull
Let’s start with a basic set of 2D points and visualize its convex hull.
import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
# 1. Define a set of 2D points
points = np.array([
[0, 0],
[1, 1],
[0.5, 2],
[2, 0.5],
[3, 3],
[1.5, 0],
[2.5, 1.5],
[0.8, 1.2],
[0.1, 2.5]
])
# 2. Compute the Convex Hull
# Note: ConvexHull expects a 2D array where each row is a point.
hull = ConvexHull(points)
# 3. Print information about the hull
print("Points used for Hull computation:\n", points)
print("\nNumber of vertices on the hull:", len(hull.vertices))
print("Indices of hull vertices in the original points array:", hull.vertices)
print("Simplices (indices of points forming the facets/edges of the hull):\n", hull.simplices)
# Note: For 2D, simplices are pairs of indices representing edges.
# For 3D, simplices are triples of indices representing triangular faces.
# 4. Visualize the hull
plt.plot(points[:,0], points[:,1], 'o', label='Original Points') # Plot original points
for simplex in hull.simplices:
plt.plot(points[simplex, 0], points[simplex, 1], 'k-') # Plot hull edges
plt.plot(points[hull.vertices, 0], points[hull.vertices, 1], 'ro', label='Hull Vertices') # Highlight hull vertices
plt.title('2D Convex Hull')
plt.xlabel('X-coordinate')
plt.ylabel('Y-coordinate')
plt.grid(True)
plt.legend()
plt.gca().set_aspect('equal', adjustable='box')
plt.show()Points used for Hull computation:
[[0. 0. ]
[1. 1. ]
[0.5 2. ]
[2. 0.5]
[3. 3. ]
[1.5 0. ]
[2.5 1.5]
[0.8 1.2]
[0.1 2.5]]
Number of vertices on the hull: 6
Indices of hull vertices in the original points array: [0 5 3 4 2 8]
Simplices (indices of points forming the facets/edges of the hull):
[[0 5]
[5 3]
[3 4]
[4 2]
[2 8]
[8 0]]
# Expected Plot Output Description:
# A scatter plot will appear.
# Blue circles ('o') will represent the original `points`.
# Red circles ('ro') will highlight the points that form the vertices of the convex hull.
# Black lines ('k-') will connect these hull vertices, forming the outline of the convex hull.
# The shape will resemble a stretched rubber band around the outermost points.
# The points [0,0], [1.5,0], [2,0.5], [3,3], [0.5,2], and [0.1,2.5] will form the vertices of the hull.Explanation of hull attributes:
hull.vertices: An array of indices into the originalpointsarray, indicating which points form the vertices of the convex hull. These are the “corners” of your rubber band.hull.simplices: An array of arrays, where each inner array represents a “simplex” of the hull. In 2D, a simplex is an edge (a pair of point indices). In 3D, it’s a triangular face (a triplet of point indices). These define the connectivity of the hull.hull.points: The original input points.hull.area(2D) orhull.volume(3D): The area or volume enclosed by the hull.
Example 2: Extracting Ordered Vertices of the Hull
Often, you don’t just need the hull itself, but the ordered sequence of points that make up its boundary. This is particularly useful for plotting, path generation, or defining polygons.
import numpy as np
from scipy.spatial import ConvexHull
points = np.array([
[0, 0], [1, 1], [0.5, 2], [2, 0.5], [3, 3],
[1.5, 0], [2.5, 1.5], [0.8, 1.2], [0.1, 2.5]
])
hull = ConvexHull(points)
# The `simplices` attribute gives us the edges. For 2D, they are pairs of indices.
# We can traverse these to get an ordered list of vertices.
# One common way to do this is to start from an arbitrary vertex and follow the edges.
# Let's get the first vertex index from the hull's vertices
hull_points_indices = hull.vertices
# To get the ordered vertices:
# `scipy.spatial.ConvexHull` doesn't directly give ordered vertices in a single list.
# We can reconstruct it using `simplices`.
# Note: For 2D, `hull.simplices` are edges. We can build an adjacency list and traverse.
# A simpler way for visualization is to use `hull.simplices` and then ensure connectivity.
# For a simple, connected hull in 2D, one can often iterate through `simplices`
# and pick a starting point, then ensure the next point connects.
# Let's extract the points that form the hull
hull_points = points[hull.vertices]
# The `simplices` attribute provides the connectivity. We can use this to order them.
# A common trick is to concatenate all simplices and remove duplicates.
# However, this won't necessarily give a *cyclical* order.
# For a guaranteed cyclical order, one needs to trace the edges.
# Let's manually trace based on the simplices for demonstration, picking an arbitrary start.
ordered_hull_indices = []
# Start with the first vertex in hull.vertices
current_index = hull.vertices[0]
ordered_hull_indices.append(current_index)
# Find the simplex (edge) that contains this first vertex
# and identify the next vertex in the sequence
for i in range(len(hull.simplices)):
if hull.simplices[i, 0] == current_index:
next_index = hull.simplices[i, 1]
break
elif hull.simplices[i, 1] == current_index:
next_index = hull.simplices[i, 0]
break
else:
# This loop logic is simplified for demonstration.
# A robust solution might involve creating an adjacency map from simplices
# and then performing a graph traversal (like DFS/BFS or simply following edges).
# SciPy's `ConvexHull` object itself often has `simplices` ordered such that
# they can be plotted sequentially for 2D.
# The simplest way to get ordered points for plotting in 2D is often:
# `plt.plot(points[hull.vertices, 0], points[hull.vertices, 1], 'k-')` for edges
# and then closing the loop `plt.plot(points[[hull.vertices[-1], hull.vertices[0]], 0], points[[hull.vertices[-1], hull.vertices[0]], 1], 'k-')`
# However, `hull.simplices` itself provides the edges which implicitly define the order.
# Let's just extract all unique vertices from simplices and show them.
# A more direct approach to get the *ordered* vertices for plotting in 2D
# is to ensure the plot connects them cyclically.
# The `hull.vertices` array itself does not guarantee an angular or sequential order.
# The `simplices` define the edges, which implies the order.
# For 2D, you can construct the ordered list by picking a point and finding its neighbors in the `simplices`.
# Let's get the specific points for the hull's edges directly from simplices for clarity:
ordered_hull_points = []
for simplex in hull.simplices:
ordered_hull_points.append(points[simplex[0]])
# Avoid adding duplicate points for the same edge (already covered by next simplex's start)
# The last point of one simplex is the first point of the next in a cyclic order.
# So just appending the first point of each simplex and then adding the last point once
# and closing the loop is typical for plotting.
# Let's get the points corresponding to the vertices in hull.vertices.
# For plotting, you often just use `points[hull.vertices, 0]` and `points[hull.vertices, 1]`.
# To get them in a sequence that forms the boundary, you can sort them by angle,
# or trace using `simplices`.
# SciPy's `ConvexHull` doesn't automatically sort `hull.vertices` for 2D.
# We can use the `simplices` to trace the boundary.
# For a 2D hull, `simplices` effectively gives the ordered pairs of vertices.
# We can construct the final ordered list:
ordered_points_for_boundary = []
# `hull.simplices` lists the edges.
# Let's just collect all unique points involved in the simplices, then sort them by angle
# from a central point (e.g., centroid of the hull points).
# Get the actual points that are vertices of the hull
hull_vertex_coords = points[hull.vertices]
# Calculate centroid of hull vertices for sorting by angle
centroid_x = np.mean(hull_vertex_coords[:, 0])
centroid_y = np.mean(hull_vertex_coords[:, 1])
# Sort hull vertices by angle around the centroid
def angle_from_centroid(point):
return np.arctan2(point[1] - centroid_y, point[0] - centroid_x)
# Note: `hull_vertex_coords` is already a subset of original `points`.
# Sort the `hull_vertex_coords` based on their angle around the centroid.
sorted_hull_points = sorted(hull_vertex_coords, key=angle_from_centroid)
# Convert back to a numpy array for consistent output
sorted_hull_points = np.array(sorted_hull_points)
print("Original Points:\n", points)
print("\nPoints on the Convex Hull (indices from original points):", hull.vertices)
print("\nSorted Points on the Convex Hull (cyclically, by angle from centroid):\n", sorted_hull_points)
# To close the loop for plotting or polygon definition, append the first point at the end
closed_loop_points = np.vstack([sorted_hull_points, sorted_hull_points[0]])
print("\nPoints for Closed Loop Boundary (first point appended at end):\n", closed_loop_points)Original Points:
[[0. 0. ]
[1. 1. ]
[0.5 2. ]
[2. 0.5]
[3. 3. ]
[1.5 0. ]
[2.5 1.5]
[0.8 1.2]
[0.1 2.5]]
Points on the Convex Hull (indices from original points): [0 5 3 4 2 8]
Sorted Points on the Convex Hull (cyclically, by angle from centroid):
[[0. 0. ]
[1.5 0. ]
[2. 0.5 ]
[3. 3. ]
[0.5 2. ]
[0.1 2.5 ]]
Points for Closed Loop Boundary (first point appended at end):
[[0. 0. ]
[1.5 0. ]
[2. 0.5 ]
[3. 3. ]
[0.5 2. ]
[0.1 2.5 ]
[0. 0. ]]Note: The hull.vertices attribute does not guarantee a specific order (e.g., clockwise or counter-clockwise). If you need the points in sequential order to draw a polygon or trace a path, you typically need to re-sort them (e.g., by angle around the centroid as shown above) or explicitly trace the edges using hull.simplices. For 2D, the simplices often provide pairs that can be directly plotted to form the outline.
Example 3: 3D Convex Hull
The concept extends to higher dimensions. In 3D, the convex hull is a convex polyhedron whose faces are triangles (simplices).
import numpy as np
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
# 1. Define a set of 3D points
points_3d = np.array([
[0, 0, 0],
[1, 0, 0],
[0, 1, 0],
[0, 0, 1],
[1, 1, 0],
[1, 0, 1],
[0, 1, 1],
[1, 1, 1],
[0.5, 0.5, 0.5], # Inner point
[0.2, 0.8, 0.1],
[0.9, 0.1, 0.7]
])
# 2. Compute the 3D Convex Hull
hull_3d = ConvexHull(points_3d)
# 3. Print information
print("Points used for 3D Hull computation:\n", points_3d)
print("\nNumber of vertices on the 3D hull:", len(hull_3d.vertices))
print("Indices of 3D hull vertices in the original points array:", hull_3d.vertices)
print("Simplices (indices of points forming triangular faces of the hull):\n", hull_3d.simplices)
print("Volume of the 3D hull:", hull_3d.volume)
# 4. Visualize the 3D hull (more complex but illustrative)
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
# Plot original points
ax.scatter(points_3d[:,0], points_3d[:,1], points_3d[:,2], c='b', marker='o', label='Original Points')
# Plot hull vertices
ax.scatter(points_3d[hull_3d.vertices,0], points_3d[hull_3d.vertices,1], points_3d[hull_3d.vertices,2], c='r', marker='o', s=50, label='Hull Vertices')
# Plot hull faces (triangles)
for s in hull_3d.simplices:
s = np.append(s, s[0]) # Close the loop for each triangle face
ax.plot(points_3d[s, 0], points_3d[s, 1], points_3d[s, 2], 'k-') # Edges
# Note: For filling faces, you'd typically use `Poly3DCollection`
# from mpl_toolkits.mplot3d.art3d.
# This example just plots the edges for clarity.
# Plot faces (optional, uncomment for filled faces)
# from mpl_toolkits.mplot3d.art3d import Poly3DCollection
# for s in hull_3d.simplices:
# triangle = points_3d[s]
# poly3d = [triangle]
# ax.add_collection3d(Poly3DCollection(poly3d, facecolors='cyan', linewidths=1, edgecolors='r', alpha=.25))
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.set_zlabel('Z')
ax.set_title('3D Convex Hull')
ax.legend()
plt.show()Points used for 3D Hull computation:
[[0. 0. 0. ]
[1. 0. 0. ]
[0. 1. 0. ]
[0. 0. 1. ]
[1. 1. 0. ]
[1. 0. 1. ]
[0. 1. 1. ]
[1. 1. 1. ]
[0.5 0.5 0.5]
[0.2 0.8 0.1]
[0.9 0.1 0.7]]
Number of vertices on the 3D hull: 8
Indices of 3D hull vertices in the original points array: [0 1 2 3 4 5 6 7]
Simplices (indices of points forming triangular faces of the hull):
[[0 2 3]
[0 3 1]
[0 1 2]
[1 3 5]
[1 5 4]
[1 4 2]
[2 4 6]
[2 6 3]
[3 6 5]
[4 5 7]
[4 7 6]
[5 6 7]]
Volume of the 3D hull: 1.0
# Expected Plot Output Description:
# A 3D scatter plot will appear.
# Blue circles ('o') will represent all original `points_3d`.
# Larger red circles ('ro') will highlight the points that form the vertices of the 3D convex hull.
# Black lines ('k-') will connect the vertices to form the edges of the triangular faces of the hull.
# In this specific example, the points represent the corners of a unit cube, and the inner points are enclosed.
# The hull will look like a wireframe cube, enclosing all points.Considerations & Gotchas
- Computational Complexity: For
Npoints, 2D convex hull algorithms typically have a time complexity of O(N log N) or O(N h) wherehis the number of points on the hull. For higher dimensions (D > 3), it grows significantly, becoming O(N^(D/2)) in worst-case scenarios, making it computationally expensive. - Degenerate Cases:
- Collinear Points: If multiple points lie on the same edge of the hull, some algorithms might include all of them as vertices, while others might only include the two extreme points of that segment. SciPy’s
ConvexHullusually gives a minimal set of vertices. - Duplicate Points: Redundant points generally don’t affect the hull’s shape but can slightly affect performance. Pre-processing to remove duplicates can be beneficial.
- Collinear Points: If multiple points lie on the same edge of the hull, some algorithms might include all of them as vertices, while others might only include the two extreme points of that segment. SciPy’s
- Floating Point Precision: Geometric computations often suffer from floating-point inaccuracies. Robust implementations (like SciPy’s underlying Qhull library) handle these cases carefully.
Conclusion
The Convex Hull is a powerful and intuitive concept in computational geometry with a wide array of practical applications for developers. While its theoretical underpinnings involve fascinating algorithms, modern libraries like SciPy make it incredibly accessible for everyday use.
By understanding what a Convex Hull represents and how to utilize existing tools to compute it, you can simplify complex shape analysis, optimize collision detection, and gain insights from your data with just a few lines of code. Experiment with different point sets, even in 3D, and see how this fundamental concept helps you tackle real-world problems.
Last updated on