Pattern Guide
Computational Geometry
"Cross products determine orientation. Convex hull wraps everything."
Computational geometry uses cross products for orientation tests, polygon area, and convex hull. Learn the cross product trick, gift wrapping, and Andrew's monotone chain algorithm.
16 min readgeometry problems →
Problems you can solve with this pattern
8 problems · click any to start solving
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;
}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
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];
}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)