{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE UndecidableInstances #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  HGeometry.Polygon.Class
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- A polygon and some basic functions to interact with them.
--
--------------------------------------------------------------------------------
module HGeometry.Polygon.Class
  ( HasOuterBoundary(..)
  , signedArea2X
  , minimumVertexBy, maximumVertexBy
  , outerBoundaryEdgeSegmentAt, outerBoundaryEdgeSegments
  , outerBoundaryWithNeighbours

  , Hole
  , HasHoles(..)

  , Polygon_(..)

  , HasVertices(..), HasVertices'(..)
  , HasEdges(..), HasEdges'(..)


  , HasPickPoint(..)
  ) where

import           Control.Lens hiding (holes)
import           Data.Function (on)
import qualified Data.Functor.Apply as Apply
import           Data.Kind (Type)
import           Data.Semigroup (First(..))
import           Data.Vector.NonEmpty.Internal (NonEmptyVector)
import           Data.Void
import           HGeometry.Cyclic (Cyclic)
import           HGeometry.Ext
import           HGeometry.Lens.Util
import           HGeometry.LineSegment
import           HGeometry.Point
import           HGeometry.Polygon.Simple.Type
import           HGeometry.Properties
import           HGeometry.Triangle
import           HGeometry.Vector
import           Hiraffe.Graph

--------------------------------------------------------------------------------
-- ^ A class for items that have an outer boundary.
class HasVertices polygon polygon => HasOuterBoundary polygon where
  {-# MINIMAL outerBoundaryVertexAt, ccwOuterBoundaryFrom, cwOuterBoundaryFrom #-}

  -- | A fold over all vertices of the outer boundary, the
  -- vertices are traversed in CCW order.
  --
  -- running time :: \(O(n)\)
  outerBoundary :: IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
  default outerBoundary :: Num (VertexIx polygon)
                        => IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
  outerBoundary = VertexIx polygon
-> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
ccwOuterBoundaryFrom VertexIx polygon
0

  -- | A CCW-traversal over all vertices of the outer boundary, starting
  -- from the vertex with the given index.
  --
  -- running time :: \(O(n)\)
  ccwOuterBoundaryFrom :: VertexIx polygon
                       -> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)

  -- | A CW-fold over all vertices of the outer boundary, starting
  -- from the vertex with the given index.
  --
  -- running time :: \(O(n)\)
  cwOuterBoundaryFrom        :: VertexIx polygon
                             -> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)

  -- | A particular vertex of the outer polygon
  --
  -- running time: \(O(1)\)
  outerBoundaryVertexAt   :: VertexIx polygon
                          -> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)

  -- | A fold over all edges in the polygon. The edges are folded over
  -- in CCW order, and each edge is associated with the index of its start vertex
  -- outerBoundaryEdges :: IndexedFold (VertexIx polygon) polygon (Vertex polygon, Vertex polygon)
  --
  --
  -- running time :: \(O(n)\)
  outerBoundaryEdges :: IndexedFold1 (VertexIx polygon,VertexIx polygon) polygon
                                     (Vertex polygon, Vertex polygon)
  default outerBoundaryEdges
    :: Enum (VertexIx polygon)
    => IndexedFold1 (VertexIx polygon,VertexIx polygon) polygon (Vertex polygon, Vertex polygon)
  outerBoundaryEdges = (polygon
 -> NonEmpty
      ((VertexIx polygon, VertexIx polygon),
       (Vertex polygon, Vertex polygon)))
-> Over
     p
     f
     polygon
     polygon
     (Vertex polygon, Vertex polygon)
     (Vertex polygon, Vertex polygon)
forall (f :: * -> *) i (p :: * -> * -> *) (g :: * -> *) s a t b.
(Foldable1 f, Indexable i p, Contravariant g, Apply g) =>
(s -> f (i, a)) -> Over p g s t a b
ifolding1 ((polygon
  -> NonEmpty
       ((VertexIx polygon, VertexIx polygon),
        (Vertex polygon, Vertex polygon)))
 -> Over
      p
      f
      polygon
      polygon
      (Vertex polygon, Vertex polygon)
      (Vertex polygon, Vertex polygon))
-> (polygon
    -> NonEmpty
         ((VertexIx polygon, VertexIx polygon),
          (Vertex polygon, Vertex polygon)))
-> Over
     p
     f
     polygon
     polygon
     (Vertex polygon, Vertex polygon)
     (Vertex polygon, Vertex polygon)
forall a b. (a -> b) -> a -> b
$
    \polygon
pg -> ( \(VertexIx polygon
i,Vertex polygon
u) -> let (VertexIx polygon
j,Vertex polygon
v) = polygon
pg polygon
-> Getting
     (VertexIx polygon, Vertex polygon)
     polygon
     (VertexIx polygon, Vertex polygon)
-> (VertexIx polygon, Vertex polygon)
forall s a. s -> Getting a s a -> a
^.VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
outerBoundaryVertexAt (VertexIx polygon -> VertexIx polygon
forall a. Enum a => a -> a
succ VertexIx polygon
i)(Indexed
   (VertexIx polygon)
   (Vertex polygon)
   (Const (VertexIx polygon, Vertex polygon) (Vertex polygon))
 -> polygon -> Const (VertexIx polygon, Vertex polygon) polygon)
-> (((VertexIx polygon, Vertex polygon)
     -> Const
          (VertexIx polygon, Vertex polygon)
          (VertexIx polygon, Vertex polygon))
    -> Indexed
         (VertexIx polygon)
         (Vertex polygon)
         (Const (VertexIx polygon, Vertex polygon) (Vertex polygon)))
-> Getting
     (VertexIx polygon, Vertex polygon)
     polygon
     (VertexIx polygon, Vertex polygon)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((VertexIx polygon, Vertex polygon)
 -> Const
      (VertexIx polygon, Vertex polygon)
      (VertexIx polygon, Vertex polygon))
-> Indexed
     (VertexIx polygon)
     (Vertex polygon)
     (Const (VertexIx polygon, Vertex polygon) (Vertex polygon))
forall i (p :: * -> * -> *) (f :: * -> *) s j t.
(Indexable i p, Functor f) =>
p (i, s) (f (j, t)) -> Indexed i s (f t)
withIndex
                       in ((VertexIx polygon
i,VertexIx polygon
j) , (Vertex polygon
u,Vertex polygon
v))
           ) ((VertexIx polygon, Vertex polygon)
 -> ((VertexIx polygon, VertexIx polygon),
     (Vertex polygon, Vertex polygon)))
-> NonEmpty (VertexIx polygon, Vertex polygon)
-> NonEmpty
     ((VertexIx polygon, VertexIx polygon),
      (Vertex polygon, Vertex polygon))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> IndexedGetting
  (VertexIx polygon)
  (NonEmptyDList (VertexIx polygon, Vertex polygon))
  polygon
  (Vertex polygon)
