cross(OA,OB)=ax*by-ay*bx; its sign gives left turn, right turn, or collinearity, while dot products encode angle and projection direction.
Recognition signals
Orientation or collinearity of three points
Segment intersection
Signed polygon area
Convex hull or boundary order
Slopes risk vertical lines and precision loss
False friends
Signal
Why it is different
Bounding boxes alone
Overlapping boxes are not sufficient for segment intersection; orientation tests are still required.
Direct zero tests on floats
Floating geometry needs an epsilon or robust predicate, not raw ==0.
Core invariant
Under one coordinate and point-order convention, cross-product sign consistently represents oriented turning; collinear cases then use coordinate ranges.
State, transition, and processing order
Item
Definition
State
Point coordinates, orientation values o1..o4, boundary-inclusion policy, and numeric tolerance.
Transition
Compute orientations of triples; strict intersection needs opposite sides, while zero orientations enter on-segment handling.
Frontier / order
There is no search frontier; each local relation is summarized by a fixed number of geometric predicates.
Python skeleton
def cross(a, b, c):
return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
def on_segment(a, b, p):
return (cross(a,b,p) == 0 and
min(a[0],b[0]) <= p[0] <= max(a[0],b[0]) and
min(a[1],b[1]) <= p[1] <= max(a[1],b[1]))
def segments_intersect(a, b, c, d):
x1, x2, x3, x4 = cross(a,b,c), cross(a,b,d), cross(c,d,a), cross(c,d,b)
if ((x1 > 0 > x2 or x2 > 0 > x1) and
(x3 > 0 > x4 or x4 > 0 > x3)):
return True
return (x1 == 0 and on_segment(a,b,c) or
x2 == 0 and on_segment(a,b,d) or
x3 == 0 and on_segment(c,d,a) or
x4 == 0 and on_segment(c,d,b))
Correctness sketch
Cross product is signed parallelogram area, so its sign encodes orientation.
At a proper intersection, each segment's endpoints lie on opposite sides of the other's supporting line.
When both opposite-side conditions hold, the crossing point lies inside both segments.
A zero cross product plus coordinate bounds handles touching and collinear overlap.
Complexity
Time
Space
Parameters
O(1) per orientation or segment-intersection test
O(1)
Coordinate range determines overflow or floating-tolerance policy
Edge cases
Zero-length segments
Whether endpoint touching counts
Collinear overlap
Large-integer multiplication overflow
Near-collinear floating input
Error patterns
Pattern
Why it fails / fix
Dividing slopes
Vertical lines divide by zero and floating errors amplify.
Omitting collinear cases
Strict crossing misses endpoint contact and overlap.