hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.

Algorithms.Geometry.LineSegmentIntersection.BentleyOttmann

Description

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

Synopsis

# Documentation

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

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 Source #

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) Source #

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 Source #

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