Convex hull computation in SciPy - Step-by-Step Execution

Concept Flow - Convex hull computation

Input: Set of points

↓

Compute convex hull using scipy.spatial.ConvexHull

↓

Identify vertices forming the hull

↓

Output hull vertices and edges

↓

Visualize or use hull for analysis

Start with points, compute hull with scipy, get vertices, then output or visualize the hull.

Execution Sample

SciPy

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

This code computes the convex hull of 5 points and prints the indices of hull vertices.

Execution Table

Step	Action	Input/State	Output/Result
1	Input points array created	points = [[0,0],[1,1],[1,0],[0,1],[0.5,0.5]]	points array ready
2	Call ConvexHull(points)	points array	ConvexHull object created
3	Compute hull vertices	ConvexHull object	hull.vertices = [0, 2, 3, 1]
4	Print hull vertices	hull.vertices	Output: [0 2 3 1]
5	End	All steps done	Convex hull computed and vertices identified

💡 All points processed; hull vertices identified; computation complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
points	undefined	[[0,0],[1,1],[1,0],[0,1],[0.5,0.5]]	[[0,0],[1,1],[1,0],[0,1],[0.5,0.5]]	[[0,0],[1,1],[1,0],[0,1],[0.5,0.5]]	[[0,0],[1,1],[1,0],[0,1],[0.5,0.5]]
hull	undefined	undefined	ConvexHull object	ConvexHull object with vertices [0,2,3,1]	ConvexHull object with vertices [0,2,3,1]
hull.vertices	undefined	undefined	undefined	[0, 2, 3, 1]	[0, 2, 3, 1]

Key Moments - 3 Insights

Why does hull.vertices not include the point [0.5, 0.5]?

Because [0.5, 0.5] lies inside the polygon formed by the other points, it is not on the convex hull boundary. See execution_table step 3 where vertices are identified.

What does hull.vertices represent exactly?

hull.vertices gives the indices of the input points that form the outer boundary (convex hull). This is shown in execution_table step 3.

Why do the vertices indices appear in a specific order?

The indices are ordered to form a polygon around the hull points, usually counterclockwise. This ordering helps in visualization and further analysis.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does hull.vertices contain?

A Indices of points forming the convex hull boundary

B Indices of points inside the hull

C Coordinates of all input points

D Number of points in the input

💡 Hint

Refer to execution_table row with step 3 showing hull.vertices = [0, 2, 3, 1]

At which step does the ConvexHull object get created?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Check execution_table row with step 2 describing ConvexHull object creation

If we add a point outside the current hull, how will hull.vertices change?

A It will remain the same

B It will include the new point's index in hull.vertices

C It will exclude all previous points

D It will become empty

💡 Hint

Adding an outside point changes the hull boundary, so hull.vertices updates to include it

Concept Snapshot

Convex hull computation with scipy:
- Input: array of 2D points
- Use scipy.spatial.ConvexHull(points)
- hull.vertices gives indices of hull boundary points
- Vertices ordered to form polygon
- Useful for shape analysis and visualization

Full Transcript

We start with a set of points in 2D space. Using scipy's ConvexHull function, we compute the smallest convex polygon enclosing all points. The hull object contains vertices which are indices of points forming the hull boundary. Points inside the hull are excluded from vertices. The vertices are ordered to form a polygon. This process helps in understanding the shape and boundary of point sets.