Copyright | (C) Frank Staals |
---|---|

License | see the LICENSE file |

Maintainer | Frank Staals |

Safe Haskell | None |

Language | Haskell2010 |

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