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

License | see the LICENSE file |

Maintainer | Frank Staals |

Safe Haskell | None |

Language | Haskell2010 |

## Synopsis

- convexHull :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> ConvexPolygon p r
- upperHull :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p)
- upperHull' :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p)
- lowerHull :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p)
- lowerHull' :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p)
- upperHullFromSorted :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p)
- upperHullFromSorted' :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p)

# Documentation

convexHull :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> ConvexPolygon p r Source #

\(O(n \log n)\) time ConvexHull using Graham-Scan. The resulting polygon is given in clockwise order.

upperHull :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) Source #

Computes the upper hull. The upper hull is given from left to right.

Specifically. A pair of points defines an edge of the upper hull iff all other points are strictly to the right of its supporting line.

Note that this definition implies that the segment may be
vertical. Use `upperHull'`

if such an edge should not be reported.

running time: \(O(n\log n)\)

upperHull' :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) Source #

Computes the upper hull, making sure that there are no vertical segments.

The upper hull is given from left to right

lowerHull :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) Source #

Computes the upper hull. The upper hull is given from left to right.

Specifically. A pair of points defines an edge of the lower hull iff all other points are strictly to the left of its supporting line.

Note that this definition implies that the segment may be
vertical. Use `lowerHull'`

if such an edge should not be reported.

running time: \(O(n\log n)\)

lowerHull' :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) Source #

Computes the lower hull, making sure there are no vertical segments. (Note that the only such segment could be the first segment).

upperHullFromSorted :: (Ord r, Num r) => NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) Source #

Given a sequence of points that is sorted on increasing x-coordinate and decreasing y-coordinate, computes the upper hull, in *right to left order*.

Specifically. A pair of points defines an edge of the upper hull iff all other points are strictly to the right of its supporting line.

Note that In constrast to the `upperHull`

function, the result is
returned *from right to left* !!!

running time: \(O(n)\).