Line and segment intersection

Why this matters when you build with AI

Ask an AI tool for a segment intersection function and it often writes a test with cross products that looks right and passes the first sample. The usual gap is the special cases. The function returns "no intersection" when two segments share only an endpoint, when one endpoint touches the other segment, or when two segments lie on the same line and overlap. Those inputs are common in judge data, because test writers place points on grid lines on purpose.

The second gap is the intersection point. A tool will compute it with double division, print a value such as 1.9999999999, and then compare that value with an integer. A robust program keeps the answer as an exact fraction until the very end.

This lesson gives one routine that handles every case, shows how it was tested against an exact brute-force program, and lists the failures a buggy version produces. Two terms first. A segment is the part of a line between two endpoints, including both endpoints. A brute force is a slow and simple program that is trusted to be correct, used as the reference for a fast one.

The idea: how to write a line

There are three common ways to write a line, and they matter for different tasks.

The point and direction form says a line passes through a point p and goes along a vector d. Every point on the line is p + t * d for some number t. This is the form used for segments in this lesson: the segment from a to b is a + t * (b - a) for t from 0 to 1.

The implicit form is a * x + b * y = c, with integers a, b and c. For a line through (x1, y1) and (x2, y2), take a = y2 - y1, b = x1 - x2 and c = a * x1 + b * y1. Worked example: the line through (0, 0) and (4, 4) has a = 4, b = -4, c = 0, so the line is 4x - 4y = 0. Check the second point: 4 * 4 - 4 * 4 = 0. The implicit form is useful for intersecting two lines with Cramer's rule, but it throws away which side of the line a point is on, and the segment test needs that side. So this lesson uses the point and direction form for the test.

The third form is the slope, y = m * x + k. Avoid it in contest code. A vertical line has no slope, and the slope is a fraction that rounds when stored as a double.

Two lines that are not parallel meet in exactly one point. Two segments meet only if that point lies on both segments. So the work is in two parts: find the point, then check the parameters t and u lie between 0 and 1. The sign test below does the second part without computing the point at all.

The segment test with signs only

Write orient(a, b, c) for the sign of cross(b - a, c - a), as in the orientation lesson. Segments ab and cd can meet in four kinds of ways.

Proper crossing. The endpoints of each segment are on opposite sides of the other segment's line. In signs: orient(a, b, c) and orient(a, b, d) are opposite and not zero, and orient(c, d, a) and orient(c, d, b) are opposite and not zero.
Touching. One endpoint lies on the other segment. Then one orientation is zero, and that point is inside the bounding box of the other segment. The T shape, where one segment ends on the middle of the other, is a touching case.
Collinear. All four points lie on one line. Every orientation is zero. The segments may overlap in a stretch, touch at one endpoint, or not meet at all. A bounding box check on each axis separates these cases.
Degenerate. One segment has zero length, so it is a single point. Its orientation with any other point on its own "line" is zero, so the first test alone is not enough. A point is on a segment only if it is on the line and inside the bounding box.

The standard rule covers all four. Segments ab and cd meet if and only if:

the bounding boxes overlap on both the x axis and the y axis, and
orient(a, b, c) * orient(a, b, d) <= 0, and
orient(c, d, a) * orient(c, d, b) <= 0.

Each sign is -1, 0 or 1, so each product is one of those three values and cannot overflow. The first condition handles the collinear case, where the sign products are all zero and only the boxes decide. The bounding box condition is also what rules out a point that lies on the extended line of a segment but outside the segment.

Worked example by hand: ab is (0, 0) to (4, 0), and cd is (4, 0) to (6, 3). The boxes overlap at (4, 0). For the first pair, orient(a, b, c) with c = (4, 0) uses the vector c - a = (4, 0), and cross((4, 0), (4, 0)) = 0, so the product is 0. For the second pair, orient(c, d, a) uses d - c = (2, 3) and a - c = (-4, 0): cross((2, 3), (-4, 0)) = 2 * 0 - 3 * (-4) = 12. Then orient(c, d, b) uses b - c = (0, 0), so its cross product is 0, and the product is 0. Both products are at most 0 and the boxes overlap, so the segments meet. The only shared point is (4, 0), an endpoint of both.

