hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.
Copyright (C) Frank Staals see the LICENSE file Frank Staals None Haskell2010

Algorithms.Geometry.ConvexHull.DivideAndConquer

Description

$$O(n\log n)$$ time divide and conquer algorithm to compute the convex hull of a set of $$n$$ points in $$\mathbb{R}^2$$.

Synopsis

# Documentation

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

$$O(n \log n)$$ time ConvexHull using divide and conquer. The resulting polygon is given in clockwise order.

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

$$O(n \log n)$$ time UpperHull using divide and conquer. The resulting Hull is given from left to right, i.e. in clockwise order.

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

$$O(n \log n)$$ time LowerHull using divide and conquer. The resulting Hull is given from left to right, i.e. in counter clockwise order.