Convex hull computation in SciPy

Introduction

A convex hull is the smallest shape that wraps around a set of points, like stretching a rubber band around nails on a board.

Finding the boundary of scattered GPS locations on a map.

Determining the outer shape of a cluster of data points in analysis.

Creating a simple shape that encloses irregular objects in images.

Calculating the minimal fence needed to enclose animals in a field.

Syntax

SciPy

from scipy.spatial import ConvexHull
hull = ConvexHull(points)

points is a 2D array of coordinates, like [[x1, y1], [x2, y2], ...]

The hull object contains vertices that form the convex boundary.

Examples

Compute convex hull for four points forming a square.

SciPy

import numpy as np
from scipy.spatial import ConvexHull
points = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
hull = ConvexHull(points)

Compute convex hull for 10 random points in 2D space.

SciPy

import numpy as np
points = np.random.rand(10, 2)  # 10 random points in 2D
hull = ConvexHull(points)

Sample Program

This program finds the convex hull of six points and prints which points form the boundary and their coordinates.

SciPy

import numpy as np
from scipy.spatial import ConvexHull

# Define points in 2D
points = np.array([
    [1, 1], [2, 5], [3, 3], [5, 3], [3, 2], [2, 2]
])

# Compute convex hull
hull = ConvexHull(points)

# Print the indices of points forming the hull
print('Hull vertices indices:', hull.vertices)

# Print the coordinates of hull vertices
print('Hull vertices coordinates:')
for vertex in hull.vertices:
    print(points[vertex])

Important Notes

The convex hull vertices are given as indices of the original points array.

The vertices are listed in order around the hull, which helps in drawing the shape.

Convex hull works in any number of dimensions, but visualization is easiest in 2D or 3D.

Summary

Convex hull wraps points with the smallest convex shape.

Use scipy.spatial.ConvexHull to compute it easily.

The hull vertices tell you which points form the boundary.