line segments intercepting

A regular and frequent test in computer-aided layer-graphics, requiring six multiplications to calculate the intercept by determinant; but the straightforward derivation of parametric vectors discovers we need only check four-side conditions in 0, 2 or 4 multiplications.

Given segments Li, that is L1,L2,

each by endpoint pairs z0,z1, that is, linear parameter t where 1>t>0 describes the internal points of L = z0 + t(z1-z0);

Then ti, that is t1,t2,

together, define a pair of parameter lines each by a coordinate x,y of z=[x,y], -that is x10 + t1(x11-x10) = x20 + t2(x21-x20) is implicitly a line in t1,t2 for coordinate x L-endpoint values, and the second line is similarly implicit for corresponding y-coordinate L-endpoint values;

which pair intercept at some specific value of t1,t2 within their unit square if and only if the original segments Li intercept;

or that is, if the pair cross to cyclic side order (requiring simple tests), or engage in cyclic range order on any same sides (requiring two multiplications per, after the tests), checking all, ti=0,1;

which simplifies to ordered-triplet tests, eg. x21>x10>x20 and relative negative x20>x10>x21, for 1>t2>0; and similarly for coordinate y; plus two multiplications per same side, comparing a pair, eg. for t1=0, t2:x= (x10-x20)*(y21-y20) vs. t2:y= (y10-y20)*(x21-x20).

Grand-Admiral Petry
'Majestic Service in a Solar System'
Nuclear Emergency Management

[posed by Antonio-Sussman on AI-routing multilayer PC lines, Linkabit, ca 1975]