Chapter 1: Introduction to Convex Hulls

In recent times, I encountered a challenge involving the determination of the convex hull for a specific collection of points. This led me to delve deeper into the spatial package of Python's SciPy. The convex hull is defined as the smallest convex shape that encloses all points in a dataset. To visualize this concept, think of the points as nails on a board; the convex hull can be likened to a rubber band stretched around the outermost nails, thereby enclosing all points within. In a two-dimensional space, this results in a polygon, while in higher dimensions, it produces a structure known as a simplex.

Chapter 2: The 2D Scenario

The two-dimensional scenario involves working with points that are positioned on a flat plane. Here, the convex hull manifests as a polygon, with its vertices connected by straight lines. Let's begin by generating some random points and visualizing them with a scatter plot.

import matplotlib.pyplot as plt

from scipy.spatial import ConvexHull

import numpy as np

points = np.random.rand(20, 2)

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

plt.xlim(0, 1)

plt.ylim(0, 1)

plt.gca().set_aspect("equal")

Next, we will calculate the convex hull using SciPy’s ConvexHull function, which employs the Quickhull algorithm and offers various attributes for analyzing and visualizing the resulting convex hull.

hull = ConvexHull(points)

The vertices property reveals the indices of the points that constitute the vertices of the convex hull, which form the outer boundary.

hull.vertices

The output will look something like this:

array([ 5, 2, 18, 14, 6, 17, 0], dtype=int32)

Similarly, the simplices property indicates the indices of the points that create the simplicial facets of the convex hull. In 2D, these simplices are merely line segments connecting the vertices.

hull.simplices

The output will be:

array([[ 2, 5],

[ 0, 5],

[ 0, 17],

[ 6, 17],

[ 6, 14],

[18, 14],

[18, 2]], dtype=int32)

Now, let’s define a function to visualize the hull. The red circles will represent the vertices of the convex hull, while the red lines will illustrate the line segments forming the perimeter.

def plot_hull():

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

plt.plot(points[hull.vertices][:, 0], points[hull.vertices][:, 1], 'ro')

for facet in hull.simplices:

plt.plot(points[facet, 0], points[facet, 1], 'r-')

plt.xlim(0, 1)

plt.ylim(0, 1)

plt.gca().set_aspect("equal")

plot_hull()

The perimeter of the red polygon can be calculated using the area attribute of the hull object, which in 2D represents a length.

hull.area

This might yield a value like:

3.142052162690126

The volume property reflects the interior of the hull, which in a 2D context corresponds to an area.

hull.volume

You may receive an output such as:

0.6449431389347489

For any given facet, the neighbors property can be used to identify its neighboring facets.

hull.neighbors

The output will show the connections between neighboring facets:

array([[1, 6],

[0, 2],

[3, 1],

[2, 4],

[5, 3],

[4, 6],

[0, 5]], dtype=int32)

To clarify this concept, let’s highlight the facet with index 2 and its neighboring facets.

plot_hull()

# Highlighting facet with index 2:

facet = hull.simplices[2]

plt.plot(points[facet].T[0], points[facet].T[1], 'g-', lw=3)

# Identifying the indices of the neighboring facets:

neighbor_inds = hull.neighbors[2, :]

# Getting the point indices for the ends of each neighboring facet:

facets = hull.simplices[neighbor_inds]

for facet in facets:

plt.plot(points[facet].T[0], points[facet].T[1], 'b-', lw=3)

In this visualization, the facet with index 2 is marked in green, while its neighboring facets are shown in blue.

Chapter 3: The 3D Scenario

The three-dimensional scenario involves points situated in a three-dimensional space. Here, the convex hull appears as a polyhedron. The method for computing the convex hull remains similar to the 2D case, but now we need to account for three-dimensional facets and vertices.

from mpl_toolkits.mplot3d.art3d import Poly3DCollection

points = np.random.rand(30, 3)

hull = ConvexHull(points)

fig = plt.figure()

ax = fig.add_subplot(111, projection='3d')

# Plotting the points

ax.scatter(points[:, 0], points[:, 1], points[:, 2], 'o')

# Visualizing the convex hull

vertices = [points[face] for face in hull.simplices]

ax.add_collection3d(Poly3DCollection(vertices, facecolors='cyan', linewidths=1, edgecolors='r'))

In this section, we have created random 3D points and used the ConvexHull function to compute the convex hull. We then utilized Matplotlib's 3D plotting functions to display the hull as a polyhedron with cyan-colored faces.

The vertices property in 3D provides the indices of the points forming the vertices of the polyhedron, which outline the convex hull.

hull.vertices

An example output might be:

array([ 0, 1, 3, 4, 5, 6, 7, 9, 10, 13, 14, 16, 19, 20, 21, 23, 25,

26, 27, 28, 29], dtype=int32)

The simplices property shows the indices of the vertices for each triangular facet of the convex hull. In 3D, these facets are triangles that make up the faces of the polyhedron.

hull.simplices

Example output:

array([[ 1, 9, 29],

[ 0, 25, 10],

[ 0, 19, 10],

[ 5, 19, 29],

[ 5, 19, 10],

[ 5, 1, 29],

...

], dtype=int32)

To highlight a particular facet, let's focus on the facet with index 1.

fig = plt.figure()

ax = fig.add_subplot(111, projection='3d')

# Plotting the points

ax.scatter(points[:, 0], points[:, 1], points[:, 2], 'o')

# Plotting the convex hull

vertices = np.array([points[face] for face in hull.simplices])

ax.add_collection3d(Poly3DCollection(vertices, facecolors='cyan', linewidths=1, edgecolors='r'))

ax.add_collection3d(Poly3DCollection([vertices[1]], facecolors='green', linewidths=1, edgecolors='r'))

In this visualization, we highlight a specific facet (with index 1) in green. Such visual representation aids in the analysis of specific components of the hull and proves beneficial for various geometric and spatial assessments.

Chapter 4: Conclusion

The idea of a convex hull is a crucial concept in computational geometry, with applications spanning computer graphics, pattern recognition, image processing, and optimization. This article has demonstrated how to compute and visualize convex hulls in both two-dimensional and three-dimensional spaces using Python's SciPy spatial package.

The first video titled "Point in Polygon (Python3) - YouTube" provides a detailed exploration of how to determine whether a point is located within a polygon using Python.

The second video titled "Creating Regular Polygons in Python (Tutorial) - YouTube" offers a tutorial on generating regular polygons using Python programming techniques.