Stolen directly from https://web.archive.org/web/20111108065352/https://www.cs.mun.ca/~rod/2500/notes/numpy-arrays/numpy-arrays.html # # line segment intersection using vectors # see Computer Graphics by F.S. Hill # from numpy import * def perp( a ) : b = empty_like(a) b[0] = -a[1] b[1] = a[0] return b # line segment a given by endpoints a1, a2 # line segment b given by endpoints … Read more
// returns true if the line from (a,b)->(c,d) intersects with (p,q)->(r,s) function intersects(a,b,c,d,p,q,r,s) { var det, gamma, lambda; det = (c – a) * (s – q) – (r – p) * (d – b); if (det === 0) { return false; } else { lambda = ((s – q) * (r – a) + … Read more
There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be vx wy − vy wx. Suppose the two line segments run from p to p + r and from q to q + s. Then any point on the first line is representable as p + t r (for a scalar parameter t) and any point … Read more