Menu
For computational geometry: convex hull, point enclosure, polygon operations. Uses monotone chain algorithm with stack-based turn detection.
Install with Codex or Claude Copy this prompt, paste it into Codex, Claude, or another assistant, and let it review the skill page and install it for you.
Based on SOC occupation classification
Conducts iterative deep research on any topic using web search, progressive exploration, and structured synthesis. Use when asked for comprehensive research, deep investigation, thorough analysis, or multi-source exploration of any topic. Triggers: research, investigate, deep dive, comprehensive analysis, explore thoroughly, find everything about.
For cross-cutting concerns: add behavior without modifying functions, caching, timing, logging, validation wrappers.
For performance work: measure before changing, profile to find bottlenecks, compare before and after.
For symbolic computation: ASTs, mathematical expressions, code that manipulates code structure, expression transformations.
For ordered processing: A* search, Dijkstra, event simulation, task scheduling. Efficient min/max extraction with heap-based queue.
For dynamic programming: overlapping subproblems, recursive solutions with repeated computations, memoization to avoid redundant work.
| name | find-convex-hull |
| description | For computational geometry: convex hull, point enclosure, polygon operations. Uses monotone chain algorithm with stack-based turn detection. |
Monotone Chain Algorithm: Sort points, build upper and lower hulls separately using stack.
def convex_hull(points):
"""Find convex hull using monotone chain algorithm. O(n log n)."""
points = sorted(set(points)) # Sort by x, then y
if len(points) <= 3:
return points
# Build upper hull
upper = []
for p in points:
while len(upper) >= 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:
return 'right'
else:
return 'straight'
from collections import namedtuple
Point = namedtuple('Point', 'x y')
def turn(A, B, C):
"""Cross product determines turn direction."""
diff = (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x)
return 'right' if diff < 0 else 'left' if diff > 0 else 'straight'
def half_hull(sorted_points):
"""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)
sorted_pts = sorted(points)
upper = half_hull(sorted_pts)
lower = half_hull(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)]