ii. Lines and Segments

Line Intersection

Representations

Form	Good for
Two points $a,b$	input format, cross product tests
Point + direction $a+td$	parametric queries, sweeps
$Ax+By=C$	solving systems, half-planes

Converting from two points to the implicit form:
$A=b_y-a_y,B=a_x-b_x,C=A{a}_x+B{a}_y.$

This is $(A,B)=-\mathrm{perp}(b-a)$: the implicit form’s normal is the direction rotated $-90°$.

Intersecting two lines

Solve $A_{1}x+B_{1}y=C_1,A_{2}x+B_{2}y=C_2$ by Cramer’s rule with $D=A_1{B}_2-A_2{B}_1$:

bool lineIntersect(double A1, double B1, double C1, double A2, double B2, double C2, PD& out) {
    double D = A1 * B2 - A2 * B1;
    if (fabs(D) < 1e-9) return false;                // parallel or identical
    out.x = (C1 * B2 - C2 * B1) / D;
    out.y = (A1 * C2 - A2 * C1) / D;
    return true;
}

$D$ equals the cross product of the two direction vectors, so $D=0$ means parallel.

The vector form — usually cleaner

Line 1 through $a$ with direction $d_1=b-a$; line 2 through $c$ with direction $d_2=e-c$:
$t=\frac{\mathrm{cross}(c-a,d_2)}{\mathrm{cross}(d_1,d_2)},\text{intersection}=a+t{d}_1.$

bool lineInter(P a, P b, P c, P d, PD& out) {
    P u = b - a, v = d - c;
    ll den = cross(u, v);
    if (den == 0) return false;                      // parallel
    double t = (double)cross(c - a, v) / den;
    out = {a.x + u.x * t, a.y + u.y * t};
    return true;
}

den is exact in integers, so the parallel test is exact even though the intersection point is floating point. That separation — exact predicate, approximate construction — is the right pattern throughout geometry.

Proof: Cramer's rule, and $D=\mathrm{cross}(d_1,d_2)$

Cramer’s rule solves $\left(\begin{array}{cc}{A}_1& B_1\\ A_2& B_2\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}{C}_1\\ C_2\end{array}\right)$ by $x=\det \left(\begin{array}{cc}{C}_1& B_1\\ C_2& B_2\end{array}\right)/D$, $y=\det \left(\begin{array}{cc}{A}_1& C_1\\ A_2& C_2\end{array}\right)/D$ with $D$ the matrix determinant — direct substitution verifies both equations when $D\ne 0$. The vector-form derivation: at the intersection, $a+t{d}_1=c+s{d}_2$ for some $s$, so $t{d}_1-s{d}_2=c-a$; taking $\mathrm{cross}(\cdot ,d_2)$ of both sides eliminates $s$ (since $\mathrm{cross}(d_2,d_2)=0$), giving $t\cdot \mathrm{cross}(d_1,d_2)=\mathrm{cross}(c-a,d_2)$, i.e. the formula above.
For $D=\mathrm{cross}(d_1,d_2)$: writing $(A,B)=-\mathrm{perp}(d)$ for each line, $D=A_1{B}_2-A_2{B}_1=\mathrm{cross}((A_1,B_1),(A_2,B_2))=\mathrm{cross}(\mathrm{perp}(d_1),\mathrm{perp}(d_2))$ (the two minus signs cancel in a product of two cross-product arguments… more carefully, $\mathrm{cross}(-u,-v)=\mathrm{cross}(u,v)$). Since $\mathrm{perp}(u)=(-u_y,u_x)$, $\mathrm{cross}(\mathrm{perp}(u),\mathrm{perp}(v))=(-u_y)v_x-u_x(-v_y)=u_x{v}_y-u_y{v}_x=\mathrm{cross}(u,v)$ — rotating both vectors by the same $90°$ preserves their cross product. Hence $D=\mathrm{cross}(d_1,d_2)$. $■$

Parallel vs identical

// cross(u,v) == 0: parallel or identical.
// cross(u, c - a) == 0 too: c lies on line ab, so the lines are IDENTICAL; otherwise PARALLEL (disjoint).

Segment intersection is a different problem

Two lines almost always meet; two segments usually do not. After computing $t$ (and the corresponding $s$ on the other segment), require $t,s\in [0,1]$ — see below for the full case analysis including collinear overlap.

Related constructions

PD foot(P p, P a, P b) {                              // the perpendicular foot from p onto line ab
    double t = (double)dot(p - a, b - a) / norm2(b - a);
    return toPD(a) + toPD(b - a) * t;
}
PD midpoint(P a, P b) { return (toPD(a) + toPD(b)) * 0.5; }
P bisectorDir(P a, P b) { return perp(b - a); }        // direction of the perpendicular bisector of ab

Construction	Method
Circumcentre of a triangle	intersect two perpendicular bisectors (or the closed form)
Incentre	intersect two angle bisectors, or the weighted average $\frac{a\cdot A+b\cdot B+c\cdot C}{a+b+c}$
Orthocentre	intersect two altitudes (or $A+B+C-2O$)
Centroid	$\frac{A+B+C}{3}$
Reflection of $p$ across line $ab$	reflectAcross(p,a,b) from Primitives, $=2\cdot \mathrm{foot}(p,a,b)-p$
Angle bisector direction at $b$	normalise $(a-b)$ and $(c-b)$, then add

Numerical care

