Algorithms.Geometry.LineSegmentIntersection.BentleyOttmann

The \(O((n+k)\log n)\) time line segment intersection algorithm by Bentley and Ottmann.

Documentation

intersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r

Compute all intersections

\(O((n+k)\log n)\), where \(k\) is the number of intersections.

interiorIntersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r

Computes all intersection points p s.t. p lies in the interior of at least one of the segments.

\(O((n+k)\log n)\), where \(k\) is the number of intersections.

ordAt :: (Fractional r, Ord r) => r -> Compare (LineSegment 2 p r)

Compare based on the x-coordinate of the intersection with the horizontal line through y

xCoordAt :: (Fractional r, Ord r) => r -> LineSegment 2 p r -> r

Given a y coord and a line segment that intersects the horizontal line through y, compute the x-coordinate of this intersection point.

note that we will pretend that the line segment is closed, even if it is not