SEGMENT INTERSECTION do two segments cross? — four orientations decide, no arithmetic on the point
Two line segments cross if and only if each one straddles the other’s line — and that is four orientation tests, no need to compute the intersection point at all. Segment AB crosses CD when C and D fall on opposite sides of AB (one orientation +, one −) and A and B fall on opposite sides of CD. It is the cross product (dart 486) read four times. The diagonals of a square cross (an X); two parallel horizontals never do. Robust, exact on integers, and the workhorse of every intersection and clipping routine.
THE TECHNIQUE cross iff each segment straddles the other — 4 orientation tests
The demo tests the two diagonals of a square (they cross) and two parallel segments (they do not) using only orientation: live demo
HISTORY & CREDIT segment intersection · straddle test
“To know if segments cross, find where they meet.” — four orientation signs decide it without computing the point. cited
the straddle · C, D on opposite sides of AB and A, B on opposite sides of CD. the test · four orientations; unequal pairs on both → they cross — no point computed. the use · intersection, clipping, sweep-line — all built on this straddle.
Two segments judged to cross by which side each endpoint falls on — four cross products, no meeting point. predicate
RECOMMEND FOR I-13 the straddle test, on the compiler
On the canonical compiler, the square’s diagonals cross (1); two parallel horizontals do not (0):
$ i13 run cg_lineintersection.i13 # 4 orientations
RUN OK · 406 step(s) · peak stack 9 · call depth 3
crossX = 1 -- diagonals (0,0)-(4,4) and (0,4)-(4,0) cross
parallel = 0 -- two horizontals do not
test = 1
Recommend as a NULL — a recognizer built on orientation. The straddle test decides whether two segments cross (B41) using four cross products (B39); it checks a relation rather than generating an invariant. NULL — four reads of dart 486, and the heart of every clipping routine.