BentleyOttmann

Reports intersections between two-dimensional segments. The sweep uses a shear to make vertical segments x-monotone; reported coordinates remain in the original coordinate system. The status is an order-maintenance tree: its keys never depend on the current sweep coordinate.

Expected time O((n + k) log(n + k)), space O(n + k), for k reported pairs under consistent geometric predicates. Epsilon-based intersection tests near their tolerance boundary can disagree with floating-point event coordinates, so finite near-coincident inputs can produce missing intersections (see precision tracking issue).