Algorithms.Geometry.LowerEnvelope.DualCH

Documentation

type Envelope a r = NonEmpty (Line 2 r :+ a)

lowerEnvelope :: (Ord r, Fractional r) => NonEmpty (Line 2 r :+ a) -> Envelope a r

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

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

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

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)

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