AlgoScope

Line Intersection

Where two segments meet is decided by orientations, then the point by cross-product ratios.

Computational geometry, algorithm, intermediate
orient(A, B, C) is 1.ABCD
orient(A, B, C) is 1.ABCD

Plane Geometry: Two segments that cross

Decision, step 2 of 6

orient(A, B, C) = 1: C is to the left of the line through A and B.

How plane geometry works

Cost

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

Taught by the same lesson

Plane Geometry covers these too, in the same run.