hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.

Algorithms.Geometry.ConvexHull.JarvisMarch

Description

Synopsis

# Documentation

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

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) Source #

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

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) Source #

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) Source #

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 Source #

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 Source #

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