Point Distance
Euclidean 2D/3D, Manhattan, and Chebyshev distance queries.
Orientation Test
Verify Clockwise, CCW, or Collinear state of three points.
Vector Cross Product
Compute signed area magnitude spanned by 2D vectors.
Vector Dot Product
Evaluate projections and angles between vectors.
Line Intersection
Check slope intersections coordinates of segments and infinite lines.
Convex Hull
Compute enclosing boundary using Graham Scan algorithm.
Polygon Properties
Shoelace Area, perimeter length, and convexity scans.
Circle Properties
Point inside circle tests, circumferences, and areas.
Triangle Properties
Centroid coordinates, areas, perimeters, and side type structures.
Point in Polygon
Verify point containment using horizontal Ray Casting checks.
Closest Pair of Points
Sweep-line strip check placeholders (coming soon).
Coordinate Transform
Translate, rotate, and reflect coordinates on linear matrices.
Formula Center (KaTeX format references)
Computational geometry is highly dependent on cross products and orientations:
- Cross Product 2D: $u \times v = u_x v_y - u_y v_x$ representing signed parallelogram areas.
- Shoelace Formula: $Area = \frac{1}{2} | \sum (x_i y_{i+1} - x_{i+1} y_i) |$ for polygon areas.
Competitive Programming Tips
To prevent floating point precision bugs when writing geometry code:
- Use Integer Types: Whenever possible, keep coordinates and cross product calculations in `long long` integers.
- Epsilon Tolerances: When floats are mandatory, use `const double eps = 1e-9` for inequality checks.