| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | GHC2024 |
HGeometry.LineSegment.Intersection.BentleyOttmann
Description
The \(O((n+k)\log n)\) time line segment intersection algorithm by Bentley and Ottmann.
Synopsis
- intersections :: forall bag lineSegment seg point r. (LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, Foldable bag, Functor bag, Eq lineSegment, HasOnSegment lineSegment 2, IntersectConstraints seg lineSegment, LineSegment_ seg point, StartPointOf lineSegment ~ EndPointOf lineSegment) => bag lineSegment -> Intersections r lineSegment
- interiorIntersections :: (LineSegment_ lineSegment point, Point_ point 2 r, Eq lineSegment, Ord r, Fractional r, IntersectConstraints seg lineSegment, LineSegment_ seg point, StartPointOf lineSegment ~ EndPointOf lineSegment, HasOnSegment lineSegment 2, Foldable f, Functor f) => f lineSegment -> Intersections r lineSegment
- module HGeometry.LineSegment.Intersection.Types
Documentation
intersections :: forall bag lineSegment seg point r. (LineSegment_ lineSegment point, Point_ point 2 r, Ord r, Fractional r, Foldable bag, Functor bag, Eq lineSegment, HasOnSegment lineSegment 2, IntersectConstraints seg lineSegment, LineSegment_ seg point, StartPointOf lineSegment ~ EndPointOf lineSegment) => bag lineSegment -> Intersections r lineSegment Source #
Compute all intersections
\(O((n+k)\log n)\), where \(k\) is the number of intersections.
interiorIntersections :: (LineSegment_ lineSegment point, Point_ point 2 r, Eq lineSegment, Ord r, Fractional r, IntersectConstraints seg lineSegment, LineSegment_ seg point, StartPointOf lineSegment ~ EndPointOf lineSegment, HasOnSegment lineSegment 2, Foldable f, Functor f) => f lineSegment -> Intersections r lineSegment 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.