1. Idea in simple words
Imagine many nails hammered into a board.
Now stretch a rubber band around all of them.
The shape made by the rubber band is called the convex hull.
The slow brute force method tries to find which point pairs form the outer boundary.
Main thought
Take every pair of points and ask:
“Does the line joining these two points leave all other points on only one side?”
- If yes, that edge belongs to the convex hull.
- If no, that edge is inside, so ignore it.
That is why this method is called slow:
it checks all pairs, and for each pair it checks all other points.
2. Visual intuition
Suppose you pick two points A and B.
Draw a line from A to B.
Now check every other point:
- if all points are on the left side, or
- all points are on the right side,
then AB is an outer edge.
But if some points are on one side and some on the other side, then that line cuts through the set, so it is not a hull edge.
3. Tiny example
Points:
A(1,1), B(2,4), C(4,5), D(6,3), E(5,1), F(3,2)
If you test edge A-E, maybe all other points lie above it.
So A-E is a hull edge.
If you test edge B-D, some points may lie above and some below.
So B-D is not a hull edge.
4. Orientation test
To know which side a point lies on, we use this value:
[(B_x – A_x)(P_y – A_y) – (B_y – A_y)(P_x – A_x)]
For points A, B, P:
- positive →
Pis on one side - negative →
Pis on the other side - zero →
Pis on the same line
This is the key math behind the algorithm.
5. Brute force algorithm
For every pair of points (Pi, Pj):
- Assume it might be a hull edge.
- Check every other point
Pk. - Compute orientation of
(Pi, Pj, Pk). - If points appear on both sides, reject the edge.
- If all points stay on one side (or on the line), accept the edge.
6. Pseudocode
BRUTE_FORCE_CONVEX_HULL(points): hull_edges = empty list for each pair of points (Pi, Pj): pos = 0 neg = 0 for each other point Pk: value = orientation(Pi, Pj, Pk) if value > 0: pos = pos + 1 else if value < 0: neg = neg + 1 if pos == 0 or neg == 0: add edge (Pi, Pj) to hull_edges return hull_edges
7. Time complexity
There are:
- about n² pairs
- and for each pair, we check n points
So total time is:
[O(n^3)]
That is why it is called slow.
8. Python implementation
This version finds the hull edges and also arranges hull points in circular order.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
import math import matplotlib.pyplot as plt from matplotlib.animation import FuncAnimation # ---------------------------- # Geometry helpers # ---------------------------- def orientation(a, b, c): return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) def brute_force_hull_edges(points): n = len(points) edges = [] for i in range(n): for j in range(i + 1, n): pos = 0 neg = 0 for k in range(n): if k == i or k == j: continue val = orientation(points[i], points[j], points[k]) if val > 0: pos += 1 elif val < 0: neg += 1 # Hull edge if all points are on one side or collinear if pos == 0 or neg == 0: edges.append((points[i], points[j])) return edges def ordered_hull_points_from_edges(edges): # collect unique hull points unique_points = [] seen = set() for a, b in edges: if a not in seen: unique_points.append(a) seen.add(a) if b not in seen: unique_points.append(b) seen.add(b) # sort around centroid cx = sum(p[0] for p in unique_points) / len(unique_points) cy = sum(p[1] for p in unique_points) / len(unique_points) unique_points.sort(key=lambda p: math.atan2(p[1] - cy, p[0] - cx)) return unique_points # ---------------------------- # Example points # ---------------------------- points = [(1, 1), (2, 4), (4, 5), (6, 3), (5, 1), (3, 2), (3.5, 3), (4.2, 2.2)] edges = brute_force_hull_edges(points) hull_points = ordered_hull_points_from_edges(edges) print("Hull edges:") for e in edges: print(e) print("\nHull points in order:") for p in hull_points: print(p) # ---------------------------- # Static plot # ---------------------------- plt.figure(figsize=(6, 6)) # Plot all points x = [p[0] for p in points] y = [p[1] for p in points] plt.scatter(x, y) # Draw hull polygon hx = [p[0] for p in hull_points] + [hull_points[0][0]] hy = [p[1] for p in hull_points] + [hull_points[0][1]] plt.plot(hx, hy) for i, p in enumerate(points): plt.text(p[0] + 0.05, p[1] + 0.05, f"P{i}") plt.title("Convex Hull - Brute Force Method") plt.xlabel("X") plt.ylabel("Y") plt.grid(True) plt.axis("equal") plt.show() |
This animation shows hull edges being added one by one.
9. One-line summary for your tutorial
The brute force convex hull method checks every pair of points and keeps only those pairs for which all remaining points lie on one side of the line.
10. Best short narration script
You can say this in your tutorial:
“In the slow convex hull method, we try every possible pair of points. For each pair, we check all other points. If all points lie on only one side of that line, then that pair forms an outer boundary edge. Repeating this for all pairs gives the convex hull. It is simple to understand, but slow, because it takes O(n³) time.”
I hope this tutorial will create a good foundation for you. If you want tutorials on another topic or you have any queries, please send an mail at contact@spatial-dev.guru.