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.

\(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)

vertices :: (Ord r, Fractional r) => Envelope a r -> [Point 2 r :+ (a, a)] Source #

Computes the vertices of the envelope, in left to right order

intersect' :: forall r a. (Ord r, Fractional r) => (Line 2 r :+ a) -> (Line 2 r :+ a) -> Point 2 r :+ (a, a) Source #

Given two non-parallel lines, compute the intersection point and return the pair of a's associated with the lines