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
- Sweep Line — detects intersections among $n$ segments in $O(n \log n)$.
- Point in Polygon — uses ray-segment intersection.