Robust Computational Geometry Primitives: 2D Cross/Dot Products, CCW Orientation & Segment Intersection

1. Formal Invariant — Exact Orientation & Segment Intersection Predicates

2. Exact Segment-Segment Intersection Decision Tree

3. Why sgn() Normalization Prevents Overflow

If coordinates satisfy $|x|, |y| \le 10^9$, then $\text{cross}(A, B, C)$ is bounded by $4 \times 10^{18}$, which fits inside a signed 64-bit integer (int64_t max $\approx 9.22 \times 10^{18}$). However, if you test opposite orientations by multiplying $\text{cross}(A, B, C) \times \text{cross}(A, B, D) < 0$ directly in int64_t, the product reaches $1.6 \times 10^{37}$ and overflows! Mapping each cross product through $\text{sgn}(v) \in \{-1, 0, +1\}$ first reduces the product to $\{-1, 0, +1\}$ with zero overflow risk.

4. Hardware & Floating-Point Realities

5. Complexity Matrix

6. Production-Grade C++20 Implementation

#include <cstdint>
#include <vector>
#include <cmath>

struct Point {
    int64_t x = 0, y = 0;
    Point operator-(const Point& o) const { return {x - o.x, y - o.y}; }
    Point operator+(const Point& o) const { return {x + o.x, y + o.y}; }
};

inline int64_t dot(const Point& u, const Point& v) {
    return u.x * v.x + u.y * v.y;
}

inline int64_t cross(const Point& u, const Point& v) {
    return u.x * v.y - u.y * v.x;
}

// Twice the signed area of triangle ABC (>0: CCW, <0: CW, 0: collinear)
inline int64_t cross(const Point& a, const Point& b, const Point& c) {
    return cross(b - a, c - a);
}

inline int sgn(int64_t val) {
    return (val > 0) - (val < 0);
}

// Returns true iff point p lies on closed segment AB
inline bool on_segment(const Point& a, const Point& b, const Point& p) {
    return cross(a, b, p) == 0 && dot(a - p, b - p) <= 0;
}

// Exact closed segment intersection between AB and CD
bool segments_intersect(const Point& a, const Point& b,
                        const Point& c, const Point& d) {
    int s1 = sgn(cross(a, b, c));
    int s2 = sgn(cross(a, b, d));
    int s3 = sgn(cross(c, d, a));
    int s4 = sgn(cross(c, d, b));

    // Proper intersection: C,D strictly on opposite sides of AB and vice versa
    if (s1 * s2 < 0 && s3 * s4 < 0) return true;

    // Collinear / endpoint touching cases
    if (s1 == 0 && on_segment(a, b, c)) return true;
    if (s2 == 0 && on_segment(a, b, d)) return true;
    if (s3 == 0 && on_segment(c, d, a)) return true;
    if (s4 == 0 && on_segment(c, d, b)) return true;
    return false;
}

// Returns 2 * Area of simple polygon P (always an exact integer!)
int64_t polygon_twice_area(const std::vector<Point>& poly) {
    int64_t sum = 0;
    const std::size_t n = poly.size();
    for (std::size_t i = 0; i < n; ++i) {
        sum += cross(poly[i], poly[(i + 1) % n]);
    }
    return sum < 0 ? -sum : sum;
}