hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.
Copyright (C) Frank Staals see the LICENSE file Frank Staals None Haskell2010

Algorithms.Geometry.LowerEnvelope.DualCH

Description

Synopsis

# Documentation

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

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

type UpperHullAlgorithm a r = NonEmpty (Point 2 r :+ a) -> NonEmpty (Point 2 r :+ a) Source #

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