| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.LineSegmentIntersection.BentleyOttmann
Description
The \(O((n+k)\log n)\) time line segment intersection algorithm by Bentley and Ottmann.
Synopsis
- intersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r
- interiorIntersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r
- ordAt :: (Fractional r, Ord r) => r -> Compare (LineSegment 2 p r)
- xCoordAt :: (Fractional r, Ord r) => r -> LineSegment 2 p r -> r
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