Computing the intersection point as an exact fraction

When the two lines are not parallel, the point is a + t * r, where r = b - a, s = d - c, q = c - a, and

t = cross(q, s) / cross(r, s)

The denominator den = cross(r, s) is not zero for non-parallel lines. Multiply through by den so the point is (xn / den, yn / den) with integers:

xn = a.x * den + tn * r.x yn = a.y * den + tn * r.y where tn = cross(q, s)

Before printing, make den positive by negating xn, yn and den if needed, then divide all three by their greatest common divisor. The result is a unique reduced fraction, so two programs that agree on the fractions agree on the point.

Worked example: a = (0, 0), b = (4, 4), c = (0, 4), d = (4, 0). Then r = (4, 4), s = (4, -4), q = (0, 4). den = 4 * (-4) - 4 * 4 = -32. tn = 0 * (-4) - 4 * 4 = -16. So t = -16 / -32 = 1/2. Next, xn = 0 * (-32) + (-16) * 4 = -64 and yn = 0 * (-32) + (-16) * 4 = -64. Flip the signs because den is negative: xn = 64, yn = 64, den = 32. The gcd of 64, 64 and 32 is 32, so the point is 2 / 1 and 2 / 1, which is (2, 2). The reference program prints this as POINT 2 2 1.

Why __int128. The denominator is a product of two differences, so with coordinates up to 10^9 each difference is at most 2 * 10^9, and den can reach 8 * 10^18. That fits in a signed 64-bit integer, which holds up to about 9.2 * 10^18. The numerator multiplies that by a coordinate, which reaches about 8 * 10^27. That does not fit. The program below keeps the numerator in __int128, a 128-bit integer type that GCC and Clang provide. It holds up to about 1.7 * 10^38, enough for this case.

The demo below uses the segments (-10^9, -999999997) to (10^9, 999999999) and (-999999994, 999999998) to (10^9, -999999997). It is a 20-line program that prints the values, and its output is real:

k=3 den=-7999999970000000024 tn=-3999999990000000000
exact xn (as __int128 digits, high/low): does not fit in 64 bits
64-bit result: 8446744097709551616
exact result, low 64 bits shown only when it fits: n/a
xn/den as a real number: 1.250000

The true x coordinate is 1.25. The 64-bit numerator is a wrong number, and dividing it by the denominator does not give 1.25. A program that uses long long for the numerator prints a wrong point with no error message.

The reference routine

The code below is the routine the lesson uses. It is C++17. The file was compiled with g++ -O2 -std=c++17 -Wall -Wextra, with no warnings, and its output on the sample is shown in the next section.

// seg.cpp: exact segment intersection with integer coordinates.
// Input: T, then T lines "x1 y1 x2 y2 x3 y3 x4 y4" (segment ab and segment cd).
// Output per line: NO | POINT xn yn d (point = (xn/d, yn/d), d > 0, reduced) | OVERLAP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
 
struct P { ll x, y; };
 
bool lexLess(P a, P b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
bool samePoint(P a, P b) { return a.x == b.x && a.y == b.y; }
P lexMin(P a, P b) { return lexLess(b, a) ? b : a; }
P lexMax(P a, P b) { return lexLess(a, b) ? b : a; }
 
// Sign of cross(b - a, c - a): +1 left turn, -1 right turn, 0 collinear.
int orient(P a, P b, P c) {
    ll ux = b.x - a.x, uy = b.y - a.y, vx = c.x - a.x, vy = c.y - a.y;
    ll cr = ux * vy - uy * vx;          // fits in ll when |coordinates| <= 1e9
    return (cr > 0) - (cr < 0);
}
 
// Do the closed intervals [a1, b1] and [a2, b2] share a point?
bool overlap1(ll a1, ll b1, ll a2, ll b2) {
    return max(min(a1, b1), min(a2, b2)) <= min(max(a1, b1), max(a2, b2));
}
 
// Do closed segments ab and cd share at least one point?
bool intersects(P a, P b, P c, P d) {
    if (!overlap1(a.x, b.x, c.x, d.x) || !overlap1(a.y, b.y, c.y, d.y)) return false;
    return orient(a, b, c) * orient(a, b, d) <= 0 && orient(c, d, a) * orient(c, d, b) <= 0;
}
 
// All four points on one line. The extra two tests matter when a segment is a single point.
bool allCollinear(P a, P b, P c, P d) {
    return orient(a, b, c) == 0 && orient(a, b, d) == 0 && orient(c, d, a) == 0 && orient(c, d, b) == 0;
}
 
i128 gcd128(i128 a, i128 b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) { i128 t = a % b; a = b; b = t; }
    return a;
}
 
