Line Intersection
Reliable line and segment intersection tests built on orientation, with exact predicates and careful boundary handling.
Line Intersection
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
In contest geometry, line intersection usually means one of two things: deciding whether two segments intersect, or computing the actual crossing point of two non-parallel lines. The first task should stay exact whenever possible; the second often needs a carefully isolated floating-point step.
When to Use It
Use these routines when:
the problem asks whether paths, walls, rays, or polygon edges cross,
boundary contact counts as an intersection,
you need a robust primitive before moving on to polygon or sweep-line logic.
Core Idea
Two segments intersect if each segment straddles the line through the other, with collinear overlap handled separately. Orientation tests are enough for the discrete predicate.
For the actual crossing point of two non-parallel infinite lines, solve the linear equations of the two lines. That part can use floating-point arithmetic after the combinatorial case split is done.
Key Insight
Most bugs come from treating all cases the same. Proper intersections, touching endpoints, and collinear overlap should be separated mentally even if the final code merges them into one predicate.
Operations / Main Technique
orientation of endpoint triples,
on-segment checks for collinear cases,
one predicate for segment intersection,
one helper for the intersection point of non-parallel lines.
Worked example.
If the endpoints of segment \(ab\) lie on opposite sides of line \(cd\), and the endpoints of \(cd\) lie on opposite sides of line \(ab\), the segments cross properly. If one orientation is zero, it becomes a boundary-touch case.
Correctness Intuition
Orientation determines the side of a line. For a proper intersection, each segment's endpoints must lie on different sides of the other segment's supporting line. Collinear cases are not captured by side changes, so they are handled by explicit range overlap.
Complexity Analysis
All primitives here run in \(O(1)\) time and \(O(1)\) memory.
Implementation
The reference code gives:
segments_intersectwith inclusive boundary handling,line_intersectionfor two non-parallel infinite lines.That is the split I use most often in contests: exact predicate first, coordinate computation second.
Common Pitfalls
Forgetting that collinear overlap is still an intersection.
Using a floating-point epsilon for problems that can be solved exactly with integer predicates.
Not deciding whether touching at one endpoint should count.
Computing the intersection point before checking for parallel lines.
Variants / Extensions
Ray or half-line intersection.
Segment-polygon intersection.
Sweep-line event ordering, which still relies on the same primitives.
Practice Problems
Determine whether two segments intersect.
Count how many query segments intersect a polygon boundary.
Compute the crossing point of two non-parallel lines.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Point {
long long x;
long long y;
};
long long cross(Point a, Point b, Point c) {
long long x1 = b.x - a.x;
long long y1 = b.y - a.y;
long long x2 = c.x - a.x;
long long y2 = c.y - a.y;
return x1 * y2 - y1 * x2;
}
bool on_segment(Point a, Point b, Point p) {
if (cross(a, b, p) != 0) return false;
return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
bool segments_intersect(Point a, Point b, Point c, Point d) {
long long ab_c = cross(a, b, c);
long long ab_d = cross(a, b, d);
long long cd_a = cross(c, d, a);
long long cd_b = cross(c, d, b);
if ((ab_c == 0 && on_segment(a, b, c)) || (ab_d == 0 && on_segment(a, b, d)) ||
(cd_a == 0 && on_segment(c, d, a)) || (cd_b == 0 && on_segment(c, d, b))) {
return true;
}
return (ab_c > 0) != (ab_d > 0) && (cd_a > 0) != (cd_b > 0);
}
struct PointD {
long double x;
long double y;
};
PointD line_intersection(Point a, Point b, Point c, Point d) {
long double A1 = b.y - a.y;
long double B1 = a.x - b.x;
long double C1 = A1 * a.x + B1 * a.y;
long double A2 = d.y - c.y;
long double B2 = c.x - d.x;
long double C2 = A2 * c.x + B2 * c.y;
long double det = A1 * B2 - A2 * B1;
return {
(B2 * C1 - B1 * C2) / det,
(A1 * C2 - A2 * C1) / det,
};
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.