AlgoScope

Segment Intersection

Two segments cross when each straddles the other's line, decided by four orientation tests.

Computational geometry, algorithm, intermediate
The segments intersect.ABCD
The segments intersect.ABCD

Plane Geometry: Two segments that cross

Result, step 6 of 6

C and D are on opposite sides of AB (1 vs -1) and A and B on opposite sides of CD (-1 vs 1): the segments cross.

How plane geometry works

Cost

Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Plane Geometry covers these too, in the same run.