Segment intersection

The segment intersection test decides whether two segments share at least one point, using the signs of four cross products, with no division. It answers yes or no; to find the common point itself, use lines and segments.

Explanation

Two segments, AB and CD, cross like an X. Draw the whole line through A and B, as in Fig. 1, and walk from A to B. C is on your left: the cross product of the vectors from A to B and from A to C, (4, 2) and (1, 3), is 4 · 3 − 2 · 1 = 10, which is positive, a left turn. For D it is −6, a right turn. C and D are on different sides of the line, so CD has to pass through it.

Two crossing segments: black AB from A at the lower left to B at the upper right, and blue CD from C at the top to D at the bottom. The line through A and B continues past both ends as a grey dashed line, with C marked plus on its left side and D marked minus on its right side. The line through C and D continues as a lighter dashed line, with A marked minus and B marked plus.

Fig. 1. C and D are on different sides of the line through A and B, and A and B are on different sides of the line through C and D.

But a line goes on forever, and AB is only a piece of it, so CD could cross the line beyond B. Check the other way too: walking from C to D, A is on the right (−9) and B on the left (7). Both checks pass, so the segments cross. The test never finds where they cross, here (2.25, 1.125): finding that point takes division, and two segments on one line have no single crossing point at all.

Fig. 2 puts five more segments around a segment AB.

Segment AB rising from A to B, with its line continued as a dashed grey line; segment 1 crosses AB, segment 3 starts on AB, segment 2 crosses the dashed line beyond B, segment 4 is a light-blue band on the line overlapping AB from A, and segment 5 lies on the line past B with a gap after B.

Fig. 2. Segment AB and five more segments. Which of them share a point with AB?

Segment 1 passes both checks. The ends of segment 2 are on different sides of AB's line (9 and −12), but it cuts that line beyond B. Seen from the line of segment 2, A and B are on the same side (−26 and −5), so the segments miss.

Segments 3, 4 and 5 each have an end exactly on AB's line. The cross product for such a point is 0: it is on the line, on neither side. The rule "the ends are on different sides" has no answer for it.

Let a point on the line count for either side: accept a pair of ends unless both are on the left or both on the right. Segment 3 starts at (6, 3), on AB itself. Its ends give 0 and 15, and A and B give 10 and −5: accepted, and AB and segment 3 do touch. Segment 4 lies on AB's line and overlaps AB from (2, 1) to (4, 2); all four cross products are 0: accepted, and they do overlap.

Segment 5 also lies on AB's line, from (10, 5) to (12, 6). All four cross products are 0, so it is accepted too. But AB ends at (8, 4), and Fig. 2 shows a gap between B and segment 5: the segments have no common point.

All four cross products are 0 only when all four points lie on one line. Then "which side" means nothing, and the signs can't tell segment 4 from segment 5. The question becomes: do two pieces of one line overlap? AB covers x from 2 to 8, and segment 5 covers x from 10 to 12. The later start, 10, comes after the earlier end, 8, so there is a gap. Segment 4 covers x from 0 to 4: the later start, 2, comes before the earlier end, 4, so they overlap.

On a vertical line every x range is a single number, so compare the y ranges in the same way. Overlapping in both x and y means that the rectangles around the two segments overlap. Such a rectangle is the segment's bounding box, and comparing the two is the box check. If any cross product is not 0, the points are not on one line and the sides decide, as they did for segment 3.

This is the standard segment intersection test: two side checks, one for each segment, and the box check when all four cross products are 0.

Segment AB and five segments around it, tested one by one: the signs of each segment's ends against AB's line, the signs of A and B against the segment's line, then the verdict, with the x and y ranges compared for the two segments on AB's line.

Line AB, segment 1: segment 1 is blue, and the line through A and B is grey dashed. Walking from A to B, its end (3, 4) is on the left, cross product 15, marked +, and its end (5, 1) is on the right, −9, marked −. A point on the line will get a grey dot.

1/15

Fig. 3. Step through the test with the buttons or the arrow keys. Blue is the segment being tested; + and − mark the sides, and a grey dot marks a point on the line. Green marks a passing check or a shared point, red a failing check.

Each verdict took four cross products and, for segments 4 and 5, two range comparisons: a fixed amount of work, .

Implementation

The functions vec, cross and orient come from geometry basics. orient(a, b, c) also tells which side of the line through a and b the point c is on: 1 for the left of the walk from a to b, −1 for the right, 0 on the line. The ends of cd against the line through a and b give the orient values o1 = orient(a, b, c) and o2 = orient(a, b, d); the ends of ab against the line through c and d give o3 = orient(c, d, a) and o4 = orient(c, d, b).

The side check "different sides, or on the line" is o1 * o2 <= 0: the product of two orient values is −1 for different sides, 0 when a point is on the line, and 1 for the same side.

The ranges [l1, r1] and [l2, r2] overlap when max(l1, l2) <= min(r1, r2). A segment's ends can come in any order, so the helper overlap first puts each range in order.

