--------------------------------------------------------------------------------
-- |
-- Module      :  Data.Geometry.Polygon.Extremes
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- Finding the Extremal vertex of a polygon in a given direction.
--
--------------------------------------------------------------------------------
module Data.Geometry.Polygon.Extremes( cmpExtreme
                                     , extremesLinear
                                     ) where

import           Control.Lens hiding (Simple,simple)
import           Data.Ext
import           Data.Geometry.Point
import           Data.Geometry.Polygon.Core as P
import           Data.Geometry.Vector

--------------------------------------------------------------------------------

{- HLINT ignore cmpExtreme -}
-- | Comparison that compares which point is 'larger' in the direction given by
-- the vector u.
cmpExtreme       :: (Num r, Ord r)
                 => Vector 2 r -> Point 2 r :+ p -> Point 2 r :+ q -> Ordering
cmpExtreme :: Vector 2 r -> (Point 2 r :+ p) -> (Point 2 r :+ q) -> Ordering
cmpExtreme Vector 2 r
u Point 2 r :+ p
p Point 2 r :+ q
q = Vector 2 r
u Vector 2 r -> Vector 2 r -> r
forall (f :: * -> *) a. (Metric f, Num a) => f a -> f a -> a
`dot` (Point 2 r :+ p
p(Point 2 r :+ p)
-> Getting (Point 2 r) (Point 2 r :+ p) (Point 2 r) -> Point 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Point 2 r) (Point 2 r :+ p) (Point 2 r)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core Point 2 r -> Point 2 r -> Diff (Point 2) r
forall (p :: * -> *) a. (Affine p, Num a) => p a -> p a -> Diff p a
.-. Point 2 r :+ q
q(Point 2 r :+ q)
-> Getting (Point 2 r) (Point 2 r :+ q) (Point 2 r) -> Point 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Point 2 r) (Point 2 r :+ q) (Point 2 r)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core) r -> r -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` r
0


-- | Finds the extreme points, minimum and maximum, in a given direction
--
-- running time: \(O(n)\)
extremesLinear     :: (Ord r, Num r) => Vector 2 r -> Polygon t p r
                   -> (Point 2 r :+ p, Point 2 r :+ p)
extremesLinear :: Vector 2 r -> Polygon t p r -> (Point 2 r :+ p, Point 2 r :+ p)
extremesLinear Vector 2 r
u Polygon t p r
p = let simple :: SimplePolygon p r
simple = Polygon t p r
pPolygon t p r
-> Getting (SimplePolygon p r) (Polygon t p r) (SimplePolygon p r)
-> SimplePolygon p r
forall s a. s -> Getting a s a -> a
^.Getting (SimplePolygon p r) (Polygon t p r) (SimplePolygon p r)
forall (t :: PolygonType) p r.
Lens' (Polygon t p r) (SimplePolygon p r)
outerBoundary
                         f :: (Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering
f  = Vector 2 r -> (Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering
forall r p q.
(Num r, Ord r) =>
Vector 2 r -> (Point 2 r :+ p) -> (Point 2 r :+ q) -> Ordering
cmpExtreme Vector 2 r
u
                     in (((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering)
-> SimplePolygon p r -> Point 2 r :+ p
forall r p (t :: PolygonType).
((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering)
-> Polygon t p r -> Point 2 r :+ p
P.minimumVertexBy (Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering
f SimplePolygon p r
simple, ((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering)
-> SimplePolygon p r -> Point 2 r :+ p
forall r p (t :: PolygonType).
((Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering)
-> Polygon t p r -> Point 2 r :+ p
P.maximumVertexBy (Point 2 r :+ p) -> (Point 2 r :+ p) -> Ordering
f SimplePolygon p r
simple)