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 L_{i}, that is L_{1},L_{2},

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

Then t_{i}, that is t_{1},t_{2},

together, define a pair of parameter lines each by a coordinate x,y of z=[x,y], -that is x_{10} + t_{1}(x_{11}-x_{10}) = x_{20} + t_{2}(x_{21}-x_{20}) is implicitly a line in t_{1},t_{2} 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 t_{1},t_{2} within their unit square if and only if the original segments L_{i} 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, t_{i}=0,1;

which simplifies to ordered-triplet tests, eg. x_{21}>x_{10}>x_{20} and relative negative x_{20}>x_{10}>x_{21}, for 1>t_{2}>0; and similarly for coordinate y; plus two multiplications per same side, comparing a pair, eg. for t_{1}=0, t_{2:x}= (x_{10}-x_{20})*(y_{21}-y_{20}) vs. t_{2:y}= (y_{10}-y_{20})*(x_{21}-x_{20}).

'Majestic Service in a Solar System'

Nuclear Emergency Management

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