Segment Intersection

Do segments $ab$ and $cd$ intersect? The exact-integer answer uses four orientation tests plus a collinear case.

The test

bool onSegment(P p, P a, P b) {                      // assumes p is collinear with a,b
    return dot(p - a, p - b) <= 0;
}
 
bool segmentsIntersect(P a, P b, P c, P 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;           // proper crossing
 
    // collinear / touching cases
    if (o1 == 0 && onSegment(c, a, b)) return true;
    if (o2 == 0 && onSegment(d, a, b)) return true;
    if (o3 == 0 && onSegment(a, c, d)) return true;
    if (o4 == 0 && onSegment(b, c, d)) return true;
    return false;
}

Proper crossing: $c$ and $d$ are on opposite sides of line $ab$, and $a$ and $b$ are on opposite sides of line $cd$. Both conditions are needed — either alone is insufficient.

Everything here is exact integer arithmetic.

The degenerate cases

Case	Handled by
Segments cross properly	o1 != o2 && o3 != o4
An endpoint lies on the other segment	the collinear checks
Segments are collinear and overlap	the collinear checks
Segments are collinear and disjoint	all checks fail — correct
A segment is a single point	onSegment still works
Segments share exactly one endpoint	reported as intersecting

Decide what "touching" means

Many problems distinguish “properly cross” from “merely touch at an endpoint”. Read the statement and use properIntersect (the first condition only) when touching should not count.

The intersection point

// assumes they intersect and are not parallel
PD intersectionPoint(P a, P b, P c, P d) {
    P u = b - a, v = d - c;
    double t = (double)cross(c - a, v) / cross(u, v);
    return {a.x + u.x * t, a.y + u.y * t};
}

For the collinear overlap case there is no single point — the intersection is a sub-segment. Compute it by projecting all four endpoints onto the common direction and taking the overlapping interval.

Exact rational intersection

When the point must be exact (to compare with others, or to deduplicate), keep it as a fraction:

$x=\frac{\mathrm{cross}(c-a,v)\cdot u_x+a_x\mathrm{cross}(u,v)}{\mathrm{cross}(u,v)},$

storing numerator and denominator separately and reducing by the gcd. Avoids all floating-point comparison problems, at the cost of __int128 and some care.

Any-intersection among $n$ segments

Question	Method	Time
Do any two of $n$ segments intersect?	Shamos-Hoey sweep	$O(n\log n)$
Report all $k$ intersections	Bentley-Ottmann	$O((n+k)\log n)$
Count intersections only	sweep + BIT for special cases (axis-parallel)	$O(n\log n)$
Brute force	all pairs	$O(n^2)$

For $n\le 2000$, the $O(n^2)$ loop is 4 million exact integer tests — fast, simple, and unhackable. Reach for a sweep only when $n$ is large.

Axis-parallel special case

When all segments are horizontal or vertical, counting intersections is a classic sweep + BIT problem:

1. Sweep $x$ from left to right.
2. A horizontal segment starting → activate its $y$; ending → deactivate.
3. A vertical segment at this $x$ spanning $[y_1,y_2]$ → query how many active $y$ lie in that range.

$O(n\log n)$, exact, and much simpler than the general Bentley-Ottmann.

Ray-segment and ray-polygon

For point-in-polygon by ray casting, you need “does a horizontal ray from $p$ cross this edge”. The standard robust form avoids computing intersection points entirely:

bool crosses(P p, P a, P b) {
    if (a.y > b.y) swap(a, b);
    if (p.y <= a.y || p.y > b.y) return false;       // half-open: counts each vertex once
    return orient(a, b, p) > 0;
}

The half-open $y$-range is what makes vertices and horizontal edges work correctly — the single most common source of bugs in point-in-polygon code.

See also: Line Intersection · Orientation Test · Sweep Line