Pattern Reference
Geometry
"Convex hull, line intersection, polygon area, point in polygon, rotating calipers."
Loading...
Deep Dive Tutorial
Computational geometry problems involve points, lines, and polygons. The fundamental operation is the cross product — it tells you the orientation of three points (clockwise, counterclockwise, or collinear) and computes areas. Everything else (convex hull, line intersection, point-in-polygon) builds on top of cross products.
The Cross Product
Cross product and orientation
// 2D cross product of vectors (b-a) and (c-a)
// = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)
function cross(a, b, c) {
return (b[0]-a[0]) * (c[1]-a[1]) - (b[1]-a[1]) * (c[0]-a[0]);
}
// Interpretation:
// > 0: counterclockwise (left turn)
// < 0: clockwise (right turn)
// = 0: collinear
// Distance between two points
function dist(a, b) {
return Math.sqrt((b[0]-a[0])**2 + (b[1]-a[1])**2);
}
// Area of polygon (shoelace formula)
function polygonArea(points) {
let area = 0;
const n = points.length;
for (let i = 0; i < n; i++) {
const j = (i + 1) % n;
area += points[i][0] * points[j][1];
area -= points[j][0] * points[i][1];
}
return Math.abs(area) / 2;
}Convex Hull — Andrew's Monotone Chain
lightbulb
Convex hull = smallest convex polygon containing all points.
Andrew's monotone chain builds lower and upper hulls separately:
1. Sort points by (x, then y)
2. Build lower hull left→right: while last turn is clockwise, pop the last point
3. Build upper hull right→left: same logic
4. Combine (drop duplicate endpoints)
Andrew's monotone chain builds lower and upper hulls separately:
1. Sort points by (x, then y)
2. Build lower hull left→right: while last turn is clockwise, pop the last point
3. Build upper hull right→left: same logic
4. Combine (drop duplicate endpoints)
Convex Hull — O(n log n)
function convexHull(points) {
points.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const n = points.length;
if (n < 3) return points;
const lower = [];
for (const p of points) {
while (lower.length >= 2 &&
cross(lower.at(-2), lower.at(-1), p) <= 0)
lower.pop();
lower.push(p);
}
const upper = [];
for (let i = n - 1; i >= 0; i--) {
const p = points[i];
while (upper.length >= 2 &&
cross(upper.at(-2), upper.at(-1), p) <= 0)
upper.pop();
upper.push(p);
}
// Remove last point of each half (duplicates of first/last)
lower.pop(); upper.pop();
return [...lower, ...upper];
}Worked Problems
More Worked Problems
lightbulb
Floating point pitfalls: Geometry problems with floating point coordinates often fail due to precision. Strategies:
1. Use integer arithmetic where possible (scale and avoid division)
2. Use ε comparisons:
3. GCD normalization for slopes eliminates float issues entirely
Key formulas:
- Cross product (orientation): (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)
- Triangle area: |cross product| / 2
- Polygon area (shoelace): |Σ(x_i * y_{i+1} - x_{i+1} * y_i)| / 2
- Distance²: dx*dx + dy*dy (avoid sqrt when just comparing)
1. Use integer arithmetic where possible (scale and avoid division)
2. Use ε comparisons:
Math.abs(a - b) < 1e-9 instead of a === b3. GCD normalization for slopes eliminates float issues entirely
Key formulas:
- Cross product (orientation): (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)
- Triangle area: |cross product| / 2
- Polygon area (shoelace): |Σ(x_i * y_{i+1} - x_{i+1} * y_i)| / 2
- Distance²: dx*dx + dy*dy (avoid sqrt when just comparing)