Algorithms.Geometry.ConvexHull.GrahamScan

Documentation

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

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

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)

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)

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)

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)

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

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

Computes the upper hull from a sorted input. Removes the last vertical segment.

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