module Algorithms.Geometry.ConvexHull.DivideAndConqueror( convexHull
, module Types
) where
import Data.Semigroup.Foldable
import Data.Semigroup
import Algorithms.Geometry.ConvexHull.Types as Types
import Control.Lens((^.))
import Data.BinaryTree
import Data.Ext
import Data.Function(on)
import Data.Geometry.Point
import Data.Geometry.Polygon
import qualified Data.Geometry.Polygon.Convex as Convex
import qualified Data.List.NonEmpty as NonEmpty
convexHull :: (Ord r, Num r)
=> NonEmpty.NonEmpty (Point 2 r :+ p) -> ConvexHull p r
convexHull = unMerge
. foldMap1 (Merge . ConvexHull . fromPoints . (:[]) . _unElem)
. asBalancedBinLeafTree
. NonEmpty.sortBy (compare `on` (^.core))
newtype Merge r p = Merge { unMerge :: ConvexHull p r }
instance (Num r, Ord r) => Semigroup (Merge r p) where
(Merge lp) <> (Merge rp) = Merge . ConvexHull $ ch
where
(ch,_,_) = Convex.merge (lp^.extractHull) (rp^.extractHull)