hgeometry-0.12.0.0: Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

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