Concepts11
3D Geometry Basics
3D geometry relies on a small toolkit: vectors, dot products, cross products, and planes; mastering these unlocks most 3D problem-solving.
Half-Plane Intersection
Half-plane intersection (HPI) computes the common region that satisfies many linear side-of-line constraints in the plane.
Minkowski Sum
The Minkowski sum A ⊕ B adds every point of set A to every point of set B, and for convex polygons it can be computed in O(n + m) by merging edge directions.
Pick's Theorem
Pick's Theorem connects area and lattice-point counts for any simple polygon with integer-coordinate vertices.
Polygon Area and Centroid
The signed area of a simple polygon can be computed in O(n) using the shoelace formula, which sums cross products of consecutive vertices.
Rotating Calipers
Rotating calipers is a geometric two-pointer technique that sweeps two (or more) parallel support lines around a convex polygon.
Basic Geometry - Lines and Segments
A line can be represented by two points, a point with a direction vector, or the general form ax + by + c = 0, and these forms are interconvertible.
Convex Hull
The convex hull is the smallest convex polygon that contains all given points, like a rubber band snapped around nails on a board.
Point in Polygon
Point-in-polygon decides whether a point lies outside, inside, or on the boundary of a polygon.
Orientation and CCW
Orientation (CCW test) tells whether three points make a left turn, right turn, or are collinear by using the sign of a 2D cross product.
Basic Geometry - Points and Vectors
A 2D point can be treated as a vector from the origin, so vector math (addition, scaling, dot, cross) applies directly to points.