AntInLoop

Line Segment Intersection

Line Segment Intersection tests whether two 2D segments AB and CD intersect in exact O(1) integer arithmetic using orientation (cross-product) signs and collinear bounding-box checks.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Line Segment Intersection

Testing whether two 2D line segments $AB$ and $CD$ intersect is a core building block of computational geometry, game physics, and Sweep Line algorithms. Using exact integer cross products avoids division-by-zero and floating-point epsilon bugs!

At a Glance

Two segments $AB$ and $CD$ intersect iff:

1. General case: orient(A, B, C) and orient(A, B, D) have opposite signs, AND orient(C, D, A) and orient(C, D, B) have opposite signs.

2. Collinear / Endpoint case: One endpoint lies on the other segment (orient == 0 and inside its bounding box).

---

Practice Problems

Easy

1. Exact Integer Segment Intersection Test

Determine in $O(1)$ exact integer arithmetic whether closed segments AB and CD intersect.

Approach: Compute the 4 orientation signs (-1, 0, +1) plus an onSegment bounding-box check for collinear endpoints. Time: $O(1)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>

struct Pt { long long x, y; };

int orient(const Pt& a, const Pt& b, const Pt& c) {
    long long v = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return (v > 0) - (v < 0);
}

bool onSegment(const Pt& a, const Pt& b, const Pt& p) {
    return orient(a, b, p) == 0 &&
           std::min(a.x, b.x) <= p.x && p.x <= std::max(a.x, b.x) &&
           std::min(a.y, b.y) <= p.y && p.y <= std::max(a.y, b.y);
}

bool segmentsIntersect(const Pt& a, const Pt& b, const Pt& c, const Pt& d) {
    int o1 = orient(a, b, c), o2 = orient(a, b, d);
    int o3 = orient(c, d, a), o4 = orient(c, d, b);
    if (o1 != o2 && o3 != o4) return true;
    return onSegment(a, b, c) || onSegment(a, b, d) || onSegment(c, d, a) || onSegment(c, d, b);
}

int main() {
    std::cout << std::boolalpha
              << segmentsIntersect({0, 0}, {4, 4}, {0, 4}, {4, 0}) << " "
              << segmentsIntersect({0, 0}, {2, 0}, {3, 0}, {5, 0}) << "\n"; // true false
    return 0;
}

</details>

---

Related Algorithms