string toStr(i128 v) {
    if (v == 0) return "0";
    bool neg = v < 0;
    if (neg) v = -v;
    string s;
    while (v > 0) { s += char('0' + (int)(v % 10)); v /= 10; }
    if (neg) s += '-';
    reverse(s.begin(), s.end());
    return s;
}
 
// Intersection point of two non-parallel lines through the segments, as an exact fraction.
void printPoint(P a, P b, P c, P d) {
    ll rx = b.x - a.x, ry = b.y - a.y;
    ll sx = d.x - c.x, sy = d.y - c.y;
    ll qx = c.x - a.x, qy = c.y - a.y;
    ll den = rx * sy - ry * sx;          // cross(r, s), up to 8e18: fits in ll
    ll tn = qx * sy - qy * sx;           // point = a + (tn / den) * r
    i128 xn = (i128)a.x * den + (i128)tn * rx;   // up to ~3e28: needs __int128
    i128 yn = (i128)a.y * den + (i128)tn * ry;
    i128 d2 = den;
    if (d2 < 0) { xn = -xn; yn = -yn; d2 = -d2; }
    i128 g = gcd128(gcd128(xn, yn), d2);
    if (g != 0) { xn /= g; yn /= g; d2 /= g; }
    cout << "POINT " << toStr(xn) << " " << toStr(yn) << " " << toStr(d2) << "\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll v[8];
        for (ll& x : v) cin >> x;
        P a{v[0], v[1]}, b{v[2], v[3]}, c{v[4], v[5]}, d{v[6], v[7]};
        if (!intersects(a, b, c, d)) {
            cout << "NO\n";
        } else if (allCollinear(a, b, c, d)) {
            P lo = lexMax(lexMin(a, b), lexMin(c, d));
            P hi = lexMin(lexMax(a, b), lexMax(c, d));
            if (samePoint(lo, hi)) cout << "POINT " << lo.x << " " << lo.y << " 1\n";
            else cout << "OVERLAP\n";
        } else {
            printPoint(a, b, c, d);
        }
    }
    return 0;
}

The program reads T and then T lines of eight integers. It prints NO, OVERLAP, or POINT xn yn d. The POINT output is a reduced fraction with a positive denominator. For a collinear touching point the program prints POINT x y 1.

Worked example: fence crossings

Statement, written for this lesson. A farm has T pairs of fences. Each fence is a closed segment with integer endpoints. For each pair, print NO if the fences share no point, OVERLAP if they share a stretch of more than one point, and POINT xn yn d for the single point they share, as a reduced fraction. Limits: 1 <= T <= 100000 and each coordinate has absolute value at most 10^9.

Sample input, with the output from the reference program:

8
0 0 4 4 0 4 4 0
0 0 2 0 2 0 4 0
0 0 4 0 2 0 6 0
0 0 2 0 2 1 4 1
0 0 3 1 0 1 3 0
1 1 1 1 0 0 2 2
0 0 0 0 1 1 2 2
0 0 2 2 0 2 2 0

POINT 2 2 1
POINT 2 0 1
OVERLAP
NO
POINT 3 1 2
POINT 1 1 1
NO
POINT 1 1 1

Read the output case by case. Case 1 is a proper crossing at (2, 2). Case 2 is two collinear fences that touch at (2, 0). Case 3 is two collinear fences that overlap on the stretch from (2, 0) to (4, 0). Case 4 is parallel and separate. Case 5 crosses at (3/2, 1/2), printed as 3 1 2. Case 6 is a single point, (1, 1), that lies on the fence (0, 0) to (2, 2). Case 7 is a point that is not on its fence. Case 8 is a crossing at (1, 1).

