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

Safe HaskellNone
LanguageHaskell2010

Algorithms.Geometry.ConvexHull.JarvisMarch

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.