----------------------------------------------------------------------------- -- | -- Module : Diagrams.TwoD.Points -- Copyright : (c) 2014 diagrams-lib team (see LICENSE) -- License : BSD-style (see LICENSE) -- Maintainer : diagrams-discuss@googlegroups.com -- -- Special functions for points in R2. -- ----------------------------------------------------------------------------- {-# LANGUAGE TypeFamilies #-} module Diagrams.TwoD.Points where import Data.List import Diagrams.Core import Diagrams.TwoD.Vector import Diagrams.TwoD.Types (P2) import Linear.Affine -- | Find the convex hull of a list of points using Andrew's monotone chain -- algorithm O(n log n). -- -- Returns clockwise list of points starting from the left-most point. convexHull2D :: OrderedField n => [P2 n] -> [P2 n] convexHull2D ps = init upper ++ reverse (tail lower) where (upper, lower) = sortedConvexHull (sort ps) -- | Find the convex hull of a set of points already sorted in the x direction. -- The first list of the tuple is the upper hull going clockwise from -- left-most to right-most point. The second is the lower hull from -- right-most to left-most in the anti-clockwise direction. sortedConvexHull :: OrderedField n => [P2 n] -> ([P2 n], [P2 n]) sortedConvexHull ps = (chain True ps, chain False ps) where chain upper (p1_:p2_:rest_) = case go (p2_ .-. p1_) p2_ rest_ of Right l -> p1_:l Left l -> chain upper (p1_:l) where test = if upper then (>0) else (<0) -- find the convex hull by comparing the angles of the vectors with -- the cross product and backtracking if necessary go dir p1 l@(p2:rest) -- backtrack if the direction is outward | test \$ dir `cross2` dir' = Left l | otherwise = case go dir' p2 rest of Left m -> go dir p1 m Right m -> Right (p1:m) where dir' = p2 .-. p1 go _ p1 p = Right (p1:p) chain _ l = l