--------------------------------------------------------------------------------
-- |
-- Module      :  Data.Geometry.Polygon
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- A Polygon data type and some basic functions to interact with them.
--
--------------------------------------------------------------------------------
module Data.Geometry.Polygon
  ( -- * Types
    PolygonType(..)
  , Polygon(..)
  , _SimplePolygon, _MultiPolygon
  , SimplePolygon, MultiPolygon, SomePolygon

    -- * Conversion
  , fromPoints
  , fromCircularVector

  , simpleFromPoints
  , simpleFromCircularVector

  , unsafeFromPoints
  , unsafeFromCircularVector
  , unsafeFromVector
  , toVector
  , toPoints

  , isSimple

    -- * Accessors

  , size
  , polygonVertices, listEdges

  , outerBoundary, outerBoundaryVector
  , unsafeOuterBoundaryVector
  , outerBoundaryEdges
  , outerVertex, outerBoundaryEdge

  , polygonHoles, polygonHoles'
  , holeList

    -- * Properties

  , area, signedArea
  , centroid

    -- * Queries
  , inPolygon, insidePolygon, onBoundary


  , isTriangle, isStarShaped

  , isCounterClockwise
  , toCounterClockWiseOrder, toCounterClockWiseOrder'
  , toClockwiseOrder, toClockwiseOrder'
  , reverseOuterBoundary

  , rotateLeft
  , rotateRight
  , maximumVertexBy
  , minimumVertexBy


   -- * Misc
  , pickPoint
  , findDiagonal

  , withIncidentEdges, numberVertices

  , extremesLinear, cmpExtreme

  , findRotateTo

  ) where

import           Algorithms.Geometry.InPolygon
import           Algorithms.Geometry.LinearProgramming.LP2DRIC
import           Algorithms.Geometry.LinearProgramming.Types
import           Control.Lens hiding (Simple)
import           Control.Monad.Random.Class
import           Data.Ext
import qualified Data.Foldable as F
import           Data.Geometry.HalfSpace (rightOf)
import           Data.Geometry.Line
import           Data.Geometry.LineSegment
import           Data.Geometry.Point
import           Data.Geometry.Boundary
import           Data.Geometry.Polygon.Core
import           Data.Geometry.Polygon.Extremes
import           Data.Geometry.Properties
import qualified Data.Sequence as Seq

--------------------------------------------------------------------------------
-- * Polygons

-- | Test if a Simple polygon is star-shaped. Returns a point in the kernel
-- (i.e. from which the entire polygon is visible), if it exists.
--
--
-- \(O(n)\) expected time
isStarShaped    :: (MonadRandom m, Ord r, Fractional r)
                => SimplePolygon p r -> m (Maybe (Point 2 r))
isStarShaped :: SimplePolygon p r -> m (Maybe (Point 2 r))
isStarShaped (SimplePolygon p r -> SimplePolygon p r
forall r (t :: PolygonType) p.
(Eq r, Num r) =>
Polygon t p r -> Polygon t p r
toClockwiseOrder -> SimplePolygon p r
pg) =
    LinearProgram 2 r -> m (Maybe (Point 2 r))
forall (m :: * -> *) r.
(MonadRandom m, Ord r, Fractional r) =>
LinearProgram 2 r -> m (Maybe (Point 2 r))
solveBoundedLinearProgram (LinearProgram 2 r -> m (Maybe (Point 2 r)))
-> LinearProgram 2 r -> m (Maybe (Point 2 r))
forall a b. (a -> b) -> a -> b
$ Vector 2 r -> [HalfSpace 2 r] -> LinearProgram 2 r
forall (d :: Nat) r.
Vector d r -> [HalfSpace d r] -> LinearProgram d r
LinearProgram Vector 2 r
c (CircularVector (HalfSpace 2 r) -> [HalfSpace 2 r]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList CircularVector (HalfSpace 2 r)
hs)
  where
    c :: Vector 2 r
c  = SimplePolygon p r
pgSimplePolygon p r
-> Getting (Vector 2 r) (SimplePolygon p r) (Vector 2 r)
-> Vector 2 r
forall s a. s -> Getting a s a -> a
^.Int -> Getter (SimplePolygon p r) (Point 2 r :+ p)
forall (t :: PolygonType) p r.
Int -> Getter (Polygon t p r) (Point 2 r :+ p)
outerVertex Int
1(((Point 2 r :+ p) -> Const (Vector 2 r) (Point 2 r :+ p))
 -> SimplePolygon p r -> Const (Vector 2 r) (SimplePolygon p r))
-> ((Vector 2 r -> Const (Vector 2 r) (Vector 2 r))
    -> (Point 2 r :+ p) -> Const (Vector 2 r) (Point 2 r :+ p))
-> Getting (Vector 2 r) (SimplePolygon p r) (Vector 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const (Vector 2 r) (Point 2 r))
-> (Point 2 r :+ p) -> Const (Vector 2 r) (Point 2 r :+ p)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core((Point 2 r -> Const (Vector 2 r) (Point 2 r))
 -> (Point 2 r :+ p) -> Const (Vector 2 r) (Point 2 r :+ p))