-> polygon -> NonEmpty (VertexIx polygon, Vertex polygon)
forall i a s.
IndexedGetting i (NonEmptyDList (i, a)) s a -> s -> NonEmpty (i, a)
itoNonEmptyOf IndexedGetting
  (VertexIx polygon)
  (NonEmptyDList (VertexIx polygon, Vertex polygon))
  polygon
  (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
outerBoundary polygon
pg
    -- \pg -> fmap ( \(i,u) -> (i,(u, pg ^.outerBoundaryVertexAt (succ i))) )
    --      . NonEmpty.fromList
    --      $ itoListOf outerBoundary pg
    -- this feels much more clunky than it should be somehow.
    -- I would like an 'itoNonEmptyOf'

  -- | Get the edge that has the given vertex as its starting edge
  --
  -- running time: \(O(1)\)
  outerBoundaryEdgeAt   :: VertexIx polygon
                        -> IndexedGetter (VertexIx polygon, VertexIx polygon) polygon
                                         (Vertex polygon, Vertex polygon)
  -- default implementation of outerBoundaryEdge. It achieves the
  -- desired running time when indexing is indeed constant.
  default outerBoundaryEdgeAt :: Enum (VertexIx polygon)
                              => VertexIx polygon
                              -> IndexedGetter (VertexIx polygon, VertexIx polygon) polygon
                                               (Vertex polygon, Vertex polygon)
  outerBoundaryEdgeAt VertexIx polygon
i = (polygon
 -> ((VertexIx polygon, VertexIx polygon),
     (Vertex polygon, Vertex polygon)))
-> Over' p f polygon (Vertex polygon, Vertex polygon)
forall i (p :: * -> * -> *) (f :: * -> *) s a.
(Indexable i p, Contravariant f) =>
(s -> (i, a)) -> Over' p f s a
ito ((polygon
  -> ((VertexIx polygon, VertexIx polygon),
      (Vertex polygon, Vertex polygon)))
 -> Over' p f polygon (Vertex polygon, Vertex polygon))
-> (polygon
    -> ((VertexIx polygon, VertexIx polygon),
        (Vertex polygon, Vertex polygon)))
-> Over' p f polygon (Vertex polygon, Vertex polygon)
forall a b. (a -> b) -> a -> b
$
    \polygon
pg -> let (VertexIx polygon
j,Vertex polygon
v) = polygon
pgpolygon
-> Getting
     (VertexIx polygon, Vertex polygon)
     polygon
     (VertexIx polygon, Vertex polygon)
-> (VertexIx polygon, Vertex polygon)
forall s a. s -> Getting a s a -> a
^.VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
outerBoundaryVertexAt (VertexIx polygon -> VertexIx polygon
forall a. Enum a => a -> a
succ VertexIx polygon
i)(Indexed
   (VertexIx polygon)
   (Vertex polygon)
   (Const (VertexIx polygon, Vertex polygon) (Vertex polygon))
 -> polygon -> Const (VertexIx polygon, Vertex polygon) polygon)
-> (((VertexIx polygon, Vertex polygon)
     -> Const
          (VertexIx polygon, Vertex polygon)
          (VertexIx polygon, Vertex polygon))
    -> Indexed
         (VertexIx polygon)
         (Vertex polygon)
         (Const (VertexIx polygon, Vertex polygon) (Vertex polygon)))
-> Getting
     (VertexIx polygon, Vertex polygon)
     polygon
     (VertexIx polygon, Vertex polygon)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((VertexIx polygon, Vertex polygon)
 -> Const
      (VertexIx polygon, Vertex polygon)
      (VertexIx polygon, Vertex polygon))
-> Indexed
     (VertexIx polygon)
     (Vertex polygon)
     (Const (VertexIx polygon, Vertex polygon) (Vertex polygon))
forall i (p :: * -> * -> *) (f :: * -> *) s j t.
(Indexable i p, Functor f) =>
p (i, s) (f (j, t)) -> Indexed i s (f t)
withIndex
           in ( (VertexIx polygon
i,VertexIx polygon
j), (polygon
pgpolygon
-> Getting (Vertex polygon) polygon (Vertex polygon)
-> Vertex polygon
forall s a. s -> Getting a s a -> a
^.VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
outerBoundaryVertexAt VertexIx polygon
i, Vertex polygon
v))


--------------------------------------------------------------------------------
-- end of te HasOuterBoundary class
--------------------------------------------------------------------------------

instance HasOuterBoundary polygon => HasOuterBoundary (polygon :+ extra) where
  outerBoundary :: IndexedTraversal1'
  (VertexIx (polygon :+ extra))
  (polygon :+ extra)
  (Vertex (polygon :+ extra))
outerBoundary = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (Vertex polygon) (f (Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon) (f (Vertex polygon))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> p (Vertex polygon) (f (Vertex polygon)) -> polygon -> f polygon
forall polygon.
HasOuterBoundary polygon =>
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
outerBoundary
  ccwOuterBoundaryFrom :: VertexIx (polygon :+ extra)
-> IndexedTraversal1'
     (VertexIx (polygon :+ extra))
     (polygon :+ extra)
     (Vertex (polygon :+ extra))
ccwOuterBoundaryFrom VertexIx (polygon :+ extra)
u = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (Vertex polygon) (f (Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon) (f (Vertex polygon))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> VertexIx polygon
-> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
ccwOuterBoundaryFrom VertexIx polygon
VertexIx (polygon :+ extra)
u
  cwOuterBoundaryFrom :: VertexIx (polygon :+ extra)
-> IndexedTraversal1'
     (VertexIx (polygon :+ extra))
     (polygon :+ extra)
     (Vertex (polygon :+ extra))
cwOuterBoundaryFrom VertexIx (polygon :+ extra)
u  = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (Vertex polygon) (f (Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon) (f (Vertex polygon))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> VertexIx polygon
-> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
cwOuterBoundaryFrom  VertexIx polygon
VertexIx (polygon :+ extra)
u
  outerBoundaryVertexAt :: VertexIx (polygon :+ extra)
-> IndexedGetter
     (VertexIx (polygon :+ extra))
     (polygon :+ extra)
     (Vertex (polygon :+ extra))
outerBoundaryVertexAt VertexIx (polygon :+ extra)
u = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (Vertex polygon) (f (Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon) (f (Vertex polygon))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
outerBoundaryVertexAt VertexIx polygon
VertexIx (polygon :+ extra)
u
  outerBoundaryEdges :: IndexedFold1
  (VertexIx (polygon :+ extra), VertexIx (polygon :+ extra))
  (polygon :+ extra)
  (Vertex (polygon :+ extra), Vertex (polygon :+ extra))
outerBoundaryEdges = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (Vertex polygon, Vertex polygon)
      (f (Vertex polygon, Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon, Vertex polygon)
     (f (Vertex polygon, Vertex polygon))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> p (Vertex polygon, Vertex polygon)
  (f (Vertex polygon, Vertex polygon))
-> polygon -> f polygon
forall polygon.
HasOuterBoundary polygon =>
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (Vertex polygon, Vertex polygon)
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (Vertex polygon, Vertex polygon)
outerBoundaryEdges
  outerBoundaryEdgeAt :: VertexIx (polygon :+ extra)
-> IndexedGetter
     (VertexIx (polygon :+ extra), VertexIx (polygon :+ extra))
     (polygon :+ extra)
     (Vertex (polygon :+ extra), Vertex (polygon :+ extra))
outerBoundaryEdgeAt VertexIx (polygon :+ extra)
u = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (Vertex polygon, Vertex polygon)
      (f (Vertex polygon, Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon, Vertex polygon)
     (f (Vertex polygon, Vertex polygon))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> VertexIx polygon
-> IndexedGetter
     (VertexIx polygon, VertexIx polygon)
     polygon
     (Vertex polygon, Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter
     (VertexIx polygon, VertexIx polygon)
     polygon
     (Vertex polygon, Vertex polygon)
outerBoundaryEdgeAt VertexIx polygon
VertexIx (polygon :+ extra)
u

--------------------------------------------------------------------------------
-- * HasOuterBoundary Helpers

-- | Yield the minimum  vertex of a polygon according to the given comparison function.
--
-- running time \( O(n) \)

-- | Yield the minimum  vertex of a polygon according to the given comparison function.
--
-- running time \( O(n) \)
minimumVertexBy     :: forall polygon. (HasOuterBoundary polygon)
                    => (Vertex polygon -> Vertex polygon -> Ordering)
                    -> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
minimumVertexBy :: forall polygon.
HasOuterBoundary polygon =>
(Vertex polygon -> Vertex polygon -> Ordering)
-> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
minimumVertexBy Vertex polygon -> Vertex polygon -> Ordering
cmp = ((p ~ (->)) =>
 (Vertex polygon -> f (Vertex polygon)) -> polygon -> f polygon)
-> (p (Vertex polygon) (f (Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon) (f (Vertex polygon))
-> polygon
-> f polygon
forall (p :: * -> * -> *) (q :: * -> * -> *) a b r.
Conjoined p =>
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
forall (q :: * -> * -> *) a b r.
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
conjoined (p ~ (->)) =>
(Vertex polygon -> f (Vertex polygon)) -> polygon -> f polygon
(Vertex polygon -> f (Vertex polygon)) -> polygon -> f polygon
Fold1 polygon (Vertex polygon)
go p (Vertex polygon) (f (Vertex polygon)) -> polygon -> f polygon
IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
igo
  where
    go :: Fold1 polygon (Vertex polygon)
    go :: Fold1 polygon (Vertex polygon)
go = (polygon -> First (Vertex polygon))
-> Fold1 polygon (Vertex polygon)
forall (f :: * -> *) s a. Foldable1 f => (s -> f a) -> Fold1 s a
folding1 ((polygon -> First (Vertex polygon))
 -> Fold1 polygon (Vertex polygon))
-> (polygon -> First (Vertex polygon))
-> Fold1 polygon (Vertex polygon)
forall a b. (a -> b) -> a -> b
$ Getting
  (Endo (Endo (Maybe (Vertex polygon)))) polygon (Vertex polygon)
-> (Vertex polygon -> Vertex polygon -> Ordering)
-> polygon
-> First (Vertex polygon)
forall {a} {a}.
Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> First a
f Getting
  (Endo (Endo (Maybe (Vertex polygon)))) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
outerBoundary Vertex polygon -> Vertex polygon -> Ordering
cmp

    igo :: IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
    igo :: IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
igo = (polygon -> First (VertexIx polygon, Vertex polygon))
-> Over p f polygon polygon (Vertex polygon) (Vertex polygon)
forall (f :: * -> *) i (p :: * -> * -> *) (g :: * -> *) s a t b.
(Foldable1 f, Indexable i p, Contravariant g, Apply g) =>
(s -> f (i, a)) -> Over p g s t a b
ifolding1 ((polygon -> First (VertexIx polygon, Vertex polygon))
 -> Over p f polygon polygon (Vertex polygon) (Vertex polygon))
-> (polygon -> First (VertexIx polygon, Vertex polygon))
-> Over p f polygon polygon (Vertex polygon) (Vertex polygon)
forall a b. (a -> b) -> a -> b
$ Getting
  (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
  polygon
  (VertexIx polygon, Vertex polygon)
-> ((VertexIx polygon, Vertex polygon)
    -> (VertexIx polygon, Vertex polygon) -> Ordering)
-> polygon
-> First (VertexIx polygon, Vertex polygon)
forall {a} {a}.
Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> First a
f (Indexed
  (VertexIx polygon)
  (Vertex polygon)
  (Const
     (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
     (Vertex polygon))
-> polygon
-> Const
     (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon)))) polygon
forall polygon.
HasOuterBoundary polygon =>
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
outerBoundary(Indexed
   (VertexIx polygon)
   (Vertex polygon)
   (Const
      (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
      (Vertex polygon))
 -> polygon
 -> Const
      (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon)))) polygon)
-> (((VertexIx polygon, Vertex polygon)
     -> Const
          (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
          (VertexIx polygon, Vertex polygon))
    -> Indexed
         (VertexIx polygon)
         (Vertex polygon)
         (Const
            (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
            (Vertex polygon)))
-> Getting
     (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
     polygon
     (VertexIx polygon, Vertex polygon)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((VertexIx polygon, Vertex polygon)
 -> Const
      (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
      (VertexIx polygon, Vertex polygon))
-> Indexed
     (VertexIx polygon)
     (Vertex polygon)
     (Const
        (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
        (Vertex polygon))
forall i (p :: * -> * -> *) (f :: * -> *) s j t.
(Indexable i p, Functor f) =>
p (i, s) (f (j, t)) -> Indexed i s (f t)
withIndex) (Vertex polygon -> Vertex polygon -> Ordering
cmp (Vertex polygon -> Vertex polygon -> Ordering)
-> ((VertexIx polygon, Vertex polygon) -> Vertex polygon)
-> (VertexIx polygon, Vertex polygon)
-> (VertexIx polygon, Vertex polygon)
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (VertexIx polygon, Vertex polygon) -> Vertex polygon
forall a b. (a, b) -> b
snd)

    f :: Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> First a
f Getting (Endo (Endo (Maybe a))) a a
boundary a -> a -> Ordering
cmp' = First a -> (a -> First a) -> Maybe a -> First a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ([Char] -> First a
forall a. HasCallStack => [Char] -> a
error [Char]
"minimumVertexBy: absurd") a -> First a
forall a. a -> First a
First
                    (Maybe a -> First a) -> (a -> Maybe a) -> a -> First a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> Maybe a
forall a s.
Getting (Endo (Endo (Maybe a))) s a
-> (a -> a -> Ordering) -> s -> Maybe a
minimumByOf Getting (Endo (Endo (Maybe a))) a a
boundary a -> a -> Ordering
cmp'

-- | Yield the maximum vertex of a polygon according to the given comparison function.
--
-- running time \( O(n) \)
maximumVertexBy     :: forall polygon. (HasOuterBoundary polygon)
                    => (Vertex polygon -> Vertex polygon -> Ordering)
                    -> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
maximumVertexBy :: forall polygon.
HasOuterBoundary polygon =>
(Vertex polygon -> Vertex polygon -> Ordering)
-> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
maximumVertexBy Vertex polygon -> Vertex polygon -> Ordering
cmp = ((p ~ (->)) =>
 (Vertex polygon -> f (Vertex polygon)) -> polygon -> f polygon)
-> (p (Vertex polygon) (f (Vertex polygon))
    -> polygon -> f polygon)
-> p (Vertex polygon) (f (Vertex polygon))
-> polygon
-> f polygon
forall (p :: * -> * -> *) (q :: * -> * -> *) a b r.
Conjoined p =>
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
forall (q :: * -> * -> *) a b r.
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
conjoined (p ~ (->)) =>
(Vertex polygon -> f (Vertex polygon)) -> polygon -> f polygon
(Vertex polygon -> f (Vertex polygon)) -> polygon -> f polygon
Fold1 polygon (Vertex polygon)
go p (Vertex polygon) (f (Vertex polygon)) -> polygon -> f polygon
IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
igo
  where
    go :: Fold1 polygon (Vertex polygon)
    go :: Fold1 polygon (Vertex polygon)
go = (polygon -> First (Vertex polygon))
-> Fold1 polygon (Vertex polygon)
forall (f :: * -> *) s a. Foldable1 f => (s -> f a) -> Fold1 s a
folding1 ((polygon -> First (Vertex polygon))
 -> Fold1 polygon (Vertex polygon))
-> (polygon -> First (Vertex polygon))
-> Fold1 polygon (Vertex polygon)
forall a b. (a -> b) -> a -> b
$ Getting
  (Endo (Endo (Maybe (Vertex polygon)))) polygon (Vertex polygon)
-> (Vertex polygon -> Vertex polygon -> Ordering)
-> polygon
-> First (Vertex polygon)
forall {a} {a}.
Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> First a
f Getting
  (Endo (Endo (Maybe (Vertex polygon)))) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
outerBoundary Vertex polygon -> Vertex polygon -> Ordering
cmp

    igo :: IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
    igo :: IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
igo = (polygon -> First (VertexIx polygon, Vertex polygon))
-> Over p f polygon polygon (Vertex polygon) (Vertex polygon)
forall (f :: * -> *) i (p :: * -> * -> *) (g :: * -> *) s a t b.
(Foldable1 f, Indexable i p, Contravariant g, Apply g) =>
(s -> f (i, a)) -> Over p g s t a b
ifolding1 ((polygon -> First (VertexIx polygon, Vertex polygon))
 -> Over p f polygon polygon (Vertex polygon) (Vertex polygon))
-> (polygon -> First (VertexIx polygon, Vertex polygon))
-> Over p f polygon polygon (Vertex polygon) (Vertex polygon)
forall a b. (a -> b) -> a -> b
$ Getting
  (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
  polygon
  (VertexIx polygon, Vertex polygon)
-> ((VertexIx polygon, Vertex polygon)
    -> (VertexIx polygon, Vertex polygon) -> Ordering)
-> polygon
-> First (VertexIx polygon, Vertex polygon)
forall {a} {a}.
Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> First a
f (Indexed
  (VertexIx polygon)
  (Vertex polygon)
  (Const
     (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
     (Vertex polygon))
-> polygon
-> Const
     (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon)))) polygon
forall polygon.
HasOuterBoundary polygon =>
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
outerBoundary(Indexed
   (VertexIx polygon)
   (Vertex polygon)
   (Const
      (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
      (Vertex polygon))
 -> polygon
 -> Const
      (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon)))) polygon)
-> (((VertexIx polygon, Vertex polygon)
     -> Const
          (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
          (VertexIx polygon, Vertex polygon))
    -> Indexed
         (VertexIx polygon)
         (Vertex polygon)
         (Const
            (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
            (Vertex polygon)))
-> Getting
     (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
     polygon
     (VertexIx polygon, Vertex polygon)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((VertexIx polygon, Vertex polygon)
 -> Const
      (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
      (VertexIx polygon, Vertex polygon))
-> Indexed
     (VertexIx polygon)
     (Vertex polygon)
     (Const
        (Endo (Endo (Maybe (VertexIx polygon, Vertex polygon))))
        (Vertex polygon))
forall i (p :: * -> * -> *) (f :: * -> *) s j t.
(Indexable i p, Functor f) =>
p (i, s) (f (j, t)) -> Indexed i s (f t)
withIndex) (Vertex polygon -> Vertex polygon -> Ordering
cmp (Vertex polygon -> Vertex polygon -> Ordering)
-> ((VertexIx polygon, Vertex polygon) -> Vertex polygon)
-> (VertexIx polygon, Vertex polygon)
-> (VertexIx polygon, Vertex polygon)
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (VertexIx polygon, Vertex polygon) -> Vertex polygon
forall a b. (a, b) -> b
snd)

    f :: Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> First a
f Getting (Endo (Endo (Maybe a))) a a
boundary a -> a -> Ordering
cmp' = First a -> (a -> First a) -> Maybe a -> First a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ([Char] -> First a
forall a. HasCallStack => [Char] -> a
error [Char]
"maximumVertexBy: absurd") a -> First a
forall a. a -> First a
First
                    (Maybe a -> First a) -> (a -> Maybe a) -> a -> First a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Getting (Endo (Endo (Maybe a))) a a
-> (a -> a -> Ordering) -> a -> Maybe a
forall a s.
Getting (Endo (Endo (Maybe a))) s a
-> (a -> a -> Ordering) -> s -> Maybe a
maximumByOf Getting (Endo (Endo (Maybe a))) a a
boundary a -> a -> Ordering
cmp'

-- | Compute the signed area times 2 of a simple polygon. The the
-- vertices are in clockwise order, the signed area will be negative,
-- if the verices are given in counter clockwise order, the area will
-- be positive.
--
-- running time: \(O(n)\)
signedArea2X      :: (Num r, HasOuterBoundary simplePolygon
                     , Point_ point 2 r
                     , Vertex simplePolygon ~ point
                     ) => simplePolygon -> r
signedArea2X :: forall r simplePolygon point.
(Num r, HasOuterBoundary simplePolygon, Point_ point 2 r,
 Vertex simplePolygon ~ point) =>
simplePolygon -> r
signedArea2X simplePolygon
poly = [r] -> r
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [ point
ppoint -> Getting r point r -> r
forall s a. s -> Getting a s a -> a
^.Getting r point r
forall (d :: Natural) point r.
(1 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int point r
xCoord r -> r -> r
forall a. Num a => a -> a -> a
* point
qpoint -> Getting r point r -> r
forall s a. s -> Getting a s a -> a
^.Getting r point r
forall (d :: Natural) point r.
(2 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int point r
yCoord r -> r -> r
forall a. Num a => a -> a -> a
- point
qpoint -> Getting r point r -> r
forall s a. s -> Getting a s a -> a
^.Getting r point r
forall (d :: Natural) point r.
(1 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int point r
xCoord r -> r -> r
forall a. Num a => a -> a -> a
* point
ppoint -> Getting r point r -> r
forall s a. s -> Getting a s a -> a
^.Getting r point r
forall (d :: Natural) point r.
(2 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int point r
yCoord
                        | (point
p,point
q) <- simplePolygon
poly simplePolygon
-> Getting (Endo [(point, point)]) simplePolygon (point, point)
-> [(point, point)]
forall s a. s -> Getting (Endo [a]) s a -> [a]
^..Getting (Endo [(point, point)]) simplePolygon (point, point)
((Vertex simplePolygon, Vertex simplePolygon)
 -> Const
      (Endo [(point, point)])
      (Vertex simplePolygon, Vertex simplePolygon))
-> simplePolygon -> Const (Endo [(point, point)]) simplePolygon
forall polygon.
HasOuterBoundary polygon =>
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (Vertex polygon, Vertex polygon)
IndexedFold1
  (VertexIx simplePolygon, VertexIx simplePolygon)
  simplePolygon
  (Vertex simplePolygon, Vertex simplePolygon)
outerBoundaryEdges ]

-- | Get the line segment representing the edge that has the given vertex as its starting edge
--
-- running time: \(O(1)\)
outerBoundaryEdgeSegmentAt   :: ( HasOuterBoundary polygon
                                , Vertex polygon ~ point
                                , Point_ point 2 r
                                )
                             => VertexIx polygon
                             -> IndexedGetter (VertexIx polygon, VertexIx polygon)
                                              polygon
                                              (ClosedLineSegment point)
outerBoundaryEdgeSegmentAt :: forall polygon point r.
(HasOuterBoundary polygon, Vertex polygon ~ point,
 Point_ point 2 r) =>
VertexIx polygon
-> IndexedGetter
     (VertexIx polygon, VertexIx polygon)
     polygon
     (ClosedLineSegment point)
outerBoundaryEdgeSegmentAt VertexIx polygon
i = VertexIx polygon
-> IndexedGetter
     (VertexIx polygon, VertexIx polygon)
     polygon
     (Vertex polygon, Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter
     (VertexIx polygon, VertexIx polygon)
     polygon
     (Vertex polygon, Vertex polygon)
outerBoundaryEdgeAt VertexIx polygon
i(p (point, point) (f (point, point)) -> polygon -> f polygon)
-> (p (ClosedLineSegment point) (f (ClosedLineSegment point))
    -> p (point, point) (f (point, point)))
-> p (ClosedLineSegment point) (f (ClosedLineSegment point))
-> polygon
-> f polygon
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((point, point) -> ClosedLineSegment point)
-> p (ClosedLineSegment point) (f (ClosedLineSegment point))
-> p (point, point) (f (point, point))
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to ((point -> point -> ClosedLineSegment point)
-> (point, point) -> ClosedLineSegment point
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry point -> point -> ClosedLineSegment point
forall point. point -> point -> ClosedLineSegment point
ClosedLineSegment)

-- | Get the line segments representing the outer boundary of the polygon.
outerBoundaryEdgeSegments :: forall polygon point r.
                             ( HasOuterBoundary polygon
                             , Vertex polygon ~ point
                             , Point_ point 2 r
                             )
                          => IndexedFold1 (VertexIx polygon,VertexIx polygon)
                                          polygon
                                          (ClosedLineSegment point)
outerBoundaryEdgeSegments :: forall polygon point r.
(HasOuterBoundary polygon, Vertex polygon ~ point,
 Point_ point 2 r) =>
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (ClosedLineSegment point)
outerBoundaryEdgeSegments = p (point, point) (f (point, point)) -> polygon -> f polygon
p (Vertex polygon, Vertex polygon)
  (f (Vertex polygon, Vertex polygon))
-> polygon -> f polygon
forall polygon.
HasOuterBoundary polygon =>
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (Vertex polygon, Vertex polygon)
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (Vertex polygon, Vertex polygon)
outerBoundaryEdges (p (point, point) (f (point, point)) -> polygon -> f polygon)
-> (p (ClosedLineSegment point) (f (ClosedLineSegment point))
    -> p (point, point) (f (point, point)))
-> p (ClosedLineSegment point) (f (ClosedLineSegment point))
-> polygon
-> f polygon
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((point, point) -> ClosedLineSegment point)
-> p (ClosedLineSegment point) (f (ClosedLineSegment point))
-> p (point, point) (f (point, point))
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to ((point -> point -> ClosedLineSegment point)
-> (point, point) -> ClosedLineSegment point
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry point -> point -> ClosedLineSegment point
forall point. point -> point -> ClosedLineSegment point
ClosedLineSegment)


-- | A fold that associates each vertex on the boundary with its
-- predecessor and successor (in that order) along the boundary.
outerBoundaryWithNeighbours :: ( HasOuterBoundary polygon
                               , VertexIx polygon ~ Int
                               )
                            =>  IndexedFold1 (VertexIx polygon,
                                                  (VertexIx polygon, VertexIx polygon))
                                        polygon
                                        (Vertex polygon, (Vertex polygon, Vertex polygon))
outerBoundaryWithNeighbours :: forall polygon.
(HasOuterBoundary polygon, VertexIx polygon ~ Int) =>
IndexedFold1
  (VertexIx polygon, (VertexIx polygon, VertexIx polygon))
  polygon
  (Vertex polygon, (Vertex polygon, Vertex polygon))
outerBoundaryWithNeighbours = (polygon
 -> NonEmpty
      ((Int, (Int, Int)),
       (Vertex polygon, (Vertex polygon, Vertex polygon))))
-> Over
     p
     f
     polygon
     polygon
     (Vertex polygon, (Vertex polygon, Vertex polygon))
     (Vertex polygon, (Vertex polygon, Vertex polygon))
forall (f :: * -> *) i (p :: * -> * -> *) (g :: * -> *) s a t b.
(Foldable1 f, Indexable i p, Contravariant g, Apply g) =>
(s -> f (i, a)) -> Over p g s t a b
ifolding1 ((polygon
  -> NonEmpty
       ((Int, (Int, Int)),
        (Vertex polygon, (Vertex polygon, Vertex polygon))))
 -> Over
      p
      f
      polygon
      polygon
      (Vertex polygon, (Vertex polygon, Vertex polygon))
      (Vertex polygon, (Vertex polygon, Vertex polygon)))
-> (polygon
    -> NonEmpty
         ((Int, (Int, Int)),
          (Vertex polygon, (Vertex polygon, Vertex polygon))))
-> Over
     p
     f
     polygon
     polygon
     (Vertex polygon, (Vertex polygon, Vertex polygon))
     (Vertex polygon, (Vertex polygon, Vertex polygon))
forall a b. (a -> b) -> a -> b
$
    \polygon
pg -> polygon
-> VertexIx polygon
-> (VertexIx polygon, Vertex polygon)
-> ((VertexIx polygon, (VertexIx polygon, VertexIx polygon)),
    (Vertex polygon, (Vertex polygon, Vertex polygon)))
forall {s} {a}.
(HasOuterBoundary s, Integral (VertexIx s)) =>
s
-> VertexIx s
-> (VertexIx s, a)
-> ((VertexIx s, (VertexIx s, VertexIx s)),
    (a, (Vertex s, Vertex s)))
f polygon
pg (polygon -> Int
forall graph. HasVertices' graph => graph -> Int
numVertices polygon
pg) ((Int, Vertex polygon)
 -> ((Int, (Int, Int)),
     (Vertex polygon, (Vertex polygon, Vertex polygon))))
-> NonEmpty (Int, Vertex polygon)
-> NonEmpty
     ((Int, (Int, Int)),
      (Vertex polygon, (Vertex polygon, Vertex polygon)))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> IndexedGetting
  Int (NonEmptyDList (Int, Vertex polygon)) polygon (Vertex polygon)
-> polygon -> NonEmpty (Int, Vertex polygon)
forall i a s.
IndexedGetting i (NonEmptyDList (i, a)) s a -> s -> NonEmpty (i, a)
itoNonEmptyOf IndexedGetting
  Int (NonEmptyDList (Int, Vertex polygon)) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
IndexedTraversal1' (VertexIx polygon) polygon (Vertex polygon)
outerBoundary polygon
pg
  where
    f :: s
-> VertexIx s
-> (VertexIx s, a)
-> ((VertexIx s, (VertexIx s, VertexIx s)),
    (a, (Vertex s, Vertex s)))
f s
pg VertexIx s
n (VertexIx s
i,a
u) = let (VertexIx s
j,Vertex s
v) = s
pgs
-> Getting (VertexIx s, Vertex s) s (VertexIx s, Vertex s)
-> (VertexIx s, Vertex s)
forall s a. s -> Getting a s a -> a
^.VertexIx s -> IndexedGetter (VertexIx s) s (Vertex s)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
outerBoundaryVertexAt ((VertexIx s
iVertexIx s -> VertexIx s -> VertexIx s
forall a. Num a => a -> a -> a
-VertexIx s
1) VertexIx s -> VertexIx s -> VertexIx s
forall a. Integral a => a -> a -> a
`mod` VertexIx s
n)(Indexed
   (VertexIx s) (Vertex s) (Const (VertexIx s, Vertex s) (Vertex s))
 -> s -> Const (VertexIx s, Vertex s) s)
-> (((VertexIx s, Vertex s)
     -> Const (VertexIx s, Vertex s) (VertexIx s, Vertex s))
    -> Indexed
         (VertexIx s) (Vertex s) (Const (VertexIx s, Vertex s) (Vertex s)))
-> Getting (VertexIx s, Vertex s) s (VertexIx s, Vertex s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((VertexIx s, Vertex s)
 -> Const (VertexIx s, Vertex s) (VertexIx s, Vertex s))
-> Indexed
     (VertexIx s) (Vertex s) (Const (VertexIx s, Vertex s) (Vertex s))
forall i (p :: * -> * -> *) (f :: * -> *) s j t.
(Indexable i p, Functor f) =>
p (i, s) (f (j, t)) -> Indexed i s (f t)
withIndex
                       (VertexIx s
k,Vertex s
w) = s
pgs
-> Getting (VertexIx s, Vertex s) s (VertexIx s, Vertex s)
-> (VertexIx s, Vertex s)
forall s a. s -> Getting a s a -> a
^.VertexIx s -> IndexedGetter (VertexIx s) s (Vertex s)
forall polygon.
HasOuterBoundary polygon =>
VertexIx polygon
-> IndexedGetter (VertexIx polygon) polygon (Vertex polygon)
outerBoundaryVertexAt ((VertexIx s
iVertexIx s -> VertexIx s -> VertexIx s
forall a. Num a => a -> a -> a
+VertexIx s
1) VertexIx s -> VertexIx s -> VertexIx s
forall a. Integral a => a -> a -> a
`mod` VertexIx s
n)(Indexed
   (VertexIx s) (Vertex s) (Const (VertexIx s, Vertex s) (Vertex s))
 -> s -> Const (VertexIx s, Vertex s) s)
-> (((VertexIx s, Vertex s)
     -> Const (VertexIx s, Vertex s) (VertexIx s, Vertex s))
    -> Indexed
         (VertexIx s) (Vertex s) (Const (VertexIx s, Vertex s) (Vertex s)))
-> Getting (VertexIx s, Vertex s) s (VertexIx s, Vertex s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.((VertexIx s, Vertex s)
 -> Const (VertexIx s, Vertex s) (VertexIx s, Vertex s))
-> Indexed
     (VertexIx s) (Vertex s) (Const (VertexIx s, Vertex s) (Vertex s))
forall i (p :: * -> * -> *) (f :: * -> *) s j t.
(Indexable i p, Functor f) =>
p (i, s) (f (j, t)) -> Indexed i s (f t)
withIndex
                   in ( (VertexIx s
i, (VertexIx s
j,VertexIx s
k)) , (a
u, (Vertex s
v, Vertex s
w)) )

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

-- | A hole is a simple polygon
type Hole polygon = SimplePolygonF (HoleF polygon) (Vertex polygon)

-- | Accessing the holes in a polygon (if there are any.)
--
-- the default implementation assumes there are no holes
class VertexContainer (HoleF polygon) (Vertex polygon) => HasHoles polygon where
  {-# MINIMAL #-}

  -- | Type we use to index holes.
  type HoleIx polygon :: Type
  type HoleIx polygon = Void

  -- | The functor used in the holes
  type HoleF polygon :: Type -> Type
  type HoleF polygon = Cyclic NonEmptyVector

  -- ^ Traversal over the holes in the polygon. Each hole is a simple polygon.
  holes :: IndexedTraversal' (HoleIx polygon) polygon (Hole polygon)
  holes = \p (Hole polygon) (f (Hole polygon))
_ polygon
pg -> polygon -> f polygon
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure polygon
pg

  -- ^ Access a particular hole. This is supposed to be an affine traversal.
  holeAt   :: HoleIx polygon -> IndexedTraversal' (HoleIx polygon) polygon (Hole polygon)
  holeAt HoleIx polygon
_ = \p (Hole polygon) (f (Hole polygon))
_ polygon
pg -> polygon -> f polygon
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure polygon
pg


-- | A class representing (planar) polygons. The edges of the polygon
-- may not intersect.
class ( HasOuterBoundary polygon
      , Vertex      polygon ~ point
      , Point_ point 2 r
      , NumType polygon ~ r, Dimension polygon ~ 2
      , HasHoles polygon
      ) => Polygon_ polygon point r where

    -- signedArea2X pg -


  -- | Finds the extreme points, minimum and maximum, in a given direction
  --
  -- running time: \(O(n)\)
  extremes      :: (Num r, Ord r, Point_ point 2 r)
                => Vector 2 r -> polygon -> (point, point)
  extremes Vector 2 r
u polygon
pg = ( Getting (First point) polygon point -> polygon -> point
forall a s. Getting (First a) s a -> s -> a
first1Of ((Vertex polygon -> Vertex polygon -> Ordering)
-> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
(Vertex polygon -> Vertex polygon -> Ordering)
-> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
minimumVertexBy (Vector 2 r -> point -> point -> Ordering
forall r point.
(Num r, Ord r, Point_ point 2 r) =>
Vector 2 r -> point -> point -> Ordering
cmpInDirection2 Vector 2 r
u)) polygon
pg
                  , Getting (First point) polygon point -> polygon -> point
forall a s. Getting (First a) s a -> s -> a
first1Of ((Vertex polygon -> Vertex polygon -> Ordering)
-> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
forall polygon.
HasOuterBoundary polygon =>
(Vertex polygon -> Vertex polygon -> Ordering)
-> IndexedFold1 (VertexIx polygon) polygon (Vertex polygon)
maximumVertexBy (Vector 2 r -> point -> point -> Ordering
forall r point.
(Num r, Ord r, Point_ point 2 r) =>
Vector 2 r -> point -> point -> Ordering
cmpInDirection2 Vector 2 r
u)) polygon
pg
                  )

  -- | Given a vertexIdx v; get an IndexedLens to access the CCW predecessor of v
  ccwPredecessorOf :: VertexIx polygon
                   -> IndexedLens' (VertexIx polygon) polygon (Vertex polygon)

  -- | Given a vertexIdx v; get an IndexedLens to access the CCW predecessor of v
  ccwSuccessorOf :: VertexIx polygon
                 -> IndexedLens' (VertexIx polygon) polygon (Vertex polygon)


--------------------------------------------------------------------------------
-- end of te Polygon_ class
--------------------------------------------------------------------------------

instance HasHoles polygon => HasHoles (polygon :+ extra) where
  type HoleIx (polygon :+ extra) = HoleIx polygon
  type HoleF  (polygon :+ extra) = HoleF  polygon
  holes :: IndexedTraversal'
  (HoleIx (polygon :+ extra))
  (polygon :+ extra)
  (Hole (polygon :+ extra))
holes    = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (SimplePolygonF (HoleF polygon) (Vertex polygon))
      (f (SimplePolygonF (HoleF polygon) (Vertex polygon)))
    -> polygon -> f polygon)
-> p (SimplePolygonF (HoleF polygon) (Vertex polygon))
     (f (SimplePolygonF (HoleF polygon) (Vertex polygon)))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> p (SimplePolygonF (HoleF polygon) (Vertex polygon))
  (f (SimplePolygonF (HoleF polygon) (Vertex polygon)))
-> polygon -> f polygon
forall polygon.
HasHoles polygon =>
IndexedTraversal' (HoleIx polygon) polygon (Hole polygon)
IndexedTraversal'
  (HoleIx polygon)
  polygon
  (SimplePolygonF (HoleF polygon) (Vertex polygon))
holes
  holeAt :: HoleIx (polygon :+ extra)
-> IndexedTraversal'
     (HoleIx (polygon :+ extra))
     (polygon :+ extra)
     (Hole (polygon :+ extra))
holeAt HoleIx (polygon :+ extra)
i = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p (SimplePolygonF (HoleF polygon) (Vertex polygon))
      (f (SimplePolygonF (HoleF polygon) (Vertex polygon)))
    -> polygon -> f polygon)
-> p (SimplePolygonF (HoleF polygon) (Vertex polygon))
     (f (SimplePolygonF (HoleF polygon) (Vertex polygon)))
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> HoleIx polygon
-> IndexedTraversal'
     (HoleIx polygon)
     polygon
     (SimplePolygonF (HoleF polygon) (Vertex polygon))
forall polygon.
HasHoles polygon =>
HoleIx polygon
-> IndexedTraversal' (HoleIx polygon) polygon (Hole polygon)
holeAt HoleIx polygon
HoleIx (polygon :+ extra)
i

instance Polygon_ polygon point r  => Polygon_ (polygon :+ extra) point r where
  extremes :: (Num r, Ord r, Point_ point 2 r) =>
Vector 2 r -> (polygon :+ extra) -> (point, point)
extremes Vector 2 r
u = Vector 2 r -> polygon -> (point, point)
forall polygon point r.
(Polygon_ polygon point r, Num r, Ord r, Point_ point 2 r) =>
Vector 2 r -> polygon -> (point, point)
extremes Vector 2 r
u (polygon -> (point, point))
-> ((polygon :+ extra) -> polygon)
-> (polygon :+ extra)
-> (point, point)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Getting polygon (polygon :+ extra) polygon
-> (polygon :+ extra) -> polygon
forall s (m :: * -> *) a. MonadReader s m => Getting a s a -> m a
view Getting polygon (polygon :+ extra) polygon
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core
  ccwPredecessorOf :: VertexIx (polygon :+ extra)
-> IndexedLens'
     (VertexIx (polygon :+ extra))
     (polygon :+ extra)
     (Vertex (polygon :+ extra))
ccwPredecessorOf VertexIx (polygon :+ extra)
u = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p point (f point) -> polygon -> f polygon)
-> p point (f point)
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> VertexIx polygon
-> IndexedLens' (VertexIx polygon) polygon (Vertex polygon)
forall polygon point r.
Polygon_ polygon point r =>
VertexIx polygon
-> IndexedLens' (VertexIx polygon) polygon (Vertex polygon)
ccwPredecessorOf VertexIx polygon
VertexIx (polygon :+ extra)
u
  ccwSuccessorOf :: VertexIx (polygon :+ extra)
-> IndexedLens'
     (VertexIx (polygon :+ extra))
     (polygon :+ extra)
     (Vertex (polygon :+ extra))
ccwSuccessorOf   VertexIx (polygon :+ extra)
u = (polygon -> f polygon)
-> (polygon :+ extra) -> f (polygon :+ extra)
forall core extra core' (f :: * -> *).
Functor f =>
(core -> f core') -> (core :+ extra) -> f (core' :+ extra)
core ((polygon -> f polygon)
 -> (polygon :+ extra) -> f (polygon :+ extra))
-> (p point (f point) -> polygon -> f polygon)
-> p point (f point)
-> (polygon :+ extra)
-> f (polygon :+ extra)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> VertexIx polygon
-> IndexedLens' (VertexIx polygon) polygon (Vertex polygon)
forall polygon point r.
Polygon_ polygon point r =>
VertexIx polygon
-> IndexedLens' (VertexIx polygon) polygon (Vertex polygon)
ccwSuccessorOf   VertexIx polygon
VertexIx (polygon :+ extra)
u

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

instance (Point_ point 2 r, Num r, Eq r) => HasOuterBoundary (Triangle point) where
  outerBoundaryVertexAt :: VertexIx (Triangle point)
-> IndexedGetter
     (VertexIx (Triangle point))
     (Triangle point)
     (Vertex (Triangle point))
outerBoundaryVertexAt VertexIx (Triangle point)
i = Traversing p f (Triangle point) (Triangle point) point point
-> Over p f (Triangle point) (Triangle point) point point
forall (p :: * -> * -> *) (f :: * -> *) s t a.
(HasCallStack, Conjoined p, Functor f) =>
Traversing p f s t a a -> Over p f s t a a
singular (VertexIx (Triangle point)
-> IndexedTraversal'
     (VertexIx (Triangle point))
     (Triangle point)
     (Vertex (Triangle point))
forall graph.
HasVertices' graph =>
VertexIx graph
-> IndexedTraversal' (VertexIx graph) graph (Vertex graph)
vertexAt (VertexIx (Triangle point)
 -> IndexedTraversal'
      (VertexIx (Triangle point))
      (Triangle point)
      (Vertex (Triangle point)))
-> VertexIx (Triangle point)
-> IndexedTraversal'
     (VertexIx (Triangle point))
     (Triangle point)
     (Vertex (Triangle point))
forall a b. (a -> b) -> a -> b
$ VertexIx (Triangle point)
i VertexIx (Triangle point)
-> VertexIx (Triangle point) -> VertexIx (Triangle point)
forall a. Integral a => a -> a -> a
`mod` Int
VertexIx (Triangle point)
3)
  outerBoundary :: IndexedTraversal1'
  (VertexIx (Triangle point))
  (Triangle point)
  (Vertex (Triangle point))
outerBoundary = p (Vertex (Triangle point)) (f (Vertex (Triangle point)))
-> Triangle point -> f (Triangle point)
forall graph graph'.
HasVertices graph graph' =>
IndexedTraversal1
  (VertexIx graph) graph graph' (Vertex graph) (Vertex graph')
IndexedTraversal1'
  (VertexIx (Triangle point))
  (Triangle point)
  (Vertex (Triangle point))
vertices
  ccwOuterBoundaryFrom :: VertexIx (Triangle point)
-> IndexedTraversal1'
     (VertexIx (Triangle point))
     (Triangle point)
     (Vertex (Triangle point))
ccwOuterBoundaryFrom VertexIx (Triangle point)
i = \p (Vertex (Triangle point)) (f (Vertex (Triangle point)))
pvFv Triangle point
tri -> Triangle point
-> Iso' (Triangle point) (Triangle point)
-> Iso' (Triangle point) (Triangle point)
-> IndexedTraversal1' Int (Triangle point) point
-> IndexedTraversal1' Int (Triangle point) point
forall point r.
(Point_ point 2 r, Num r, Eq r) =>
Triangle point
-> Iso' (Triangle point) (Triangle point)
-> Iso' (Triangle point) (Triangle point)
-> IndexedTraversal1' Int (Triangle point) point
-> IndexedTraversal1' Int (Triangle point) point
ifCCW Triangle point
tri p (Triangle point) (f (Triangle point))
-> p (Triangle point) (f (Triangle point))
forall a. a -> a
Iso' (Triangle point) (Triangle point)
id p (Triangle point) (f (Triangle point))
-> p (Triangle point) (f (Triangle point))
forall a. Reversing a => Iso' a a
Iso' (Triangle point) (Triangle point)
reversed (Int -> IndexedTraversal1' Int (Triangle point) point
forall point. Int -> IndexedTraversal1' Int (Triangle point) point
traverseTriangleFrom Int
VertexIx (Triangle point)
i) p point (f point)
p (Vertex (Triangle point)) (f (Vertex (Triangle point)))
pvFv Triangle point
tri
  cwOuterBoundaryFrom :: VertexIx (Triangle point)
-> IndexedTraversal1'
     (VertexIx (Triangle point))
     (Triangle point)
     (Vertex (Triangle point))
cwOuterBoundaryFrom  VertexIx (Triangle point)
i = \p (Vertex (Triangle point)) (f (Vertex (Triangle point)))
pvFv Triangle point
tri -> Triangle point
-> Iso' (Triangle point) (Triangle point)
-> Iso' (Triangle point) (Triangle point)
-> IndexedTraversal1' Int (Triangle point) point
-> IndexedTraversal1' Int (Triangle point) point
forall point r.
(Point_ point 2 r, Num r, Eq r) =>
Triangle point
-> Iso' (Triangle point) (Triangle point)
-> Iso' (Triangle point) (Triangle point)
-> IndexedTraversal1' Int (Triangle point) point
-> IndexedTraversal1' Int (Triangle point) point
ifCCW Triangle point
tri p (Triangle point) (f (Triangle point))
-> p (Triangle point) (f (Triangle point))
forall a. Reversing a => Iso' a a
Iso' (Triangle point) (Triangle point)
reversed p (Triangle point) (f (Triangle point))
-> p (Triangle point) (f (Triangle point))
forall a. a -> a
Iso' (Triangle point) (Triangle point)
id (Int -> IndexedTraversal1' Int (Triangle point) point
forall point. Int -> IndexedTraversal1' Int (Triangle point) point
traverseTriangleFrom Int
VertexIx (Triangle point)
i) p point (f point)
p (Vertex (Triangle point)) (f (Vertex (Triangle point)))
pvFv Triangle point
tri

-- | Helper to reverse the orientation of the traversal depending on the orientation
-- of the triangle.
ifCCW         :: (Point_ point 2 r, Num r, Eq r)
              => Triangle point
              -> Iso' (Triangle point) (Triangle point)
              -> Iso' (Triangle point) (Triangle point)
              -> IndexedTraversal1' Int (Triangle point) point
              -> IndexedTraversal1' Int (Triangle point) point
ifCCW :: forall point r.
(Point_ point 2 r, Num r, Eq r) =>
Triangle point
-> Iso' (Triangle point) (Triangle point)
-> Iso' (Triangle point) (Triangle point)
-> IndexedTraversal1' Int (Triangle point) point
-> IndexedTraversal1' Int (Triangle point) point
ifCCW Triangle point
tri Iso' (Triangle point) (Triangle point)
f Iso' (Triangle point) (Triangle point)
g IndexedTraversal1' Int (Triangle point) point
t
  | (\r
x -> r
x r -> r -> Bool
forall a. Eq a => a -> a -> Bool
== r -> r
forall a. Num a => a -> a
abs r
x) (r -> Bool) -> (Triangle point -> r) -> Triangle point -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Triangle point -> r
forall r point triangle.
(Num r, Point_ point 2 r, Triangle_ triangle point) =>
triangle -> r
triangleSignedArea2X (Triangle point -> Bool) -> Triangle point -> Bool
forall a b. (a -> b) -> a -> b
$ Triangle point
tri = (Triangle point -> f (Triangle point))
-> Triangle point -> f (Triangle point)
Iso' (Triangle point) (Triangle point)
f((Triangle point -> f (Triangle point))
 -> Triangle point -> f (Triangle point))
-> (p point (f point) -> Triangle point -> f (Triangle point))
-> p point (f point)
-> Triangle point
-> f (Triangle point)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.p point (f point) -> Triangle point -> f (Triangle point)
IndexedTraversal1' Int (Triangle point) point
t
  | Bool
otherwise                                       = (Triangle point -> f (Triangle point))
-> Triangle point -> f (Triangle point)
Iso' (Triangle point) (Triangle point)
g((Triangle point -> f (Triangle point))
 -> Triangle point -> f (Triangle point))
-> (p point (f point) -> Triangle point -> f (Triangle point))
-> p point (f point)
-> Triangle point
-> f (Triangle point)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.p point (f point) -> Triangle point -> f (Triangle point)
IndexedTraversal1' Int (Triangle point) point
t

-- | Traverse the boundary of a triangle from the given starting vertex
traverseTriangleFrom   :: forall point. Int -> IndexedTraversal1' Int (Triangle point) point
traverseTriangleFrom :: forall point. Int -> IndexedTraversal1' Int (Triangle point) point
traverseTriangleFrom Int
i = ((p ~ (->)) =>
 (point -> f point) -> Triangle point -> f (Triangle point))
-> (p point (f point) -> Triangle point -> f (Triangle point))
-> p point (f point)
-> Triangle point
-> f (Triangle point)
forall (p :: * -> * -> *) (q :: * -> * -> *) a b r.
Conjoined p =>
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
forall (q :: * -> * -> *) a b r.
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
conjoined (p ~ (->)) =>
(point -> f point) -> Triangle point -> f (Triangle point)
(point -> f point) -> Triangle point -> f (Triangle point)
forall (f :: * -> *).
Apply f =>
(point -> f point) -> Triangle point -> f (Triangle point)
trav ((Int -> point -> f point) -> Triangle point -> f (Triangle point)
forall (f :: * -> *).
Apply f =>
(Int -> point -> f point) -> Triangle point -> f (Triangle point)
itrav ((Int -> point -> f point) -> Triangle point -> f (Triangle point))
-> (p point (f point) -> Int -> point -> f point)
-> p point (f point)
-> Triangle point
-> f (Triangle point)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. p point (f point) -> Int -> point -> f point
forall a b. p a b -> Int -> a -> b
forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed)
  where
    trav :: Apply.Apply f => (point -> f point) -> Triangle point -> f (Triangle point)
    trav :: forall (f :: * -> *).
Apply f =>
(point -> f point) -> Triangle point -> f (Triangle point)
trav point -> f point
f (Triangle point
a point
b point
c) = case Int
i Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
3 of
                                Int
0 -> point -> point -> point -> Triangle point
forall point. point -> point -> point -> Triangle point
Triangle
                                      (point -> point -> point -> Triangle point)
-> f point -> f (point -> point -> Triangle point)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> point -> f point
f point
a f (point -> point -> Triangle point)
-> f point -> f (point -> Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> point -> f point
f point
b f (point -> Triangle point) -> f point -> f (Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> point -> f point
f point
c
                                Int
1 -> (\point
b' point
c' point
a' -> point -> point -> point -> Triangle point
forall point. point -> point -> point -> Triangle point
Triangle point
a' point
b' point
c')
                                     (point -> point -> point -> Triangle point)
-> f point -> f (point -> point -> Triangle point)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> point -> f point
f point
b f (point -> point -> Triangle point)
-> f point -> f (point -> Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> point -> f point
f point
c f (point -> Triangle point) -> f point -> f (Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> point -> f point
f point
a
                                Int
_ -> (\point
c' point
a' point
b' -> point -> point -> point -> Triangle point
forall point. point -> point -> point -> Triangle point
Triangle point
a' point
b' point
c')
                                     (point -> point -> point -> Triangle point)
-> f point -> f (point -> point -> Triangle point)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> point -> f point
f point
c f (point -> point -> Triangle point)
-> f point -> f (point -> Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> point -> f point
f point
a f (point -> Triangle point) -> f point -> f (Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> point -> f point
f point
b
    itrav :: Apply.Apply f => (Int -> point -> f point) -> Triangle point -> f (Triangle point)
    itrav :: forall (f :: * -> *).
Apply f =>
(Int -> point -> f point) -> Triangle point -> f (Triangle point)
itrav Int -> point -> f point
f (Triangle point
a point
b point
c) = case Int
i Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
3 of
                                 Int
0 -> point -> point -> point -> Triangle point
forall point. point -> point -> point -> Triangle point
Triangle
                                      (point -> point -> point -> Triangle point)
-> f point -> f (point -> point -> Triangle point)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> point -> f point
f Int
0 point
a f (point -> point -> Triangle point)
-> f point -> f (point -> Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> Int -> point -> f point
f Int
1 point
b f (point -> Triangle point) -> f point -> f (Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> Int -> point -> f point
f Int
2 point
c
                                 Int
1 -> (\point
b' point
c' point
a' -> point -> point -> point -> Triangle point
forall point. point -> point -> point -> Triangle point
Triangle point
a' point
b' point
c')
                                      (point -> point -> point -> Triangle point)
-> f point -> f (point -> point -> Triangle point)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> point -> f point
f Int
1 point
b f (point -> point -> Triangle point)
-> f point -> f (point -> Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> Int -> point -> f point
f Int
2 point
c f (point -> Triangle point) -> f point -> f (Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> Int -> point -> f point
f Int
0 point
a
                                 Int
_ -> (\point
c' point
a' point
b' -> point -> point -> point -> Triangle point
forall point. point -> point -> point -> Triangle point
Triangle point
a' point
b' point
c')
                                      (point -> point -> point -> Triangle point)
-> f point -> f (point -> point -> Triangle point)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> point -> f point
f Int
2 point
c f (point -> point -> Triangle point)
-> f point -> f (point -> Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> Int -> point -> f point
f Int
0 point
a f (point -> Triangle point) -> f point -> f (Triangle point)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
Apply.<.> Int -> point -> f point
f Int
1 point
b


-- We need Rectanlge to be an instance of HasVertices' first; but that requires
-- that vertices is a fold rather than a traversal.
-- instance (Point_ point 2 r, Num r) => HasOuterBoundary (Rectangle point) where
--   outerBoundaryVertexAt i = undefined
--   ccwOuterBoundaryFrom i = undefined
--   cwOuterBoundaryFrom i = undefined



-- data MultiPG
-- data SimplePG

-- class DerivingStrategyPolygon strat polygon point r | polygon point r -> strat where
--   derivedArea :: Fractional r => polygon point r -> r

-- instance (SimplePolygon_ polygon point r) =>  DerivingStrategyPolygon SimplePG polygon point r where
--   derivedArea = signedArea -- abs . signedArea
--                 -- since the polygon is stored in CCW order, there is no need to actually
--                 -- use the absolute value.


{-
-}


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

-- | A Class for polygon types that support returning a point inside the polygon.
class HasPickPoint polygon r | polygon -> r where
  -- | Returns a point in the interior of the polygon
  pointInteriorTo :: polygon -> Point 2 r


instance (Point_ vertex 2 r, Fractional r, Eq r) => HasPickPoint (Triangle vertex) r where
  pointInteriorTo :: Triangle vertex -> Point 2 r
pointInteriorTo = Triangle vertex -> Point 2 r
forall {b} {simplePolygon}.
(Dimension b ~ 2, Dimension (Vertex simplePolygon) ~ 2,
 NumType (Vertex simplePolygon) ~ NumType b,
 ConstructablePoint_ b 2 (NumType b), Fractional (NumType b),
 HasOuterBoundary simplePolygon,
 Point_ (Vertex simplePolygon) 2 (NumType b)) =>
simplePolygon -> b
centroid'
    where
      -- TODO: this is just the definition of centroid, copied over from
      -- the simple polygon class. Avoid the code duplication, by splititng the SimplePolygon_
      -- class
      centroid' :: simplePolygon -> b
centroid' simplePolygon
poly = Vector
  (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> b
forall point (d :: Natural) r.
ConstructablePoint_ point d r =>
Vector d r -> point
fromVector (Vector
   (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
 -> b)
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> b
forall a b. (a -> b) -> a -> b
$ [Vector
   (Dimension (Vertex simplePolygon))
   (NumType (Vertex simplePolygon))]
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
sum' [Vector
   (Dimension (Vertex simplePolygon))
   (NumType (Vertex simplePolygon))]
xs Vector
  (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> NumType (Vertex simplePolygon)
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall vector (d :: Natural) r.
(Vector_ vector d r, Fractional r) =>
vector -> r -> vector
^/ (NumType (Vertex simplePolygon)
3 NumType (Vertex simplePolygon)
-> NumType (Vertex simplePolygon) -> NumType (Vertex simplePolygon)
forall a. Num a => a -> a -> a
* simplePolygon -> NumType (Vertex simplePolygon)
forall r simplePolygon point.
(Num r, HasOuterBoundary simplePolygon, Point_ point 2 r,
 Vertex simplePolygon ~ point) =>
simplePolygon -> r
signedArea2X simplePolygon
poly)
        where
           xs :: [Vector
   (Dimension (Vertex simplePolygon))
   (NumType (Vertex simplePolygon))]
xs = [ (Vertex simplePolygon
pVertex simplePolygon
-> Getting
     (Vector
        (Dimension (Vertex simplePolygon))
        (NumType (Vertex simplePolygon)))
     (Vertex simplePolygon)
     (Vector
        (Dimension (Vertex simplePolygon))
        (NumType (Vertex simplePolygon)))
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall s a. s -> Getting a s a -> a
^.Getting
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
  (Vertex simplePolygon)
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
forall (d :: Natural) r s.
(Dimension (Vertex simplePolygon) ~ d,
 NumType (Vertex simplePolygon) ~ r,
 Dimension (Vertex simplePolygon) ~ d,
 NumType (Vertex simplePolygon) ~ s) =>
Lens
  (Vertex simplePolygon)
  (Vertex simplePolygon)
  (Vector d r)
  (Vector d s)
forall point point' (d :: Natural) r s.
(HasVector point point', Dimension point ~ d, NumType point ~ r,
 Dimension point' ~ d, NumType point' ~ s) =>
Lens point point' (Vector d r) (Vector d s)
Lens
  (Vertex simplePolygon)
  (Vertex simplePolygon)
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
vector Vector
  (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall r vector (d :: Natural).
(Num r, Additive_ vector d r) =>
vector -> vector -> vector
^+^ Vertex simplePolygon
qVertex simplePolygon
-> Getting
     (Vector
        (Dimension (Vertex simplePolygon))
        (NumType (Vertex simplePolygon)))
     (Vertex simplePolygon)
     (Vector
        (Dimension (Vertex simplePolygon))
        (NumType (Vertex simplePolygon)))
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall s a. s -> Getting a s a -> a
^.Getting
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
  (Vertex simplePolygon)
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
forall (d :: Natural) r s.
(Dimension (Vertex simplePolygon) ~ d,
 NumType (Vertex simplePolygon) ~ r,
 Dimension (Vertex simplePolygon) ~ d,
 NumType (Vertex simplePolygon) ~ s) =>
Lens
  (Vertex simplePolygon)
  (Vertex simplePolygon)
  (Vector d r)
  (Vector d s)
forall point point' (d :: Natural) r s.
(HasVector point point', Dimension point ~ d, NumType point ~ r,
 Dimension point' ~ d, NumType point' ~ s) =>
Lens point point' (Vector d r) (Vector d s)
Lens
  (Vertex simplePolygon)
  (Vertex simplePolygon)
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
  (Vector
     (Dimension (Vertex simplePolygon))
     (NumType (Vertex simplePolygon)))
vector) Vector
  (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> NumType (Vertex simplePolygon)
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall r vector (d :: Natural).
(Num r, Vector_ vector d r) =>
vector -> r -> vector
^* (Vertex simplePolygon
pVertex simplePolygon
-> Getting
     (NumType (Vertex simplePolygon))
     (Vertex simplePolygon)
     (NumType (Vertex simplePolygon))
-> NumType (Vertex simplePolygon)
forall s a. s -> Getting a s a -> a
^.Getting
  (NumType (Vertex simplePolygon))
  (Vertex simplePolygon)
  (NumType (Vertex simplePolygon))
forall (d :: Natural) point r.
(1 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens'
  Int (Vertex simplePolygon) (NumType (Vertex simplePolygon))
xCoord NumType (Vertex simplePolygon)
-> NumType (Vertex simplePolygon) -> NumType (Vertex simplePolygon)
forall a. Num a => a -> a -> a
* Vertex simplePolygon
qVertex simplePolygon
-> Getting
     (NumType (Vertex simplePolygon))
     (Vertex simplePolygon)
     (NumType (Vertex simplePolygon))
-> NumType (Vertex simplePolygon)
forall s a. s -> Getting a s a -> a
^.Getting
  (NumType (Vertex simplePolygon))
  (Vertex simplePolygon)
  (NumType (Vertex simplePolygon))
forall (d :: Natural) point r.
(2 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens'
  Int (Vertex simplePolygon) (NumType (Vertex simplePolygon))
yCoord NumType (Vertex simplePolygon)
-> NumType (Vertex simplePolygon) -> NumType (Vertex simplePolygon)
forall a. Num a => a -> a -> a
- Vertex simplePolygon
qVertex simplePolygon
-> Getting
     (NumType (Vertex simplePolygon))
     (Vertex simplePolygon)
     (NumType (Vertex simplePolygon))
-> NumType (Vertex simplePolygon)
forall s a. s -> Getting a s a -> a
^.Getting
  (NumType (Vertex simplePolygon))
  (Vertex simplePolygon)
  (NumType (Vertex simplePolygon))
forall (d :: Natural) point r.
(1 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens'
  Int (Vertex simplePolygon) (NumType (Vertex simplePolygon))
xCoord NumType (Vertex simplePolygon)
-> NumType (Vertex simplePolygon) -> NumType (Vertex simplePolygon)
forall a. Num a => a -> a -> a
* Vertex simplePolygon
pVertex simplePolygon
-> Getting
     (NumType (Vertex simplePolygon))
     (Vertex simplePolygon)
     (NumType (Vertex simplePolygon))
-> NumType (Vertex simplePolygon)
forall s a. s -> Getting a s a -> a
^.Getting
  (NumType (Vertex simplePolygon))
  (Vertex simplePolygon)
  (NumType (Vertex simplePolygon))
forall (d :: Natural) point r.
(2 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens'
  Int (Vertex simplePolygon) (NumType (Vertex simplePolygon))
yCoord)
                | (Vertex simplePolygon
p,Vertex simplePolygon
q) <- simplePolygon
poly simplePolygon
-> Getting
     (Endo [(Vertex simplePolygon, Vertex simplePolygon)])
     simplePolygon
     (Vertex simplePolygon, Vertex simplePolygon)
-> [(Vertex simplePolygon, Vertex simplePolygon)]
forall s a. s -> Getting (Endo [a]) s a -> [a]
^..Getting
  (Endo [(Vertex simplePolygon, Vertex simplePolygon)])
  simplePolygon
  (Vertex simplePolygon, Vertex simplePolygon)
forall polygon.
HasOuterBoundary polygon =>
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (Vertex polygon, Vertex polygon)
IndexedFold1
  (VertexIx simplePolygon, VertexIx simplePolygon)
  simplePolygon
  (Vertex simplePolygon, Vertex simplePolygon)
outerBoundaryEdges   ]
           sum' :: [Vector
   (Dimension (Vertex simplePolygon))
   (NumType (Vertex simplePolygon))]
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
sum' = (Vector
   (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
 -> Vector
      (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
 -> Vector
      (Dimension (Vertex simplePolygon))
      (NumType (Vertex simplePolygon)))
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> [Vector
      (Dimension (Vertex simplePolygon))
      (NumType (Vertex simplePolygon))]
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Vector
  (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
-> Vector
     (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall r vector (d :: Natural).
(Num r, Additive_ vector d r) =>
vector -> vector -> vector
(^+^) Vector
  (Dimension (Vertex simplePolygon)) (NumType (Vertex simplePolygon))
forall r vector (d :: Natural).
(Num r, Additive_ vector d r) =>
vector
zero