Line intersections in 2D, and skew lines in 3D
Intersect two lines with the 2D cross product, tell segments that cross from lines that only would, handle parallel and collinear cases, and find where two skew lines in 3D come closest.
Two lines, two unknowns
t = ((C − A) × s) ÷ (r × s): how far along AB the meeting point is. u = ((C − A) × r) ÷ (r × s): how far along CD it is. The point itself is A + t·r, which is the same point as C + u·s.
| Result | Meaning | In a BIM model |
|---|---|---|
Report("Crossing walls", new(0, 0), new(4, 4), new(0, 4), new(4, 0));Report("Wall stops short", new(0, 0), new(2, 0), new(4, -1), new(4, 3));Report("Parallel walls", new(0, 0), new(4, 0), new(0, 2), new(4, 2)); static void Report(string name, V2 a, V2 b, V2 c, V2 d){ V2 r = b - a, s = d - c, ca = c - a; double den = V2.Cross(r, s); if (Math.Abs(den) <= 1e-9 * r.Length * s.Length) { bool collinear = Math.Abs(V2.Cross(ca, r)) <= 1e-9 * r.Length * ca.Length; Console.WriteLine($"{name}: {(collinear ? "collinear" : "parallel, no intersection")}"); return; } double t = V2.Cross(ca, s) / den; double u = V2.Cross(ca, r) / den; bool onBoth = t >= 0 && t <= 1 && u >= 0 && u <= 1; Console.WriteLine($"{name}: lines meet at {a + r * t}, t = {t}, u = {u}, {(onBoth ? "segments cross" : "segments do not")}");} readonly record struct V2(double X, double Y){ public static V2 operator +(V2 a, V2 b) => new(a.X + b.X, a.Y + b.Y); public static V2 operator -(V2 a, V2 b) => new(a.X - b.X, a.Y - b.Y); public static V2 operator *(V2 v, double k) => new(v.X * k, v.Y * k); public static double Dot(V2 a, V2 b) => a.X * b.X + a.Y * b.Y; public static double Cross(V2 a, V2 b) => a.X * b.Y - a.Y * b.X; public double Length => Math.Sqrt(X * X + Y * Y); public override string ToString() => $"({X:0.###}, {Y:0.###})";}Crossing walls: lines meet at (2, 2), t = 0.5, u = 0.5, segments cross Wall stops short: lines meet at (4, 0), t = 2, u = 0.25, segments do not Parallel walls: parallel, no intersection
Skew lines in 3D
t = (rs·sw − ss·rw) ÷ (rr·ss − rs²) u = (rr·sw − rs·rw) ÷ (rr·ss − rs²) The denominator equals |r × s|², so it is zero exactly when the lines are parallel.
var pipeA = new V3(0, 0, 3.2); var pipeB = new V3(10, 0, 3.2); // pipe, radius 0.05var ductA = new V3(2, -3, 2.6); var ductB = new V3(8, 5, 2.6); // round duct, radius 0.4 var (p, q) = ClosestPoints(pipeA, pipeB - pipeA, ductA, ductB - ductA);double gap = (p - q).Length;Console.WriteLine($"Closest on pipe: {p}");Console.WriteLine($"Closest on duct: {q}");Console.WriteLine($"Centre distance {gap:F3} m, clearance {gap - 0.05 - 0.4:F3} m"); static (V3, V3) ClosestPoints(V3 a, V3 r, V3 c, V3 s){ V3 w = a - c; double rr = V3.Dot(r, r), rs = V3.Dot(r, s), ss = V3.Dot(s, s); double rw = V3.Dot(r, w), sw = V3.Dot(s, w); double den = rr * ss - rs * rs; // |r x s|^2: zero when parallel if (den <= 1e-12 * rr * ss) throw new ArgumentException("The lines are parallel"); double t = (rs * sw - ss * rw) / den; double u = (rr * sw - rs * rw) / den; return (a + r * t, c + s * u);} readonly record struct V3(double X, double Y, double Z){ public static V3 operator +(V3 a, V3 b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z); public static V3 operator -(V3 a, V3 b) => new(a.X - b.X, a.Y - b.Y, a.Z - b.Z); public static V3 operator *(V3 v, double k) => new(v.X * k, v.Y * k, v.Z * k); public static double Dot(V3 a, V3 b) => a.X * b.X + a.Y * b.Y + a.Z * b.Z; public double Length => Math.Sqrt(Dot(this, this)); public override string ToString() => $"({X:0.###}, {Y:0.###}, {Z:0.###})";}Closest on pipe: (4.25, 0, 3.2) Closest on duct: (4.25, 0, 2.6) Centre distance 0.600 m, clearance 0.150 m
Extend(a, b, c, d) for a wall join: if the line of wall AB meets wall CD (0 ≤ u ≤ 1) beyond B (t > 1), return the extended end point; otherwise leave B unchanged. Test it with AB = (0, 0)→(3, 0) against CD = (5, −2)→(5, 2), and against CD = (5, 1)→(5, 4).
Show a hint
Report. Only t > 1 together with 0 ≤ u ≤ 1 is a join; in the second test the line of AB passes below wall CD, so u is negative.
Show the solution
var a = new V2(0, 0);var b = new V2(3, 0);Console.WriteLine(Extend(a, b, new(5, -2), new(5, 2)));Console.WriteLine(Extend(a, b, new(5, 1), new(5, 4))); static string Extend(V2 a, V2 b, V2 c, V2 d){ V2 r = b - a, s = d - c, ca = c - a; double den = V2.Cross(r, s); if (Math.Abs(den) <= 1e-9 * r.Length * s.Length) return $"Parallel: {b} unchanged"; double t = V2.Cross(ca, s) / den; double u = V2.Cross(ca, r) / den; if (t > 1 && u >= 0 && u <= 1) return $"Extended to {a + r * t}"; return $"No join: {b} unchanged";} readonly record struct V2(double X, double Y){ public static V2 operator +(V2 a, V2 b) => new(a.X + b.X, a.Y + b.Y); public static V2 operator -(V2 a, V2 b) => new(a.X - b.X, a.Y - b.Y); public static V2 operator *(V2 v, double k) => new(v.X * k, v.Y * k); public static double Dot(V2 a, V2 b) => a.X * b.X + a.Y * b.Y; public static double Cross(V2 a, V2 b) => a.X * b.Y - a.Y * b.X; public double Length => Math.Sqrt(X * X + Y * Y); public override string ToString() => $"({X:0.###}, {Y:0.###})";}Extended to (5, 0) No join: (3, 0) unchanged
Remember
For A + t·r and C + u·s: t = ((C − A) × s) ÷ (r × s) and u = ((C − A) × r) ÷ (r × s). Test r × s against a scale-aware tolerance before dividing: zero means parallel or collinear. The segments cross only if both t and u are in [0, 1]; otherwise t and u say which wall to extend, and by how much. In 3D, non-parallel lines are usually skew; find their closest points with two dot-product equations. The distance between centrelines, minus the radii, is the clearance used in clash detection.