Line Intersection

Code

type Frac = [i128; 2];
/// Calculates the intersection of line segments `p` and `q`.
/// Returns `None` for no intersection.
/// Returns `Some(Ok([x, y]))` for a point intersection, where `[x, y]` is a fraction (`[numerator, denominator]`).
/// Returns `Some(Err([x, y]))` for an overlapping line segment, where `[x, y]` represents endpoints of the overlap.
///
/// Note: Potential overflow for `i64` or `i128`; intended for use with `i32`.
fn intersect(p: L, q: L) -> Option<Result<[Frac; 2], L>> {
	use std::cmp::Ordering::*;
	let u = cross(sub(p[1], p[0]), sub(q[1], q[0]));
	let sn = cross(sub(q[0], p[0]), sub(q[1], q[0]));
	let tn = cross(sub(q[0], p[0]), sub(p[1], p[0]));
	if u != 0 {
		let int = if u >= 0 { 0..=u } else { u..=0 };
		if int.contains(&sn) && int.contains(&tn) {
			let [s, r] = [sn, u - sn].map(|x| x as i128);
			let [g, h] = p.map(|f| f.map(|x| x as i128));
			let [x, y] = [0, 1].map(|i| [r * g[i] + s * h[i], u as i128]);
			Some(Ok([x, y]))
		} else {
			None
		}
	} else {
		if sn != 0 || tn != 0 {
			return None;
		}
		let (a0, a1) = (p[0].min(p[1]), p[0].max(p[1]));
		let (b0, b1) = (q[0].min(q[1]), q[0].max(q[1]));
		let (l, r) = (a0.max(b0), a1.min(b1));
		match l.cmp(&r) {
			Less => Some(Err([l, r])),
			Equal => Some(Ok(l.map(|x| [x.into(), 1]))),
			Greater => None,
		}
	}
}

The code below only checks if two lines meet, without calculating where they do.

/// Checks if line segments `p` and `q` intersect.
/// Returns `true` if they intersect at any point, `false` otherwise.
fn meets(p: L, q: L) -> bool {
	let u = cross(sub(p[1], p[0]), sub(q[1], q[0]));
	let sn = cross(sub(q[0], p[0]), sub(q[1], q[0]));
	let tn = cross(sub(q[0], p[0]), sub(p[1], p[0]));
	if u != 0 {
		let int = if u >= 0 { 0..=u } else { u..=0 };
		int.contains(&sn) && int.contains(&tn)
	} else {
		if sn != 0 || tn != 0 {
			return false;
		}
		let (a0, a1) = (p[0].min(p[1]), p[0].max(p[1]));
		let (b0, b1) = (q[0].min(q[1]), q[0].max(q[1]));
		let (l, r) = (a0.max(b0), a1.min(b1));
		l <= r
	}
}

Last modified on 240119.