HGeometry.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

convexHull :: (Ord r, Num r, Point_ point 2 r) => NonEmpty point -> ConvexPolygon point
upperHull :: (Ord r, Num r, Point_ point 2 r) => NonEmpty point -> NonEmpty point
lowerHull :: (Ord r, Num r, Point_ point 2 r) => NonEmpty point -> NonEmpty point

Documentation

\(O(n \log n)\) time ConvexHull using divide and conquer.

upperHull :: (Ord r, Num r, Point_ point 2 r) => NonEmpty point -> NonEmpty point 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, Point_ point 2 r) => NonEmpty point -> NonEmpty point 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.