Find Convex Hull

find-convex-hull

When to Use

• Finding convex hull of point set
• Determining if point is inside polygon
• Computational geometry problems
• Collision detection bounds
• Geographic/map computations

When NOT to Use

• When hull is given (just use it)
• Very few points (= 2 and turn(upper[-2], upper[-1], p) != 'left':

upper.pop() upper.append(p)

# Build lower hull lower = [] for p in reversed(points): while len(lower) >= 2 and turn(lower[-2], lower[-1], p) != 'left': lower.pop() lower.append(p)

return upper[:-1] + lower[:-1] # Remove duplicate endpoints

def turn(A, B, C): """Determine turn direction A -> B -> C using cross product.""" cross = (B[0] - A[0]) (C[1] - B[1]) - (B[1] - A[1]) (C[0] - B[0]) if cross > 0: return 'left' elif cross 0 else 'straight'

def halfhull(sortedpoints): """Build one half of the hull.""" hull = [] for C in sorted_points: # Pop points that don't make left turn while len(hull) >= 2 and turn(hull[-2], hull[-1], C) != 'left': hull.pop() hull.append(C) return hull

def convex_hull(points): """Complete convex hull from two half-hulls.""" if len(points) <= 3: return list(points)

sortedpts = sorted(points) upper = halfhull(sortedpts) lower = halfhull(reversed(sorted_pts))

return upper + lower[1:-1] # Avoid duplicate endpoints

Usage

points = [Point(0, 0), Point(1, 1), Point(2, 0), Point(1, 2), Point(0.5, 0.5)] hull = convex_hull(points)

Returns: [Point(0, 0), Point(2, 0), Point(1, 2)]

## Key Principles
1. **Sort first**: O(n log n) sorting dominates
2. **Stack-based**: Pop non-left-turning points
3. **Cross product**: Positive = left turn, negative = right turn
4. **Two passes**: Upper hull left-to-right, lower hull right-to-left
5. **Named tuples**: Make geometry code readable with .x and .y

## Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

- **Author:** [jimmc414](https://github.com/jimmc414)
- **Source:** [jimmc414/claude-code-plugin-marketplace](https://github.com/jimmc414/claude-code-plugin-marketplace)
- **License:** MIT

Install and usage instructions live in the source repository linked above.