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.$

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) < EPS) return false;                 // parallel or identical
    out.x = (C1 * B2 - C2 * B1) / D;
    out.y = (A1 * C2 - A2 * C1) / D;
    return true;
}

$D$ is exactly 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;
    long long 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.

Parallel vs identical

if (cross(u, v) == 0) {
    if (cross(u, c - a) == 0) return IDENTICAL;      // c lies on line ab
    else                      return PARALLEL;
}

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 Segment Intersection for the full case analysis including collinear overlap.

Related constructions

// perpendicular from p to line ab (the foot)
PD foot(P p, P a, P b) {
    double t = (double)dot(p - a, b - a) / norm2(b - a);
    return {a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t};
}
 
// perpendicular bisector of ab, as a point and a direction
PD midpoint = {(a.x + b.x) / 2.0, (a.y + b.y) / 2.0};
P dir = perp(b - a);                                  // {-(b.y-a.y), b.x-a.x}

Construction	Method
Circumcentre of a triangle	intersect two perpendicular bisectors
Incentre	intersect two angle bisectors, or the weighted average $\frac{a\vec{A}+b\vec{B}+c\vec{C}}{a+b+c}$
Orthocentre	intersect two altitudes
Centroid	$\frac{A+B+C}{3}$
Reflection of $p$ across line $ab$	$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 angle 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<long long,long long> canonical(P d) {
    long long 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};
}

See also: Segment Intersection · Cross Product · Half-Plane Intersection