-> ((Vector 2 r -> Const (Vector 2 r) (Vector 2 r))
    -> Point 2 r -> Const (Vector 2 r) (Point 2 r))
-> (Vector 2 r -> Const (Vector 2 r) (Vector 2 r))
-> (Point 2 r :+ p)
-> Const (Vector 2 r) (Point 2 r :+ p)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector 2 r -> Const (Vector 2 r) (Vector 2 r))
-> Point 2 r -> Const (Vector 2 r) (Point 2 r)
forall (d :: Nat) r r'.
Lens (Point d r) (Point d r') (Vector d r) (Vector d r')
vector
    -- the first vertex is the intersection point of the two supporting lines
    -- bounding it, so the first two edges bound the shape in this sirection
    hs :: CircularVector (HalfSpace 2 r)
hs = (LineSegment 2 p r -> HalfSpace 2 r)
-> CircularVector (LineSegment 2 p r)
-> CircularVector (HalfSpace 2 r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Line 2 r -> HalfSpace 2 r
forall r. Num r => Line 2 r -> HalfPlane r
rightOf (Line 2 r -> HalfSpace 2 r)
-> (LineSegment 2 p r -> Line 2 r)
-> LineSegment 2 p r
-> HalfSpace 2 r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. LineSegment 2 p r -> Line 2 r
forall t.
HasSupportingLine t =>
t -> Line (Dimension t) (NumType t)
supportingLine) (CircularVector (LineSegment 2 p r)
 -> CircularVector (HalfSpace 2 r))
-> (SimplePolygon p r -> CircularVector (LineSegment 2 p r))
-> SimplePolygon p r
-> CircularVector (HalfSpace 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SimplePolygon p r -> CircularVector (LineSegment 2 p r)
forall (t :: PolygonType) p r.
Polygon t p r -> CircularVector (LineSegment 2 p r)
outerBoundaryEdges (SimplePolygon p r -> CircularVector (HalfSpace 2 r))
-> SimplePolygon p r -> CircularVector (HalfSpace 2 r)
forall a b. (a -> b) -> a -> b
$ SimplePolygon p r
pg


--------------------------------------------------------------------------------
-- * Instances

type instance IntersectionOf (Line 2 r) (Boundary (Polygon t p r)) =
  '[Seq.Seq (Either (Point 2 r) (LineSegment 2 () r))]

type instance IntersectionOf (Point 2 r) (Polygon t p r) = [NoIntersection, Point 2 r]

instance (Fractional r, Ord r) => Point 2 r `IsIntersectableWith` Polygon t p r where
  nonEmptyIntersection :: proxy (Point 2 r)
-> proxy (Polygon t p r)
-> Intersection (Point 2 r) (Polygon t p r)
-> Bool
nonEmptyIntersection = proxy (Point 2 r)
-> proxy (Polygon t p r)
-> Intersection (Point 2 r) (Polygon t p r)
-> Bool
forall g h (proxy :: * -> *).
(NoIntersection ∈ IntersectionOf g h,
 RecApplicative (IntersectionOf g h)) =>
proxy g -> proxy h -> Intersection g h -> Bool
defaultNonEmptyIntersection
  Point 2 r
q intersects :: Point 2 r -> Polygon t p r -> Bool
`intersects` Polygon t p r
pg = Point 2 r
q Point 2 r -> Polygon t p r -> PointLocationResult
forall (t :: PolygonType) p r.
(Fractional r, Ord r) =>
Point 2 r -> Polygon t p r -> PointLocationResult
`inPolygon` Polygon t p r
pg PointLocationResult -> PointLocationResult -> Bool
forall a. Eq a => a -> a -> Bool
/= PointLocationResult
Outside
  Point 2 r
q intersect :: Point 2 r
-> Polygon t p r -> Intersection (Point 2 r) (Polygon t p r)
`intersect` Polygon t p r
pg | Point 2 r
q Point 2 r -> Polygon t p r -> Bool
forall g h. IsIntersectableWith g h => g -> h -> Bool
`intersects` Polygon t p r
pg = Point 2 r -> CoRec Identity '[NoIntersection, Point 2 r]
forall a (as :: [*]). (a ∈ as) => a -> CoRec Identity as
coRec Point 2 r
q
                   | Bool
otherwise         = NoIntersection -> CoRec Identity '[NoIntersection, Point 2 r]
forall a (as :: [*]). (a ∈ as) => a -> CoRec Identity as
coRec NoIntersection
NoIntersection

-- instance IsIntersectableWith (Line 2 r) (Boundary (Polygon t p r)) where
--   nonEmptyIntersection _ _ (CoRec xs) = null xs
--   l `intersect` (Boundary (SimplePolygon vs)) =
--     undefined
  -- l `intersect` (Boundary (MultiPolygon vs hs)) = coRec .
  --    Seq.sortBy f . Seq.fromList
  --     . concatMap (unpack . (l `intersect`) . Boundary)
  --     $ SimplePolygon vs : hs
  --   where
  --     unpack (CoRec x) = x
  --     f = undefined