hgeometry-0.12.0.2: Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

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.