How this was tested

The checker is a separate Python program. It does not use cross products. For each pair it solves the parametric equations a + t * r = c + u * s with Fraction numbers, which are exact rationals in Python, and checks that t and u are between 0 and 1. For parallel lines it projects the points onto one axis. For a segment of zero length it checks whether the point is on the other segment with an exact test. The two methods share no code.

The test ran 23,000 random pairs. 20,000 had coordinates from -3 to 3, which gives many touching and collinear cases. 3,000 had coordinates from -10^9 to 10^9, which exercises the big numerators. The reference program agreed with the brute force on every case: 0 mismatches. The brute force found 16,245 NO, 6,666 POINT and 89 OVERLAP answers among the small cases and the large ones together.

The test is not a proof. Random cases cover only the situations they happen to hit. The case analysis above is the argument, and the test checks it.

Complexity

Each pair takes constant time: a fixed number of cross products and bounding box checks, and at most one gcd on numbers of about 128 bits. For T pairs the total time is O(T * log C), where C is the largest coordinate, because the gcd takes about log C steps. Memory is constant.

Common mistakes

Mistake 1: testing only proper crossings. The test orient(a, b, c) * orient(a, b, d) < 0 and the same for the other pair misses every touching and collinear case. A buggy version of the routine, with only that test, was run on the sample. Its output differs from the reference on three cases:

case 2 (touching at an endpoint): NO, expected POINT 2 0 1
case 3 (collinear overlap):       NO, expected OVERLAP
case 6 (point on a segment):      NO, expected POINT 1 1 1

Mistake 2: forgetting the bounding box. Without it, the collinear case lets through segments that do not meet. The variant below is the reference with the box check removed, run on three inputs:

input:  (0,0)-(1,0) and (5,0)-(6,0)   collinear, far apart
output: OVERLAP   expected NO
input:  (0,0)-(1,1) and (3,0)-(4,0)   no common point
output: NO        expected NO
input:  (0,0)-(4,4) and (1,2)-(5,2)   crossing at (2,2)
output: POINT 2 2 1   expected POINT 2 2 1

The first line is the failure. The collinear branch prints OVERLAP whenever its two sorted endpoints differ, and it never checks that the range is empty. The bounding box test is what rejects these inputs before that branch runs.

Mistake 3: computing the point in double and comparing it with integers. A double result can be a little off from the exact value, so a test for equality with 2 can fail. Keep the fraction.

Mistake 4: a denominator that is negative or unreduced. The checker compares fractions, so -6 / -3 and 2 / 1 must print as the same value. The routine makes den positive and divides by the gcd.

Mistake 5: long long for the numerator. The demo above shows a wrong number from a plausible input. The symptom is a point far from the true one, with no error message.

Mistake 6: a degenerate segment treated as a line. A segment (1, 1) to (1, 1) has no direction, so cross(b - a, s) is zero and the division by den is zero. The collinear branch must run first, because dividing by the zero den is undefined behavior in C++. The reference checks all four orientations before it divides.

Checklist to keep

Write each segment as two endpoints, and keep the four orientation signs as integers.
Check the bounding boxes on both axes before the sign products.
Treat all four points on one line as the collinear case, and sort the endpoints lexicographically to find the overlap.
Compute the point only when the lines are not parallel, and keep it as xn / den and yn / den.
Make the denominator positive and divide by the gcd.
Use __int128 for the numerator when coordinates are near 10^9.
Test against a brute force that uses exact fractions and a different method.
Include a zero-length segment in the random tests.

Hands-on exercise

Write the routine on your own machine, in C++17, from the description above, without copying the reference. Compile with g++ -O2 -std=c++17 -Wall -Wextra. Then write a Python brute force that uses Fraction, and a generator with a fixed seed that produces 20,000 small cases (coordinates from -3 to 3) and 3,000 large cases (coordinates from -10^9 to 10^9). Run both on the same input and print the number of mismatches. Aim for 0. If you get a mismatch, print the first five cases and find out which kind of case they are.

Then reproduce the failure. Make a copy of your routine with the bounding box check removed, and run it on the sample of the worked example. Record which lines change.