The test for segments ab and cd:

  1. Orient values: compute o1, o2, o3, o4.

  2. Box check: if all four are 0, answer whether the x ranges overlap and the y ranges overlap.

  3. Side checks: otherwise, answer o1 * o2 <= 0 && o3 * o4 <= 0.

For segment 2, o1, o2 are 1, −1 and o3, o4 are −1, −1: o1 * o2 = -1 passes, but o3 * o4 = 1 fails, so the answer is NO. For segment 5 all four are 0, and the x ranges [2, 8] and [10, 12] don't overlap: NO.

A segment that is a single point, with a equal to b, needs no extra code: o3 and o4 decide, or all four orient values are 0 and the box check does.

The program reads eight integers x1 y1 x2 y2 x3 y3 x4 y4: the ends of the first segment, then the ends of the second, each at most 10^9 in absolute value. It prints YES if the segments share a point and NO otherwise. The test compares cross products with 0 exactly, so it needs integer coordinates; with double coordinates the comparison with 0 needs a tolerance. For AB and segment 5 the input is:

2 1 8 4 10 5 12 6
#include <algorithm>
#include <iostream>
using namespace std;

struct Point { long long x, y; };

Point vec(Point a, Point b) { return {b.x - a.x, b.y - a.y}; }   // vector from a to b
long long cross(Point u, Point v) { return u.x * v.y - u.y * v.x; }

// 1: a -> b -> c turns left, -1: turns right, 0: a, b, c on one line
int orient(Point a, Point b, Point c) {
    long long s = cross(vec(a, b), vec(a, c));
    if (s > 0) return 1;
    if (s < 0) return -1;
    return 0;
}

// do the ranges [l1, r1] and [l2, r2] share a number?
bool overlap(long long l1, long long r1, long long l2, long long r2) {
    if (l1 > r1) swap(l1, r1);
    if (l2 > r2) swap(l2, r2);
    return max(l1, l2) <= min(r1, r2);
}

// do the segments ab and cd share at least one point?
bool intersect(Point a, Point b, Point c, Point d) {
    // orient values
    int o1 = orient(a, b, c), o2 = orient(a, b, d);
    int o3 = orient(c, d, a), o4 = orient(c, d, b);

    // box check: all four points on one line
    if (o1 == 0 && o2 == 0 && o3 == 0 && o4 == 0)
        return overlap(a.x, b.x, c.x, d.x) && overlap(a.y, b.y, c.y, d.y);

    // side checks
    return o1 * o2 <= 0 && o3 * o4 <= 0;
}

int main() {
    Point a, b, c, d;
    cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
    cout << (intersect(a, b, c, d) ? "YES" : "NO") << '\n';
}

The test takes time and memory for one pair of segments. For segments, checking all pairs takes O(n^2).

Strict crossing

Some problems ask whether two segments cross, and touching does not count. Then the test is o1 * o2 < 0 && o3 * o4 < 0, with no box check, since segments on one line never cross.

Correctness proof

Suppose the four points are not all on one line, and A ≠ B, C ≠ D. If the lines through AB and CD are parallel, C and D are strictly on the same side of AB's line, and the test rightly says no.

Otherwise the lines meet in exactly one point . CD contains a point of AB's line exactly when C and D are not strictly on the same side of it, and that point can only be . In the same way, AB contains exactly when A and B are not strictly on the same side of CD's line. The segments share a point exactly when both contain , which is what the side checks test.

Segment AB in black and segment CD in blue, both continued as grey dashed lines; the lines meet at a grey point P on AB, but past D on CD's line, and C and D are both marked plus, on the same side of AB's line.

Fig. 4. C and D are on the same side of AB's line, so CD stops before P.

If all four points are on one line, the segments are two pieces of it, and they overlap exactly when their x ranges and their y ranges overlap: the box check.

If A = B, then o_1 and o_2 are 0 and o_3 = o_4. The test says yes only when o_3 = 0, that is, when A is on CD's line; then all four values are 0, and the box check tells whether A lies between C and D.

Common mistakes

  • Accepting a 0 on both pairs without the box check. (0, 0)–(1, 1) and (2, 2)–(3, 3) lie on one line with a gap, and the test says yes. Add the box check for four zeros.

  • Using strict signs, o1 * o2 < 0, which misses touching. (0, 0)–(2, 2) and (2, 2)–(4, 0) share an end, but the strict test says no. Use <= 0 unless touching does not count.

  • Comparing ranges without putting the ends in order. (8, 4)–(2, 1) and (4, 2)–(10, 5) lie on one line and overlap from (4, 2) to (8, 4), but unordered x ranges give max(8, 4) = 8 > min(2, 10) = 2, so the check says no. Swap first, as overlap does.

Similar algorithms

Lines and segments finds where two lines meet, whether a point lies on a segment, and the distance to a segment.

A sweep line answers "does any pair among segments intersect" for large , where all pairs at O(n^2) is too slow: it keeps the segments in order and runs this test only on neighbours.

Point in polygon counts how many sides of a polygon a ray from the point crosses: a segment test per side, with its own rules for vertices on the ray.

Practice

Was this page helpful?