Nearly parallel lines

When $D$ is tiny but non-zero, the intersection point is enormous and its relative error is huge. If the algorithm then feeds that point into further computations, the error compounds badly. Mitigations: keep the exact cross for all decisions and only construct the point when it is genuinely needed; scale coordinates so they are comparable in magnitude; use long double.

Lines through many points

Detecting collinear triples among $n$ points: for each point, sort the others by direction around it and group equal directions — $O(n^2\log n)$. Canonicalise each direction by dividing by the gcd and fixing the sign, so (2,4) and (-1,-2) compare equal:

pair<ll,ll> canonicalDir(P d) {
    ll g = __gcd(llabs(d.x), llabs(d.y));
    if (g) { d.x /= g; d.y /= g; }
    if (d.x < 0 || (d.x == 0 && d.y < 0)) { d.x = -d.x; d.y = -d.y; }
    return {d.x, d.y};
}

Segment Intersection

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

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
 
    if (o1 == 0 && onSegment(c, a, b)) return true;   // collinear / touching cases
    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;
}

(onSegment, orient: Primitives.) 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, from Primitives) when touching should not count.

Proof: segmentsIntersect is correct

The strict-crossing case o1≠o2 && o3≠o4 is `properIntersect`, proved there. It remains to handle the case where at least one $o_i=0$, i.e. one segment has an endpoint collinear with the other segment’s line — ruling out a transversal crossing but not a touch or overlap.

If $o_1=0$: $c$ is collinear with line $ab$. The two segments meet somewhere iff that meeting point is $c$ itself (since $c$ is on line $ab$, the only way segment $cd$ can touch segment $ab$ through its collinear endpoint $c$ is if $c$ itself lies on segment $ab$ — any other point of $cd$ is off the line, hence off segment $ab$ too, unless $cd$ is also collinear with $ab$, which is exactly the case where $o_1=o_2=0$ and the check for $c$ is symmetric with the check for $d$). So the test is precisely onSegment(c,a,b). Symmetric reasoning covers $o_2=0$ (endpoint $d$), $o_3=0$ (endpoint $a$ on line $cd$) and $o_4=0$ (endpoint $b$).

These four checks cover every way the two segments can meet without a strict crossing: a shared or absorbed endpoint, or collinear overlap (where at least one endpoint of one segment lies within the other, which is guaranteed whenever two collinear segments overlap at all — if neither endpoint of $cd$ lay in $[a,b]$ and neither endpoint of $ab$ lay in $[c,d]$, the two collinear segments would be disjoint). Conversely, if any check succeeds, that point is a shared point of both segments by onSegment’s own correctness. $■$

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 toPD(a) + toPD(u) * t;
}

This is exactly lineInter above. 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 of parameters.

Exact rational intersection

When the point must be exact (to compare with others, or to deduplicate), keep the same $t$ as a fraction instead of evaluating it:
$x=a_x+\frac{\mathrm{cross}(c-a,v)}{\mathrm{cross}(u,v)}{u}_x,$
storing numerator $\mathrm{cross}(c-a,v)\cdot u_x+a_x\cdot \mathrm{cross}(u,v)$ and denominator $\mathrm{cross}(u,v)$ separately and reducing by their gcd. Avoids all floating-point comparison problems, at the cost of __int128 (the numerator is a product of three $O({\text{coord}}^2)$ terms) 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. The general sweeps are covered in Sweep Line.

Axis-parallel special case

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

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

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

Proof: the axis-parallel sweep counts correctly

A horizontal segment $H$ and vertical segment $V$ cross iff $V$‘s $x$-coordinate lies in $H$‘s $x$-range and $H$‘s $y$-coordinate lies in $V$‘s $y$-range. Processing events left to right by $x$ (with activations before deactivations at equal $x$, or exactly matching the half-open convention the problem wants for touching endpoints), $H$ is “active” (its $y$ is in the Fenwick) exactly while the sweep $x$ is inside $H$‘s $x$-range. So when the sweep reaches each vertical segment $V$, querying the Fenwick for active $y$‘s in $V$‘s $y$-range counts exactly the horizontal segments currently spanning $V$‘s $x$ with $y$ in range — precisely the horizontals crossing $V$. Summing over all verticals counts every crossing pair once. $■$

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;
}

Proof: the half-open $y$-range is necessary and sufficient

The ray is $\{(x,p.y):x>p.x\}$ (rightward from $p$). An edge $ab$ with $a.y\le b.y$ after the swap can only meet this ray’s height if $a.y\le p.y\le b.y$; the function instead uses $a.y<p.y\le b.y$ (half-open on the low end, inclusive on the high end). This specific choice makes every lattice $y$-value that is exactly a vertex’s $y$-coordinate belong to exactly one of the two edges meeting at that vertex (the edge going up includes it as its top, the edge going down excludes it as its bottom, or vice versa under the swap normalization) — so a ray passing exactly through a vertex is counted once, not zero or two times, regardless of which of the two incident edges “owns” that height. Any other convention (both inclusive, both exclusive, or the complementary half-open choice) either double-counts or misses rays through vertices. Given the height is in range, orient(a,b,p) > 0 (with $a$ below $b$) tests that $p$ is to the right of the edge, i.e. that the ray going right from $p$ actually meets the edge rather than passing behind it — exactly the cross product sign for ”$p$ is clockwise of (below-right of) the upward edge $ab$”. $■$