Prompt to try with an AI tool

Use this prompt, then check the answer with the steps above:

Write a C++17 function that tests whether two closed segments with integer
endpoints (coordinates up to 1e9 in absolute value) share at least one point.
It must handle proper crossings, endpoints touching, a point lying in the middle
of the other segment, collinear overlap, and zero-length segments. Use only
integer arithmetic, no double. Then give three input cases where a simpler
test that checks only proper crossings gives the wrong answer, with the expected
answer for each.

A good answer uses the four sign products together with the bounding box check, or an equivalent that covers collinear and degenerate cases. Its three counterexamples should be touching cases, collinear overlap, and a point on a segment. Check the claim by running the function on the three cases and on a small random set compared with a brute force. Reject an answer that uses a tolerance, or one that drops the bounding box check, or one that handles collinear segments by returning true without looking at overlap.

Summary

Two segments meet when their bounding boxes overlap and the endpoints of each lie on opposite sides of the other, with zero allowed. The collinear and degenerate cases fall out of the same rule once the bounding box is checked. An intersection point is a fraction with an integer numerator and denominator, and the numerator needs 128-bit integers when coordinates are near 10^9. The test that makes this trustworthy is an exact brute force that uses a different method.

Practice

These take a few minutes each. Try them on paper or in your scratch folder before you open the answers.

Practice 1: touching at an endpoint

Decide whether the segments (0, 0) to (4, 0) and (4, 0) to (6, 3) meet, and if they do, give the point.

Hint: Check the bounding boxes first. Then find the point where the two endpoints coincide.

Show the answer

They meet at (4, 0), which is an endpoint of both. The reference program prints POINT 4 0 1 for this input. A proper-crossing-only test would print NO.

Practice 2: intersection as a fraction

Find the intersection point of the segments (0, 0) to (3, 1) and (0, 2) to (3, 0), and write it as POINT xn yn d.

Hint: On the first segment the points are (3t, t). On the second they are (3u, 2 - 2u). Set the two equal and solve for t.

Show the answer

Setting 3t = 3u and t = 2 - 2u gives u = t and t = 2 - 2t, so t = 2/3. The point is (2, 2/3). Written with denominator 3, that is POINT 6 2 3. The reference program prints the same.

Practice 3: overlap or a single point

Two collinear segments are (0, 0) to (4, 0) and (1, 0) to (3, 0). Then take (0, 0) to (2, 0) and (2, 0) to (5, 0). Say what each pair shares.

Hint: Sort the endpoints along the line. The shared stretch runs from the larger of the two left endpoints to the smaller of the two right endpoints.

Show the answer

The first pair shares the stretch from (1, 0) to (3, 0), so the output is OVERLAP. The second pair shares only (2, 0), so the output is POINT 2 0 1. The reference program prints these two lines in that order.

Practice 4: a zero-length segment

Decide whether the point (1, 1) lies on the segment (0, 0) to (2, 2), and check what the program prints for the input 1 1 1 1 0 0 2 2.

Hint: A zero-length segment is one point. Check the point against the other segment with the cross product and the bounding box.

Show the answer

The point is on the segment, since the line y = x passes through (1, 1) and the point is between the endpoints. The program prints POINT 1 1 1. The degenerate case must be checked against both segments' orientations, as the reference does, before any division.

Practice 5: the size of the numbers

With coordinates between -10^9 and 10^9, what is the largest possible value of den = cross(r, s), and does it fit in a signed 64-bit integer? Then do the same for the numerator a.x * den.

Hint: Each difference of coordinates is at most 2 * 10^9. Each cross product has two products and one subtraction.

Show the answer

Each component of r and s is at most 2 * 10^9 in absolute value. So each product is at most 4 * 10^18, and den is at most 8 * 10^18 in absolute value. The signed 64-bit limit is about 9.2 * 10^18, so den fits. The numerator a.x * den is about 10^9 * 8 * 10^18 = 8 * 10^27, which does not fit, so it needs __int128.

Sources

Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd edition, Springer, 2008 (DOI 10.1007/978-3-540-77974-2). It is a standard textbook reference for this geometry. The routine and the tester in this lesson are its own.