Algorithms.Geometry.ConvexHull.JarvisMarch

Documentation

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

Compute the convexhull using JarvisMarch. The resulting polygon is given in clockwise order.

running time: \(O(nh)\), where \(n\) is the number of input points and \(h\) is the complexity of the hull.

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

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

Upepr hull from left to right, without any vertical segments.

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

Computes the lower hull, from left to right. Includes vertical segments at the start.

running time: \(O(nh)\), where \(h\) is the complexity of the hull.

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

Jarvis March to compute the lower hull, without any vertical segments.

running time: \(O(nh)\), where \(h\) is the complexity of the hull.

steepestCcwFrom :: (Ord r, Num r) => (Point 2 r :+ a) -> NonEmpty (Point 2 r :+ b) -> Point 2 r :+ b

Find the next point in counter clockwise order, i.e. the point with minimum slope w.r.t. the given point.

steepestCwFrom :: (Ord r, Num r) => (Point 2 r :+ a) -> NonEmpty (Point 2 r :+ b) -> Point 2 r :+ b

Find the next point in clockwise order, i.e. the point with maximum slope w.r.t. the given point.