| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.LowerEnvelope.DualCH
Description
Synopsis
- type Envelope a r = NonEmpty (Line 2 r :+ a)
- lowerEnvelope :: (Ord r, Fractional r) => NonEmpty (Line 2 r :+ a) -> Envelope a r
- type UpperHullAlgorithm a r = NonEmpty (Point 2 r :+ a) -> NonEmpty (Point 2 r :+ a)
- lowerEnvelopeWith :: (Fractional r, Eq r) => UpperHullAlgorithm (Line 2 r :+ a) r -> NonEmpty (Line 2 r :+ a) -> Envelope a r
- vertices :: (Ord r, Fractional r) => Envelope a r -> [Point 2 r :+ (a, a)]
- intersect' :: forall r a. (Ord r, Fractional r) => (Line 2 r :+ a) -> (Line 2 r :+ a) -> Point 2 r :+ (a, a)
Documentation
lowerEnvelope :: (Ord r, Fractional r) => NonEmpty (Line 2 r :+ a) -> Envelope a r Source #
Given a list of non-vertical lines, computes the lower envelope using duality. The lines are given in left to right order.
\(O(n\log n)\)
lowerEnvelopeWith :: (Fractional r, Eq r) => UpperHullAlgorithm (Line 2 r :+ a) r -> NonEmpty (Line 2 r :+ a) -> Envelope a r Source #
Given a list of non-vertical lines, computes the lower envelope by computing the upper convex hull. It uses the given algorithm to do so
running time: O(time required by the given upper hull algorithm)