Line Segment Intersection

The Two-Segment Problem

Input: Two line segments $p_1 p_2$ and $p_3 p_4$ (four endpoints, given as coordinates).

Output: true if they intersect, false otherwise.

The Straddle Test

Two segments intersect if and only if each segment straddles the line containing the other — or an endpoint of one lies on the other segment.

For segment $p_1 p_2$ to straddle the line through $p_3 p_4$, the endpoints $p_1$ and $p_2$ must lie on opposite sides of the infinite line through $p_3 p_4$ (or one endpoint lies exactly on that line).

Define the direction of $p_i$ with respect to segment $p_j p_k$:

$\text{DIRECTION}(p_j, p_k, p_i) = (p_i - p_j) \times (p_k - p_j)$

This is the orientation test with $p_j$ as origin.

Algorithm

SEGMENTS-INTERSECT(p1, p2, p3, p4):
    d1 = DIRECTION(p3, p4, p1)
    d2 = DIRECTION(p3, p4, p2)
    d3 = DIRECTION(p1, p2, p3)
    d4 = DIRECTION(p1, p2, p4)

    // Both segments straddle each other's line
    if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and
       ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
        return true

    // Check collinear cases: endpoint lies on the other segment
    if d1 == 0 and ON-SEGMENT(p3, p4, p1): return true
    if d2 == 0 and ON-SEGMENT(p3, p4, p2): return true
    if d3 == 0 and ON-SEGMENT(p1, p2, p3): return true
    if d4 == 0 and ON-SEGMENT(p1, p2, p4): return true

    return false

ON-SEGMENT(pi, pj, pk):
    return (min(xi, xj) <= xk <= max(xi, xj)) and
           (min(yi, yj) <= yk <= max(yi, yj))

ON-SEGMENT checks that the collinear point actually falls within the segment bounds (not just on the infinite line).

Worked Example

Segments: $p_1 = (0,0)$, $p_2 = (4,4)$, $p_3 = (0,4)$, $p_4 = (4,0)$.

Compute the four directions:

$d_1 = \text{DIRECTION}(p_3, p_4, p_1) = (0-0)(0-4) - (0-4)(4-0) = 0 \cdot (-4) - (-4) \cdot 4 = 16 > 0$

$d_2 = \text{DIRECTION}(p_3, p_4, p_2) = (4-0)(0-4) - (4-4)(4-0) = 4 \cdot (-4) - 0 \cdot 4 = -16 < 0$

$d_1 > 0$ and $d_2 < 0$, so $p_1 p_2$ straddles the line of $p_3 p_4$. Check the other pair:

$d_3 = \text{DIRECTION}(p_1, p_2, p_3) = (0-0)(4-0) - (4-0)(4-0) = 0 \cdot 4 - 4 \cdot 4 = -16 < 0$

$d_4 = \text{DIRECTION}(p_1, p_2, p_4) = (4-0)(4-0) - (0-0)(4-0) = 4 \cdot 4 - 0 \cdot 4 = 16 > 0$

$d_3 < 0$ and $d_4 > 0$, so $p_3 p_4$ straddles the line of $p_1 p_2$. Both conditions met → intersection at $(2,2)$. Correct.

The n-Segment Intersection Problem

Input: $n$ line segments.

Output: true if any pair intersects; false otherwise.

Naive: $\Theta(n^2)$

Check all $\binom{n}{2}$ pairs. Impractical for large $n$.

Sweep-Line Algorithm: $O((n+k)\log n)$

Where $k$ is the number of intersections reported.

The idea: sweep a vertical line from left to right across the plane. Maintain two data structures:

1. Event queue (priority queue): endpoints sorted by $x$-coordinate, plus intersection points discovered during the sweep.
2. Sweep-line status (balanced BST): segments currently intersecting the sweep line, ordered by their $y$-coordinate at the sweep line’s position.

When the sweep line reaches:

• Left endpoint: insert segment into the BST; check the segment above and below for intersection.
• Right endpoint: remove segment from the BST; check the newly adjacent segments for intersection.
• Intersection point: swap the two intersecting segments in the BST and check their new neighbours.

Key insight: segments can only intersect if they become adjacent in the sweep-line ordering at some point. The BST ensures we only check $O(n+k)$ pairs rather than $\Theta(n^2)$.

Special Cases

• Vertical segments: handled by the event queue ordering.
• Multiple segments sharing an endpoint: careful tie-breaking in the comparison.
• Collinear overlapping segments: detect and merge or report.

Summary

Problem	Algorithm	Time
Two segments	Straddle test (4 cross products)	$O(1)$
$n$ segments (any pair)	Naive all-pairs	$\Theta(n^2)$
$n$ segments (any pair)	Sweep-line	$O((n+k)\log n)$
Cross product use	Orientation test, no division	Exact for integer coords

Exam Note: You may be asked to trace the straddle test on a specific pair of segments, or to explain the sweep-line approach. Tripos questions on geometry are new for 25/26; expect ~bookwork plus small tracing.