{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE PartialTypeSignatures #-}
{-# LANGUAGE ScopedTypeVariables #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  Data.Geometry.PlnarSubdivision.Basic
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
-- Description :  Basic data types to represent a PlanarSubdivision
--
--------------------------------------------------------------------------------
module Data.Geometry.PlanarSubdivision.Basic( VertexId', FaceId'
                                            , VertexData(VertexData), PG.vData, PG.location

                                            , FaceData(FaceData), holes, fData

                                            , PlanarSubdivision(PlanarSubdivision)
                                            , Wrap

                                            , Component, ComponentId

                                            , PolygonFaceData(..)
                                            , PlanarGraph
                                            , PlaneGraph
                                            , fromSimplePolygon
                                            , fromConnectedSegments
                                            , fromPlaneGraph, fromPlaneGraph'

                                            , numComponents, numVertices
                                            , numEdges, numFaces, numDarts
                                            , dual

                                            , components, component
                                            , vertices', vertices
                                            , edges', edges
                                            , faces', faces, internalFaces
                                            , darts'
                                            -- , traverseVertices, traverseDarts, traverseFaces

                                            , headOf, tailOf, twin, endPoints

                                            , incidentEdges, incomingEdges, outgoingEdges
                                            , nextIncidentEdge
                                            , neighboursOf

                                            , leftFace, rightFace
                                            , outerBoundaryDarts, boundaryVertices, holesOf
                                            , outerFaceId
                                            , boundary'

                                            , locationOf
                                            , HasDataOf(..)

                                            , endPointsOf, endPointData

                                            , faceDataOf

                                            , edgeSegment, edgeSegments
                                            , rawFacePolygon, rawFaceBoundary
                                            , rawFacePolygons

                                            , VertexId(..), FaceId(..), Dart, World(..)

                                            , rawVertexData, rawDartData, rawFaceData
                                            , vertexData, dartData, faceData
                                            , dataVal

                                            , dartMapping, Raw(..)
                                            ) where

import           Control.Lens hiding (holes, holesOf, (.=))
import           Data.Coerce
import           Data.Ext
import qualified Data.Foldable as F
import           Data.Geometry.Box
import           Data.Geometry.LineSegment hiding (endPoints)
import           Data.Geometry.PlanarSubdivision.Raw
import           Data.Geometry.Point
import           Data.Geometry.Polygon
import           Data.Geometry.Properties
import           Data.List.NonEmpty (NonEmpty(..))
import qualified Data.List.NonEmpty as NonEmpty
import           Data.PlanarGraph.Dart (allDarts,isPositive)
import qualified Data.PlaneGraph as PG
import           Data.PlaneGraph( PlaneGraph, PlanarGraph, dual
                                , Dart, VertexId(..), FaceId(..), twin
                                , World(..)
                                , VertexId', FaceId'
                                , VertexData, location, vData
                                , HasDataOf(..)
                                )
import qualified Data.Sequence as Seq
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import           GHC.Generics (Generic)

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

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

-- | A connected component.
--
-- For every face f, and every hole in this face, the facedata points to a dart
-- d on the hole s.t. this dart has the face f on its left. i.e.
-- leftFace d = f
type Component s r = PlaneGraph (Wrap s)
                                (VertexId' s) (Dart s) (FaceId' s)
                                r


-- | A planarsubdivision is essentially a bunch of plane-graphs; one for every
-- connected component. These graphs store the global ID's (darts, vertexId's, faceId's)
-- in their data values. This essentially gives us a mapping between the two.
--
-- note that a face may actually occur in multiple graphs, hence when we store
-- the edges to the the holes, we store the global edgeId's rather than the
-- 'local' edgeId (dart)'s.
--
-- invariant: the outerface has faceId 0
data PlanarSubdivision s v e f r =
  PlanarSubdivision { PlanarSubdivision s v e f r -> Vector (Component s r)
_components    :: V.Vector (Component s r)
                    , PlanarSubdivision s v e f r
-> Vector (Raw s (VertexId' (Wrap s)) v)
_rawVertexData :: V.Vector (Raw s (VertexId' (Wrap s)) v)
                    , PlanarSubdivision s v e f r -> Vector (Raw s (Dart (Wrap s)) e)
_rawDartData   :: V.Vector (Raw s (Dart      (Wrap s)) e)
                    , PlanarSubdivision s v e f r -> Vector (RawFace s f)
_rawFaceData   :: V.Vector (RawFace s f)
                    } deriving (Int -> PlanarSubdivision s v e f r -> ShowS
[PlanarSubdivision s v e f r] -> ShowS
PlanarSubdivision s v e f r -> String
(Int -> PlanarSubdivision s v e f r -> ShowS)
-> (PlanarSubdivision s v e f r -> String)
-> ([PlanarSubdivision s v e f r] -> ShowS)
-> Show (PlanarSubdivision s v e f r)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
Int -> PlanarSubdivision s v e f r -> ShowS
forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
[PlanarSubdivision s v e f r] -> ShowS
forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
PlanarSubdivision s v e f r -> String
showList :: [PlanarSubdivision s v e f r] -> ShowS
$cshowList :: forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
[PlanarSubdivision s v e f r] -> ShowS
show :: PlanarSubdivision s v e f r -> String
$cshow :: forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
PlanarSubdivision s v e f r -> String
showsPrec :: Int -> PlanarSubdivision s v e f r -> ShowS
$cshowsPrec :: forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
Int -> PlanarSubdivision s v e f r -> ShowS
Show,PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool
(PlanarSubdivision s v e f r
 -> PlanarSubdivision s v e f r -> Bool)
-> (PlanarSubdivision s v e f r
    -> PlanarSubdivision s v e f r -> Bool)
-> Eq (PlanarSubdivision s v e f r)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k (s :: k) v e f r.
(Eq r, Eq v, Eq e, Eq f) =>
PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool
/= :: PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool
$c/= :: forall k (s :: k) v e f r.
(Eq r, Eq v, Eq e, Eq f) =>
PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool
== :: PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool
$c== :: forall k (s :: k) v e f r.
(Eq r, Eq v, Eq e, Eq f) =>
PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool
Eq,a -> PlanarSubdivision s v e f b -> PlanarSubdivision s v e f a
(a -> b)
-> PlanarSubdivision s v e f a -> PlanarSubdivision s v e f b
(forall a b.
 (a -> b)
 -> PlanarSubdivision s v e f a -> PlanarSubdivision s v e f b)
-> (forall a b.
    a -> PlanarSubdivision s v e f b -> PlanarSubdivision s v e f a)
-> Functor (PlanarSubdivision s v e f)
forall k (s :: k) v e f a b.
a -> PlanarSubdivision s v e f b -> PlanarSubdivision s v e f a
forall k (s :: k) v e f a b.
(a -> b)
-> PlanarSubdivision s v e f a -> PlanarSubdivision s v e f b
forall a b.
a -> PlanarSubdivision s v e f b -> PlanarSubdivision s v e f a
forall a b.
(a -> b)
-> PlanarSubdivision s v e f a -> PlanarSubdivision s v e f b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> PlanarSubdivision s v e f b -> PlanarSubdivision s v e f a
$c<$ :: forall k (s :: k) v e f a b.
a -> PlanarSubdivision s v e f b -> PlanarSubdivision s v e f a
fmap :: (a -> b)
-> PlanarSubdivision s v e f a -> PlanarSubdivision s v e f b
$cfmap :: forall k (s :: k) v e f a b.
(a -> b)
-> PlanarSubdivision s v e f a -> PlanarSubdivision s v e f b
Functor,(forall x.
 PlanarSubdivision s v e f r -> Rep (PlanarSubdivision s v e f r) x)
-> (forall x.
    Rep (PlanarSubdivision s v e f r) x -> PlanarSubdivision s v e f r)
-> Generic (PlanarSubdivision s v e f r)
forall x.
Rep (PlanarSubdivision s v e f r) x -> PlanarSubdivision s v e f r
forall x.
PlanarSubdivision s v e f r -> Rep (PlanarSubdivision s v e f r) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (s :: k) v e f r x.
Rep (PlanarSubdivision s v e f r) x -> PlanarSubdivision s v e f r
forall k (s :: k) v e f r x.
PlanarSubdivision s v e f r -> Rep (PlanarSubdivision s v e f r) x
$cto :: forall k (s :: k) v e f r x.
Rep (PlanarSubdivision s v e f r) x -> PlanarSubdivision s v e f r
$cfrom :: forall k (s :: k) v e f r x.
PlanarSubdivision s v e f r -> Rep (PlanarSubdivision s v e f r) x
Generic)
makeLenses ''PlanarSubdivision


type instance NumType   (PlanarSubdivision s v e f r) = r
type instance Dimension (PlanarSubdivision s v e f r) = 2

instance IsBoxable (PlanarSubdivision s v e f r) where
  boundingBox :: PlanarSubdivision s v e f r
-> Box
     (Dimension (PlanarSubdivision s v e f r))
     ()
     (NumType (PlanarSubdivision s v e f r))
boundingBox = [PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r]
-> Box 2 () r
forall g (c :: * -> *).
(IsBoxable g, Foldable c, Ord (NumType g), Arity (Dimension g)) =>
c g -> Box (Dimension g) () (NumType g)
boundingBoxList' ([PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r]
 -> Box 2 () r)
-> (PlanarSubdivision s v e f r
    -> [PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r])
-> PlanarSubdivision s v e f r
-> Box 2 () r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> [PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r]
forall a. Vector a -> [a]
V.toList (Vector (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
 -> [PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r])
-> (PlanarSubdivision s v e f r
    -> Vector
         (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r))
-> PlanarSubdivision s v e f r
-> [PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r
-> Vector
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Component s r)
_components


component    :: ComponentId s -> Lens' (PlanarSubdivision s v e f r)
                                       (Component s r)
component :: ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
component ComponentId s
ci = (Vector (Component s r) -> f (Vector (Component s r)))
-> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r r.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Component s r))
  (Vector (Component s r))
components((Vector (Component s r) -> f (Vector (Component s r)))
 -> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f r))
-> ((Component s r -> f (Component s r))
    -> Vector (Component s r) -> f (Vector (Component s r)))
-> (Component s r -> f (Component s r))
-> PlanarSubdivision s v e f r
-> f (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Traversing
  (->)
  f
  (Vector (Component s r))
  (Vector (Component s r))
  (Component s r)
  (Component s r)
-> (Component s r -> f (Component s r))
-> Vector (Component s r)
-> f (Vector (Component s r))
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 (Index (Vector (Component s r))
-> Traversal'
     (Vector (Component s r)) (IxValue (Vector (Component s r)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (Index (Vector (Component s r))
 -> Traversal'
      (Vector (Component s r)) (IxValue (Vector (Component s r))))
-> Index (Vector (Component s r))
-> Traversal'
     (Vector (Component s r)) (IxValue (Vector (Component s r)))
forall a b. (a -> b) -> a -> b
$ ComponentId s -> Int
forall k (s :: k). ComponentId s -> Int
unCI ComponentId s
ci)

-- instance (ToJSON v, ToJSON v, ToJSON e, ToJSON f, ToJSON r)
--          => ToJSON (PlanarSubdivision s v e f r) where
--   toEncoding = genericToEncoding defaultOptions



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

-- | Constructs a planarsubdivision from a PlaneGraph
--
-- runningTime: \(O(n)\)
fromPlaneGraph   :: forall s v e f r. (Ord r, Fractional r)
                      => PlaneGraph s v e f r -> PlanarSubdivision s v e f r
fromPlaneGraph :: PlaneGraph s v e f r -> PlanarSubdivision s v e f r
fromPlaneGraph PlaneGraph s v e f r
g = PlaneGraph s v e f r -> Dart s -> PlanarSubdivision s v e f r
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> Dart s -> PlanarSubdivision s v e f r
fromPlaneGraph' PlaneGraph s v e f r
g (PlaneGraph s v e f r -> Dart s
forall k r (s :: k) v e f.
(Ord r, Fractional r) =>
PlaneGraph s v e f r -> Dart s
PG.outerFaceDart PlaneGraph s v e f r
g)

{- HLINT ignore fromPlaneGraph' -}
-- | Given a (connected) PlaneGraph and a dart that has the outerface on its left
-- | Constructs a planarsubdivision
--
-- runningTime: \(O(n)\)
fromPlaneGraph'        :: forall s v e f r. PlaneGraph s v e f r -> Dart s
                       -> PlanarSubdivision s v e f r
fromPlaneGraph' :: PlaneGraph s v e f r -> Dart s -> PlanarSubdivision s v e f r
fromPlaneGraph' PlaneGraph s v e f r
g Dart s
ofD = Vector (Component s r)
-> Vector (Raw s (VertexId' (Wrap s)) v)
-> Vector (Raw s (Dart (Wrap s)) e)
-> Vector (RawFace s f)
-> PlanarSubdivision s v e f r
forall k (s :: k) v e f r.
Vector (Component s r)
-> Vector (Raw s (VertexId' (Wrap s)) v)
-> Vector (Raw s (Dart (Wrap s)) e)
-> Vector (RawFace s f)
-> PlanarSubdivision s v e f r
PlanarSubdivision (Component s r -> Vector (Component s r)
forall a. a -> Vector a
V.singleton (Component s r -> Vector (Component s r))
-> (PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
    -> Component s r)
-> PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
-> Vector (Component s r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r -> Component s r
coerce (PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
 -> Vector (Component s r))
-> PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
-> Vector (Component s r)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
g') Vector (Raw s (VertexId' (Wrap s)) v)
vd Vector (Raw s (Dart (Wrap s)) e)
ed Vector (RawFace s f)
fd
  where
    c :: ComponentId s
c = Int -> ComponentId s
forall k (s :: k). Int -> ComponentId s
ComponentId Int
0
    vd :: Vector (Raw s (VertexId' (Wrap s)) v)
vd = (Int -> v -> Raw s (VertexId' (Wrap s)) v)
-> Vector v -> Vector (Raw s (VertexId' (Wrap s)) v)
forall a b. (Int -> a -> b) -> Vector a -> Vector b
V.imap    (\Int
i v
v   -> ComponentId s
-> VertexId' (Wrap s) -> v -> Raw s (VertexId' (Wrap s)) v
forall k (s :: k) ia a. ComponentId s -> ia -> a -> Raw s ia a
Raw ComponentId s
forall k (s :: k). ComponentId s
c (Int -> VertexId' (Wrap s)
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId Int
i) v
v)                   (Vector v -> Vector (Raw s (VertexId' (Wrap s)) v))
-> Vector v -> Vector (Raw s (VertexId' (Wrap s)) v)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r
gPlaneGraph s v e f r
-> Getting (Vector v) (PlaneGraph s v e f r) (Vector v) -> Vector v
forall s a. s -> Getting a s a -> a
^.Getting (Vector v) (PlaneGraph s v e f r) (Vector v)
forall k (s :: k) v e f r v'.
Lens
  (PlaneGraph s v e f r)
  (PlaneGraph s v' e f r)
  (Vector v)
  (Vector v')
PG.vertexData
    ed :: Vector (Raw s (Dart (Wrap s)) e)
ed = (Dart (Wrap s) -> e -> Raw s (Dart (Wrap s)) e)
-> Vector (Dart (Wrap s))
-> Vector e
-> Vector (Raw s (Dart (Wrap s)) e)
forall a b c. (a -> b -> c) -> Vector a -> Vector b -> Vector c
V.zipWith (\Dart (Wrap s)
d e
dd  -> ComponentId s -> Dart (Wrap s) -> e -> Raw s (Dart (Wrap s)) e
forall k (s :: k) ia a. ComponentId s -> ia -> a -> Raw s ia a
Raw ComponentId s
forall k (s :: k). ComponentId s
c Dart (Wrap s)
d e
dd) Vector (Dart (Wrap s))
forall k (s' :: k). Vector (Dart s')
allDarts''                  (Vector e -> Vector (Raw s (Dart (Wrap s)) e))
-> Vector e -> Vector (Raw s (Dart (Wrap s)) e)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r
gPlaneGraph s v e f r
-> Getting (Vector e) (PlaneGraph s v e f r) (Vector e) -> Vector e
forall s a. s -> Getting a s a -> a
^.Getting (Vector e) (PlaneGraph s v e f r) (Vector e)
forall k (s :: k) v e f r e'.
Lens
  (PlaneGraph s v e f r)
  (PlaneGraph s v e' f r)
  (Vector e)
  (Vector e')
PG.rawDartData
    fd :: Vector (RawFace s f)
fd = (Int -> f -> RawFace s f) -> Vector f -> Vector (RawFace s f)
forall a b. (Int -> a -> b) -> Vector a -> Vector b
V.imap (\Int
i f
f      -> Maybe (ComponentId s, FaceId' (Wrap s))
-> FaceData (Dart s) f -> RawFace s f
forall k (s :: k) f1.
Maybe (ComponentId s, FaceId' (Wrap s))
-> FaceData (Dart s) f1 -> RawFace s f1
RawFace (Int -> Maybe (ComponentId s, FaceId' (Wrap s))
mkFaceIdx Int
i) (Int -> f -> FaceData (Dart s) f
mkFaceData Int
i f
f)) (Vector f -> Vector (RawFace s f))
-> Vector f -> Vector (RawFace s f)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r
gPlaneGraph s v e f r
-> Getting (Vector f) (PlaneGraph s v e f r) (Vector f) -> Vector f
forall s a. s -> Getting a s a -> a
^.Getting (Vector f) (PlaneGraph s v e f r) (Vector f)
forall k (s :: k) v e f r f'.
Lens
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f' r)
  (Vector f)
  (Vector f')
PG.faceData

    g' :: PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
    g' :: PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
g' = PlaneGraph s v e f r
gPlaneGraph s v e f r
-> (PlaneGraph s v e f r -> PlaneGraph s v e (FaceId' s) r)
-> PlaneGraph s v e (FaceId' s) r
forall a b. a -> (a -> b) -> b
&(Vector f -> Identity (Vector (FaceId' s)))
-> PlaneGraph s v e f r
-> Identity (PlaneGraph s v e (FaceId' s) r)
forall k (s :: k) v e f r f'.
Lens
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f' r)
  (Vector f)
  (Vector f')
PG.faceData    ((Vector f -> Identity (Vector (FaceId' s)))
 -> PlaneGraph s v e f r
 -> Identity (PlaneGraph s v e (FaceId' s) r))
-> (Vector f -> Vector (FaceId' s))
-> PlaneGraph s v e f r
-> PlaneGraph s v e (FaceId' s) r
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (Int -> f -> FaceId' s) -> Vector f -> Vector (FaceId' s)
forall a b. (Int -> a -> b) -> Vector a -> Vector b
V.imap (\Int
i f
_ -> Int -> FaceId' s
forall k (s' :: k). Int -> FaceId' s'
mkFaceId (Int -> FaceId' s) -> Int -> FaceId' s
forall a b. (a -> b) -> a -> b
$ Int -> Int
flipID Int
i)
          PlaneGraph s v e (FaceId' s) r
-> (PlaneGraph s v e (FaceId' s) r
    -> PlaneGraph s (VertexId' s) e (FaceId' s) r)
-> PlaneGraph s (VertexId' s) e (FaceId' s) r
forall a b. a -> (a -> b) -> b
&(Vector v -> Identity (Vector (VertexId' s)))
-> PlaneGraph s v e (FaceId' s) r
-> Identity (PlaneGraph s (VertexId' s) e (FaceId' s) r)
forall k (s :: k) v e f r v'.
Lens
  (PlaneGraph s v e f r)
  (PlaneGraph s v' e f r)
  (Vector v)
  (Vector v')
PG.vertexData  ((Vector v -> Identity (Vector (VertexId' s)))
 -> PlaneGraph s v e (FaceId' s) r
 -> Identity (PlaneGraph s (VertexId' s) e (FaceId' s) r))
-> (Vector v -> Vector (VertexId' s))
-> PlaneGraph s v e (FaceId' s) r
-> PlaneGraph s (VertexId' s) e (FaceId' s) r
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (Int -> v -> VertexId' s) -> Vector v -> Vector (VertexId' s)
forall a b. (Int -> a -> b) -> Vector a -> Vector b
V.imap (\Int
i v
_ -> Int -> VertexId' s
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId Int
i)
          PlaneGraph s (VertexId' s) e (FaceId' s) r
-> (PlaneGraph s (VertexId' s) e (FaceId' s) r
    -> PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r)
-> PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
forall a b. a -> (a -> b) -> b
&(Vector e -> Identity (Vector (Dart s)))
-> PlaneGraph s (VertexId' s) e (FaceId' s) r
-> Identity (PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r e'.
Lens
  (PlaneGraph s v e f r)
  (PlaneGraph s v e' f r)
  (Vector e)
  (Vector e')
PG.rawDartData ((Vector e -> Identity (Vector (Dart s)))
 -> PlaneGraph s (VertexId' s) e (FaceId' s) r
 -> Identity (PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r))
-> Vector (Dart s)
-> PlaneGraph s (VertexId' s) e (FaceId' s) r
-> PlaneGraph s (VertexId' s) (Dart s) (FaceId' s) r
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Vector (Dart s)
forall k (s' :: k). Vector (Dart s')
allDarts''

    allDarts'' :: forall s'. V.Vector (Dart s')
    allDarts'' :: Vector (Dart s')
allDarts'' = Int -> Vector (Dart s')
forall k (s' :: k). Int -> Vector (Dart s')
allDarts' (PlaneGraph s v e f r -> Int
forall k (s :: k) v e f r. PlaneGraph s v e f r -> Int
PG.numDarts PlaneGraph s v e f r
g)

    -- make sure the outerFaceId is 0
    oF :: FaceId' s
oF@(FaceId (VertexId Int
of')) = Dart s -> PlaneGraph s v e f r -> FaceId' s
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> FaceId' s
PG.leftFace Dart s
ofD PlaneGraph s v e f r
g

    mkFaceIdx :: Int -> Maybe (ComponentId s, FaceId' (Wrap s))
mkFaceIdx Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = Maybe (ComponentId s, FaceId' (Wrap s))
forall a. Maybe a
Nothing
                | Bool
otherwise = (ComponentId s, FaceId' (Wrap s))
-> Maybe (ComponentId s, FaceId' (Wrap s))
forall a. a -> Maybe a
Just (ComponentId s
forall k (s :: k). ComponentId s
c,Int -> FaceId' (Wrap s)
forall k (s' :: k). Int -> FaceId' s'
mkFaceId (Int -> FaceId' (Wrap s))
-> (Int -> Int) -> Int -> FaceId' (Wrap s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int
flipID (Int -> FaceId' (Wrap s)) -> Int -> FaceId' (Wrap s)
forall a b. (a -> b) -> a -> b
$ Int
i)

    -- at index i we are storing the outerface
    mkFaceData                 :: Int -> f -> FaceData (Dart s) f
    mkFaceData :: Int -> f -> FaceData (Dart s) f
mkFaceData Int
i f
f | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = Seq (Dart s) -> f -> FaceData (Dart s) f
forall h f1. Seq h -> f1 -> FaceData h f1
FaceData (Dart s -> Seq (Dart s)
forall a. a -> Seq a
Seq.singleton Dart s
ofD) (PlaneGraph s v e f r
gPlaneGraph s v e f r -> Getting f (PlaneGraph s v e f r) f -> f
forall s a. s -> Getting a s a -> a
^.FaceId' s
-> Lens'
     (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf FaceId' s
oF)
                   | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
of'  = Seq (Dart s) -> f -> FaceData (Dart s) f
forall h f1. Seq h -> f1 -> FaceData h f1
FaceData Seq (Dart s)
forall a. Monoid a => a
mempty              (PlaneGraph s v e f r
gPlaneGraph s v e f r -> Getting f (PlaneGraph s v e f r) f -> f
forall s a. s -> Getting a s a -> a
^.FaceId' s
-> Lens'
     (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf (Int -> FaceId' s
forall k (s' :: k). Int -> FaceId' s'
mkFaceId @s Int
0))
                   | Bool
otherwise = Seq (Dart s) -> f -> FaceData (Dart s) f
forall h f1. Seq h -> f1 -> FaceData h f1
FaceData Seq (Dart s)
forall a. Monoid a => a
mempty              f
f

    mkFaceId :: forall s'. Int -> FaceId' s'
    mkFaceId :: Int -> FaceId' s'
mkFaceId = VertexId s' 'Dual -> FaceId' s'
forall k (s :: k) (w :: World). VertexId s (DualOf w) -> FaceId s w
FaceId (VertexId s' 'Dual -> FaceId' s')
-> (Int -> VertexId s' 'Dual) -> Int -> FaceId' s'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> VertexId s' 'Dual
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId

    flipID :: Int -> Int
flipID Int
i | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0    = Int
of'
             | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
of'  = Int
0
             | Bool
otherwise = Int
i

-- | Construct a plane graph from a simple polygon. It is assumed that the
-- polygon is given in counterclockwise order.
--
-- the interior of the polygon will have faceId 0
--
-- pre: the input polygon is given in counterclockwise order
-- running time: \(O(n)\).
fromSimplePolygon            :: (Ord r, Fractional r)
                             => proxy s
                             -> SimplePolygon p r
                             -> f -- ^ data inside
                             -> f -- ^ data outside the polygon
                             -> PlanarSubdivision s p () f r
fromSimplePolygon :: proxy s
-> SimplePolygon p r -> f -> f -> PlanarSubdivision s p () f r
fromSimplePolygon proxy s
p SimplePolygon p r
pg f
iD f
oD =
  PlaneGraph s p () f r -> PlanarSubdivision s p () f r
forall k (s :: k) v e f r.
(Ord r, Fractional r) =>
PlaneGraph s v e f r -> PlanarSubdivision s v e f r
fromPlaneGraph (proxy s -> SimplePolygon p r -> f -> f -> PlaneGraph s p () f r
forall k (proxy :: k -> *) (s :: k) p r f.
proxy s -> SimplePolygon p r -> f -> f -> PlaneGraph s p () f r
PG.fromSimplePolygon proxy s
p SimplePolygon p r
pg f
iD f
oD)

-- | Constructs a connected planar subdivision.
--
-- pre: the segments form a single connected component
-- running time: \(O(n\log n)\)
fromConnectedSegments    :: (Foldable f, Ord r, Fractional r)
                         => proxy s
                         -> f (LineSegment 2 p r :+ e)
                         -> PlanarSubdivision s (NonEmpty p) e () r
fromConnectedSegments :: proxy s
-> f (LineSegment 2 p r :+ e)
-> PlanarSubdivision s (NonEmpty p) e () r
fromConnectedSegments proxy s
px = PlaneGraph s (NonEmpty p) e () r
-> PlanarSubdivision s (NonEmpty p) e () r
forall k (s :: k) v e f r.
(Ord r, Fractional r) =>
PlaneGraph s v e f r -> PlanarSubdivision s v e f r
fromPlaneGraph (PlaneGraph s (NonEmpty p) e () r
 -> PlanarSubdivision s (NonEmpty p) e () r)
-> (f (LineSegment 2 p r :+ e) -> PlaneGraph s (NonEmpty p) e () r)
-> f (LineSegment 2 p r :+ e)
-> PlanarSubdivision s (NonEmpty p) e () r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. proxy s
-> f (LineSegment 2 p r :+ e) -> PlaneGraph s (NonEmpty p) e () r
forall k (f :: * -> *) r (proxy :: k -> *) (s :: k) p e.
(Foldable f, Ord r, Num r) =>
proxy s
-> f (LineSegment 2 p r :+ e) -> PlaneGraph s (NonEmpty p) e () r
PG.fromConnectedSegments proxy s
px

-- g1 = PG.fromConnectedSegments (Identity Test1) testSegs
-- ps1 = fromConnectedSegments (Identity Test1) testSegs

-- data Test1 = Test1

-- draw = V.filter isEmpty . rawFacePolygons
--   where
--     isEmpty (_,Left  p :+ _) = (< 3) . length . polygonVertices $ p
--     isEmpty (_,Right p :+ _) = (< 3) . length . polygonVertices $ p

-- testSegs = map (\(p,q) -> ClosedLineSegment (ext p) (ext q) :+ ())
--                    [ (origin, Point2 10 10)
--                    , (origin, Point2 12 10)
--                    , (origin, Point2 20 5)
--                    , (origin, Point2 13 20)
--                    , (Point2 10 10, Point2 12 10)
--                    , (Point2 10 10, Point2 13 20)
--                    , (Point2 12 10, Point2 20 5)
--                    ]


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

-- | Data type that expresses whether or not we are inside or outside the
-- polygon.
data PolygonFaceData = Inside | Outside deriving (Int -> PolygonFaceData -> ShowS
[PolygonFaceData] -> ShowS
PolygonFaceData -> String
(Int -> PolygonFaceData -> ShowS)
-> (PolygonFaceData -> String)
-> ([PolygonFaceData] -> ShowS)
-> Show PolygonFaceData
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PolygonFaceData] -> ShowS
$cshowList :: [PolygonFaceData] -> ShowS
show :: PolygonFaceData -> String
$cshow :: PolygonFaceData -> String
showsPrec :: Int -> PolygonFaceData -> ShowS
$cshowsPrec :: Int -> PolygonFaceData -> ShowS
Show,ReadPrec [PolygonFaceData]
ReadPrec PolygonFaceData
Int -> ReadS PolygonFaceData
ReadS [PolygonFaceData]
(Int -> ReadS PolygonFaceData)
-> ReadS [PolygonFaceData]
-> ReadPrec PolygonFaceData
-> ReadPrec [PolygonFaceData]
-> Read PolygonFaceData
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [PolygonFaceData]
$creadListPrec :: ReadPrec [PolygonFaceData]
readPrec :: ReadPrec PolygonFaceData
$creadPrec :: ReadPrec PolygonFaceData
readList :: ReadS [PolygonFaceData]
$creadList :: ReadS [PolygonFaceData]
readsPrec :: Int -> ReadS PolygonFaceData
$creadsPrec :: Int -> ReadS PolygonFaceData
Read,PolygonFaceData -> PolygonFaceData -> Bool
(PolygonFaceData -> PolygonFaceData -> Bool)
-> (PolygonFaceData -> PolygonFaceData -> Bool)
-> Eq PolygonFaceData
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PolygonFaceData -> PolygonFaceData -> Bool
$c/= :: PolygonFaceData -> PolygonFaceData -> Bool
== :: PolygonFaceData -> PolygonFaceData -> Bool
$c== :: PolygonFaceData -> PolygonFaceData -> Bool
Eq)


--------------------------------------------------------------------------------
-- * Basic Graph information

-- | Get the number of vertices
--
-- >>> numVertices myGraph
-- 1
numComponents :: PlanarSubdivision s v e f r  -> Int
numComponents :: PlanarSubdivision s v e f r -> Int
numComponents = Vector (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> Int
forall a. Vector a -> Int
V.length (Vector (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
 -> Int)
-> (PlanarSubdivision s v e f r
    -> Vector
         (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r))
-> PlanarSubdivision s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r
-> Vector
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Component s r)
_components

-- | Get the number of vertices
--
-- >>> numVertices myGraph
-- 4
numVertices :: PlanarSubdivision s v e f r  -> Int
numVertices :: PlanarSubdivision s v e f r -> Int
numVertices = Vector (Raw s (VertexId' (Wrap s)) v) -> Int
forall a. Vector a -> Int
V.length (Vector (Raw s (VertexId' (Wrap s)) v) -> Int)
-> (PlanarSubdivision s v e f r
    -> Vector (Raw s (VertexId' (Wrap s)) v))
-> PlanarSubdivision s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r
-> Vector (Raw s (VertexId' (Wrap s)) v)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r
-> Vector (Raw s (VertexId' (Wrap s)) v)
_rawVertexData

-- | Get the number of Darts
--
-- >>> numDarts myGraph
-- 12
numDarts :: PlanarSubdivision s v e f r  -> Int
numDarts :: PlanarSubdivision s v e f r -> Int
numDarts = Vector (Raw s (Dart (Wrap s)) e) -> Int
forall a. Vector a -> Int
V.length (Vector (Raw s (Dart (Wrap s)) e) -> Int)
-> (PlanarSubdivision s v e f r
    -> Vector (Raw s (Dart (Wrap s)) e))
-> PlanarSubdivision s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r -> Vector (Raw s (Dart (Wrap s)) e)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Raw s (Dart (Wrap s)) e)
_rawDartData

-- | Get the number of Edges
--
-- >>> numEdges myGraph
-- 6
numEdges :: PlanarSubdivision s v e f r  -> Int
numEdges :: PlanarSubdivision s v e f r -> Int
numEdges = (Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) (Int -> Int)
-> (PlanarSubdivision s v e f r -> Int)
-> PlanarSubdivision s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (Raw s (Dart (Wrap s)) e) -> Int
forall a. Vector a -> Int
V.length (Vector (Raw s (Dart (Wrap s)) e) -> Int)
-> (PlanarSubdivision s v e f r
    -> Vector (Raw s (Dart (Wrap s)) e))
-> PlanarSubdivision s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r -> Vector (Raw s (Dart (Wrap s)) e)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Raw s (Dart (Wrap s)) e)
_rawDartData

-- | \( O(1) \). Get the number of faces
--
-- >>> numFaces myGraph
-- 4
numFaces :: PlanarSubdivision s v e f r  -> Int
numFaces :: PlanarSubdivision s v e f r -> Int
numFaces = Vector (RawFace s f) -> Int
forall a. Vector a -> Int
V.length (Vector (RawFace s f) -> Int)
-> (PlanarSubdivision s v e f r -> Vector (RawFace s f))
-> PlanarSubdivision s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r -> Vector (RawFace s f)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (RawFace s f)
_rawFaceData

-- | Enumerate all vertices
--
-- >>> vertices' myGraph
-- [VertexId 0,VertexId 1,VertexId 2,VertexId 3]
vertices'   :: PlanarSubdivision s v e f r  -> V.Vector (VertexId' s)
vertices' :: PlanarSubdivision s v e f r -> Vector (VertexId' s)
vertices' PlanarSubdivision s v e f r
ps = let n :: Int
n = PlanarSubdivision s v e f r -> Int
forall k (s :: k) v e f r. PlanarSubdivision s v e f r -> Int
numVertices PlanarSubdivision s v e f r
ps
               in [VertexId' s] -> Vector (VertexId' s)
forall a. [a] -> Vector a
V.fromList ([VertexId' s] -> Vector (VertexId' s))
-> [VertexId' s] -> Vector (VertexId' s)
forall a b. (a -> b) -> a -> b
$ (Int -> VertexId' s) -> [Int] -> [VertexId' s]
forall a b. (a -> b) -> [a] -> [b]
map Int -> VertexId' s
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId [Int
0..Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1]

-- | Enumerate all vertices, together with their vertex data

-- >>> vertices myGraph
-- [(VertexId 0,()),(VertexId 1,()),(VertexId 2,()),(VertexId 3,())]
vertices    :: PlanarSubdivision s v e f r  -> V.Vector (VertexId' s, VertexData r v)
vertices :: PlanarSubdivision s v e f r -> Vector (VertexId' s, VertexData r v)
vertices PlanarSubdivision s v e f r
ps = (\VertexId' s
vi -> (VertexId' s
vi,PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (VertexData r v) (PlanarSubdivision s v e f r) (VertexData r v)
-> VertexData r v
forall s a. s -> Getting a s a -> a
^.VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
vertexDataOf VertexId' s
vi)) (VertexId' s -> (VertexId' s, VertexData r v))
-> Vector (VertexId' s) -> Vector (VertexId' s, VertexData r v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PlanarSubdivision s v e f r -> Vector (VertexId' s)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (VertexId' s)
vertices' PlanarSubdivision s v e f r
ps

-- | Enumerate all darts
darts' :: PlanarSubdivision s v e f r  -> V.Vector (Dart s)
darts' :: PlanarSubdivision s v e f r -> Vector (Dart s)
darts' = Int -> Vector (Dart s)
forall k (s' :: k). Int -> Vector (Dart s')
allDarts' (Int -> Vector (Dart s))
-> (PlanarSubdivision s v e f r -> Int)
-> PlanarSubdivision s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r -> Int
forall k (s :: k) v e f r. PlanarSubdivision s v e f r -> Int
numDarts

allDarts'   :: forall s'. Int -> V.Vector (Dart s')
allDarts' :: Int -> Vector (Dart s')
allDarts' Int
n = [Dart s'] -> Vector (Dart s')
forall a. [a] -> Vector a
V.fromList ([Dart s'] -> Vector (Dart s')) -> [Dart s'] -> Vector (Dart s')
forall a b. (a -> b) -> a -> b
$ Int -> [Dart s'] -> [Dart s']
forall a. Int -> [a] -> [a]
take Int
n [Dart s']
forall k (s :: k). [Dart s]
allDarts


-- | Enumerate all edges. We report only the Positive darts
edges' :: PlanarSubdivision s v e f r  -> V.Vector (Dart s)
edges' :: PlanarSubdivision s v e f r -> Vector (Dart s)
edges' = (Dart s -> Bool) -> Vector (Dart s) -> Vector (Dart s)
forall a. (a -> Bool) -> Vector a -> Vector a
V.filter Dart s -> Bool
forall k (s :: k). Dart s -> Bool
isPositive (Vector (Dart s) -> Vector (Dart s))
-> (PlanarSubdivision s v e f r -> Vector (Dart s))
-> PlanarSubdivision s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Dart s)
darts'

-- | Enumerate all edges with their edge data. We report only the Positive
-- darts.
--
-- >>> mapM_ print $ edges myGraph
-- (Dart (Arc 2) +1,"c+")
-- (Dart (Arc 1) +1,"b+")
-- (Dart (Arc 0) +1,"a+")
-- (Dart (Arc 5) +1,"g+")
-- (Dart (Arc 4) +1,"e+")
-- (Dart (Arc 3) +1,"d+")
edges    :: PlanarSubdivision s v e f r  -> V.Vector (Dart s, e)
edges :: PlanarSubdivision s v e f r -> Vector (Dart s, e)
edges PlanarSubdivision s v e f r
ps = (\Dart s
e -> (Dart s
e,PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting e (PlanarSubdivision s v e f r) e -> e
forall s a. s -> Getting a s a -> a
^.Dart s
-> Lens'
     (PlanarSubdivision s v e f r)
     (DataOf (PlanarSubdivision s v e f r) (Dart s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart s
e)) (Dart s -> (Dart s, e)) -> Vector (Dart s) -> Vector (Dart s, e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Dart s)
edges' PlanarSubdivision s v e f r
ps

-- | \( O(n) \). Vector of all primal faces.
faces'    :: PlanarSubdivision s v e f r -> V.Vector (FaceId' s)
faces' :: PlanarSubdivision s v e f r -> Vector (FaceId' s)
faces' PlanarSubdivision s v e f r
ps = let n :: Int
n = PlanarSubdivision s v e f r -> Int
forall k (s :: k) v e f r. PlanarSubdivision s v e f r -> Int
numFaces PlanarSubdivision s v e f r
ps
            in [FaceId' s] -> Vector (FaceId' s)
forall a. [a] -> Vector a
V.fromList ([FaceId' s] -> Vector (FaceId' s))
-> [FaceId' s] -> Vector (FaceId' s)
forall a b. (a -> b) -> a -> b
$ (Int -> FaceId' s) -> [Int] -> [FaceId' s]
forall a b. (a -> b) -> [a] -> [b]
map (VertexId s 'Dual -> FaceId' s
forall k (s :: k) (w :: World). VertexId s (DualOf w) -> FaceId s w
FaceId (VertexId s 'Dual -> FaceId' s)
-> (Int -> VertexId s 'Dual) -> Int -> FaceId' s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> VertexId s 'Dual
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId) [Int
0..Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1]

-- | \( O(n) \). Vector of all primal faces with associated data.
faces    :: PlanarSubdivision s v e f r -> V.Vector (FaceId' s, FaceData (Dart s) f)
faces :: PlanarSubdivision s v e f r
-> Vector (FaceId' s, FaceData (Dart s) f)
faces PlanarSubdivision s v e f r
ps = (\FaceId' s
fi -> (FaceId' s
fi,PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (FaceData (Dart s) f)
     (PlanarSubdivision s v e f r)
     (FaceData (Dart s) f)
-> FaceData (Dart s) f
forall s a. s -> Getting a s a -> a
^.FaceId' s
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
forall k (s :: k) v e f r.
FaceId' s
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
faceDataOf FaceId' s
fi)) (FaceId' s -> (FaceId' s, FaceData (Dart s) f))
-> Vector (FaceId' s) -> Vector (FaceId' s, FaceData (Dart s) f)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PlanarSubdivision s v e f r -> Vector (FaceId' s)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (FaceId' s)
faces' PlanarSubdivision s v e f r
ps




-- | Enumerates all faces with their face data exlcluding  the outer face
internalFaces    :: PlanarSubdivision s v e f r
                 -> V.Vector (FaceId' s, FaceData (Dart s) f)
internalFaces :: PlanarSubdivision s v e f r
-> Vector (FaceId' s, FaceData (Dart s) f)
internalFaces PlanarSubdivision s v e f r
ps = Vector (FaceId' s, FaceData (Dart s) f)
-> Vector (FaceId' s, FaceData (Dart s) f)
forall a. Vector a -> Vector a
V.tail (Vector (FaceId' s, FaceData (Dart s) f)
 -> Vector (FaceId' s, FaceData (Dart s) f))
-> Vector (FaceId' s, FaceData (Dart s) f)
-> Vector (FaceId' s, FaceData (Dart s) f)
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r
-> Vector (FaceId' s, FaceData (Dart s) f)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r
-> Vector (FaceId' s, FaceData (Dart s) f)
faces PlanarSubdivision s v e f r
ps
  -- this uses that the outerfaceId is 0, and thus it is the first face in the vector.

-- | lens to access the Dart Data
dartData :: Lens (PlanarSubdivision s v e f r) (PlanarSubdivision s v e' f r)
                 (V.Vector (Dart s, e))        (V.Vector (Dart s, e'))
dartData :: (Vector (Dart s, e) -> f (Vector (Dart s, e')))
-> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e' f r)
dartData = (PlanarSubdivision s v e f r -> Vector (Dart s, e))
-> (PlanarSubdivision s v e f r
    -> Vector (Dart s, e') -> PlanarSubdivision s v e' f r)
-> Lens
     (PlanarSubdivision s v e f r)
     (PlanarSubdivision s v e' f r)
     (Vector (Dart s, e))
     (Vector (Dart s, e'))
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarSubdivision s v e f r -> Vector (Dart s, e)
forall k (s :: k) v b f r.
PlanarSubdivision s v b f r -> Vector (Dart s, b)
getF PlanarSubdivision s v e f r
-> Vector (Dart s, e') -> PlanarSubdivision s v e' f r
forall k (t :: * -> *) a (s :: k) v a f r e.
(Foldable t, Enum a) =>
PlanarSubdivision s v a f r
-> t (a, e) -> PlanarSubdivision s v e f r
setF
  where
    getF :: PlanarSubdivision s v b f r -> Vector (Dart s, b)
getF     = (Int -> Raw s (Dart (Wrap s)) b -> (Dart s, b))
-> Vector (Raw s (Dart (Wrap s)) b) -> Vector (Dart s, b)
forall a b. (Int -> a -> b) -> Vector a -> Vector b
V.imap (\Int
i Raw s (Dart (Wrap s)) b
x -> (Int -> Dart s
forall a. Enum a => Int -> a
toEnum Int
i, Raw s (Dart (Wrap s)) b
xRaw s (Dart (Wrap s)) b
-> Getting b (Raw s (Dart (Wrap s)) b) b -> b
forall s a. s -> Getting a s a -> a
^.Getting b (Raw s (Dart (Wrap s)) b) b
forall k (s :: k) ia a b. Lens (Raw s ia a) (Raw s ia b) a b
dataVal)) (Vector (Raw s (Dart (Wrap s)) b) -> Vector (Dart s, b))
-> (PlanarSubdivision s v b f r
    -> Vector (Raw s (Dart (Wrap s)) b))
-> PlanarSubdivision s v b f r
-> Vector (Dart s, b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v b f r -> Vector (Raw s (Dart (Wrap s)) b)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Raw s (Dart (Wrap s)) e)
_rawDartData
    setF :: PlanarSubdivision s v a f r
-> t (a, e) -> PlanarSubdivision s v e f r
setF PlanarSubdivision s v a f r
ps t (a, e)
ds' = PlanarSubdivision s v a f r
psPlanarSubdivision s v a f r
-> (PlanarSubdivision s v a f r -> PlanarSubdivision s v e f r)
-> PlanarSubdivision s v e f r
forall a b. a -> (a -> b) -> b
&(Vector (Raw s (Dart (Wrap s)) a)
 -> Identity (Vector (Raw s (Dart (Wrap s)) e)))
-> PlanarSubdivision s v a f r
-> Identity (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r e.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (Dart (Wrap s)) e))
  (Vector (Raw s (Dart (Wrap s)) e))
rawDartData ((Vector (Raw s (Dart (Wrap s)) a)
  -> Identity (Vector (Raw s (Dart (Wrap s)) e)))
 -> PlanarSubdivision s v a f r
 -> Identity (PlanarSubdivision s v e f r))
-> (Vector (Raw s (Dart (Wrap s)) a)
    -> Vector (Raw s (Dart (Wrap s)) e))
-> PlanarSubdivision s v a f r
-> PlanarSubdivision s v e f r
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ t (a, e)
-> Vector (Raw s (Dart (Wrap s)) a)
-> Vector (Raw s (Dart (Wrap s)) e)
forall k (t :: * -> *) a b (s :: k) ia a.
(Foldable t, Enum a) =>
t (a, b) -> Vector (Raw s ia a) -> Vector (Raw s ia b)
mkDS' t (a, e)
ds'

    -- create a new dartData vector to assign the values to
    mkDS' :: t (a, b) -> Vector (Raw s ia a) -> Vector (Raw s ia b)
mkDS' t (a, b)
ds' Vector (Raw s ia a)
ds = (forall s. ST s (MVector s (Raw s ia b))) -> Vector (Raw s ia b)
forall a. (forall s. ST s (MVector s a)) -> Vector a
V.create ((forall s. ST s (MVector s (Raw s ia b))) -> Vector (Raw s ia b))
-> (forall s. ST s (MVector s (Raw s ia b))) -> Vector (Raw s ia b)
forall a b. (a -> b) -> a -> b
$ do
                     MVector s (Raw s ia b)
v <- Int -> ST s (MVector (PrimState (ST s)) (Raw s ia b))
forall (m :: * -> *) a.
PrimMonad m =>
Int -> m (MVector (PrimState m) a)
MV.new (Vector (Raw s ia a) -> Int
forall a. Vector a -> Int
V.length Vector (Raw s ia a)
ds)
                     ((a, b) -> ST s ()) -> t (a, b) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Vector (Raw s ia a)
-> MVector (PrimState (ST s)) (Raw s ia b) -> (a, b) -> ST s ()
forall k a (m :: * -> *) (s :: k) ia a b.
(Enum a, PrimMonad m) =>
Vector (Raw s ia a)
-> MVector (PrimState m) (Raw s ia b) -> (a, b) -> m ()
assignDart Vector (Raw s ia a)
ds MVector s (Raw s ia b)
MVector (PrimState (ST s)) (Raw s ia b)
v) t (a, b)
ds'
                     MVector s (Raw s ia b) -> ST s (MVector s (Raw s ia b))
forall (f :: * -> *) a. Applicative f => a -> f a
pure MVector s (Raw s ia b)
v

    assignDart :: Vector (Raw s ia a)
-> MVector (PrimState m) (Raw s ia b) -> (a, b) -> m ()
assignDart Vector (Raw s ia a)
ds MVector (PrimState m) (Raw s ia b)
v (a
d,b
x) = let i :: Int
i = a -> Int
forall a. Enum a => a -> Int
fromEnum a
d
                                y :: Raw s ia a
y = Vector (Raw s ia a)
ds Vector (Raw s ia a) -> Int -> Raw s ia a
forall a. Vector a -> Int -> a
V.! Int
i
                            in MVector (PrimState m) (Raw s ia b) -> Int -> Raw s ia b -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
MV.write MVector (PrimState m) (Raw s ia b)
v Int
i (Raw s ia a
yRaw s ia a -> (Raw s ia a -> Raw s ia b) -> Raw s ia b
forall a b. a -> (a -> b) -> b
&(a -> Identity b) -> Raw s ia a -> Identity (Raw s ia b)
forall k (s :: k) ia a b. Lens (Raw s ia a) (Raw s ia b) a b
dataVal ((a -> Identity b) -> Raw s ia a -> Identity (Raw s ia b))
-> b -> Raw s ia a -> Raw s ia b
forall s t a b. ASetter s t a b -> b -> s -> t
.~ b
x)


-- | Lens to the facedata of the faces themselves. The indices correspond to the faceIds
faceData :: Lens (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f' r)
                 (V.Vector f)                  (V.Vector f')
faceData :: (Vector f -> f (Vector f'))
-> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f' r)
faceData = (PlanarSubdivision s v e f r -> Vector f)
-> (PlanarSubdivision s v e f r
    -> Vector f' -> PlanarSubdivision s v e f' r)
-> Lens
     (PlanarSubdivision s v e f r)
     (PlanarSubdivision s v e f' r)
     (Vector f)
     (Vector f')
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarSubdivision s v e f r -> Vector f
forall k (s :: k) v e f1 r.
PlanarSubdivision s v e f1 r -> Vector f1
getF PlanarSubdivision s v e f r
-> Vector f' -> PlanarSubdivision s v e f' r
forall k (s :: k) v e f1 r f.
PlanarSubdivision s v e f1 r
-> Vector f -> PlanarSubdivision s v e f r
setF
  where
    getF :: PlanarSubdivision s v e f1 r -> Vector f1
getF = (RawFace s f1 -> f1) -> Vector (RawFace s f1) -> Vector f1
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (RawFace s f1 -> Getting f1 (RawFace s f1) f1 -> f1
forall s a. s -> Getting a s a -> a
^.(FaceData (Dart s) f1 -> Const f1 (FaceData (Dart s) f1))
-> RawFace s f1 -> Const f1 (RawFace s f1)
forall k (s :: k) f1 f2.
Lens
  (RawFace s f1)
  (RawFace s f2)
  (FaceData (Dart s) f1)
  (FaceData (Dart s) f2)
faceDataVal((FaceData (Dart s) f1 -> Const f1 (FaceData (Dart s) f1))
 -> RawFace s f1 -> Const f1 (RawFace s f1))
-> ((f1 -> Const f1 f1)
    -> FaceData (Dart s) f1 -> Const f1 (FaceData (Dart s) f1))
-> Getting f1 (RawFace s f1) f1
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(f1 -> Const f1 f1)
-> FaceData (Dart s) f1 -> Const f1 (FaceData (Dart s) f1)
forall h f1 f2. Lens (FaceData h f1) (FaceData h f2) f1 f2
fData) (Vector (RawFace s f1) -> Vector f1)
-> (PlanarSubdivision s v e f1 r -> Vector (RawFace s f1))
-> PlanarSubdivision s v e f1 r
-> Vector f1
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f1 r -> Vector (RawFace s f1)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (RawFace s f)
_rawFaceData
    setF :: PlanarSubdivision s v e f1 r
-> Vector f -> PlanarSubdivision s v e f r
setF PlanarSubdivision s v e f1 r
ps Vector f
v' = PlanarSubdivision s v e f1 r
psPlanarSubdivision s v e f1 r
-> (PlanarSubdivision s v e f1 r -> PlanarSubdivision s v e f r)
-> PlanarSubdivision s v e f r
forall a b. a -> (a -> b) -> b
&(Vector (RawFace s f1) -> Identity (Vector (RawFace s f)))
-> PlanarSubdivision s v e f1 r
-> Identity (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r f.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (RawFace s f))
  (Vector (RawFace s f))
rawFaceData ((Vector (RawFace s f1) -> Identity (Vector (RawFace s f)))
 -> PlanarSubdivision s v e f1 r
 -> Identity (PlanarSubdivision s v e f r))
-> (Vector (RawFace s f1) -> Vector (RawFace s f))
-> PlanarSubdivision s v e f1 r
-> PlanarSubdivision s v e f r
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (f -> RawFace s f1 -> RawFace s f)
-> Vector f -> Vector (RawFace s f1) -> Vector (RawFace s f)
forall a b c. (a -> b -> c) -> Vector a -> Vector b -> Vector c
V.zipWith (\f
x' RawFace s f1
x -> RawFace s f1
xRawFace s f1 -> (RawFace s f1 -> RawFace s f) -> RawFace s f
forall a b. a -> (a -> b) -> b
&(FaceData (Dart s) f1 -> Identity (FaceData (Dart s) f))
-> RawFace s f1 -> Identity (RawFace s f)
forall k (s :: k) f1 f2.
Lens
  (RawFace s f1)
  (RawFace s f2)
  (FaceData (Dart s) f1)
  (FaceData (Dart s) f2)
faceDataVal((FaceData (Dart s) f1 -> Identity (FaceData (Dart s) f))
 -> RawFace s f1 -> Identity (RawFace s f))
-> ((f1 -> Identity f)
    -> FaceData (Dart s) f1 -> Identity (FaceData (Dart s) f))
-> (f1 -> Identity f)
-> RawFace s f1
-> Identity (RawFace s f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(f1 -> Identity f)
-> FaceData (Dart s) f1 -> Identity (FaceData (Dart s) f)
forall h f1 f2. Lens (FaceData h f1) (FaceData h f2) f1 f2
fData ((f1 -> Identity f) -> RawFace s f1 -> Identity (RawFace s f))
-> f -> RawFace s f1 -> RawFace s f
forall s t a b. ASetter s t a b -> b -> s -> t
.~ f
x') Vector f
v'

-- | Lens to the facedata of the vertexdata themselves. The indices correspond to the vertexId's
vertexData :: Lens (PlanarSubdivision s v e f r) (PlanarSubdivision s v' e f r)
                   (V.Vector v)                  (V.Vector v')
vertexData :: (Vector v -> f (Vector v'))
-> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v' e f r)
vertexData = (PlanarSubdivision s v e f r -> Vector v)
-> (PlanarSubdivision s v e f r
    -> Vector v' -> PlanarSubdivision s v' e f r)
-> Lens
     (PlanarSubdivision s v e f r)
     (PlanarSubdivision s v' e f r)
     (Vector v)
     (Vector v')
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarSubdivision s v e f r -> Vector v
forall k (s :: k) a e f r. PlanarSubdivision s a e f r -> Vector a
getF PlanarSubdivision s v e f r
-> Vector v' -> PlanarSubdivision s v' e f r
forall k (s :: k) a e f r v.
PlanarSubdivision s a e f r
-> Vector v -> PlanarSubdivision s v e f r
setF
  where
    getF :: PlanarSubdivision s a e f r -> Vector a
getF = (Raw s (VertexId' (Wrap s)) a -> a)
-> Vector (Raw s (VertexId' (Wrap s)) a) -> Vector a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Raw s (VertexId' (Wrap s)) a
-> Getting a (Raw s (VertexId' (Wrap s)) a) a -> a
forall s a. s -> Getting a s a -> a
^.Getting a (Raw s (VertexId' (Wrap s)) a) a
forall k (s :: k) ia a b. Lens (Raw s ia a) (Raw s ia b) a b
dataVal) (Vector (Raw s (VertexId' (Wrap s)) a) -> Vector a)
-> (PlanarSubdivision s a e f r
    -> Vector (Raw s (VertexId' (Wrap s)) a))
-> PlanarSubdivision s a e f r
-> Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s a e f r
-> Vector (Raw s (VertexId' (Wrap s)) a)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r
-> Vector (Raw s (VertexId' (Wrap s)) v)
_rawVertexData
    setF :: PlanarSubdivision s a e f r
-> Vector v -> PlanarSubdivision s v e f r
setF PlanarSubdivision s a e f r
ps Vector v
v' = PlanarSubdivision s a e f r
psPlanarSubdivision s a e f r
-> (PlanarSubdivision s a e f r -> PlanarSubdivision s v e f r)
-> PlanarSubdivision s v e f r
forall a b. a -> (a -> b) -> b
&(Vector (Raw s (VertexId' (Wrap s)) a)
 -> Identity (Vector (Raw s (VertexId' (Wrap s)) v)))
-> PlanarSubdivision s a e f r
-> Identity (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r v.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (VertexId' (Wrap s)) v))
  (Vector (Raw s (VertexId' (Wrap s)) v))
rawVertexData ((Vector (Raw s (VertexId' (Wrap s)) a)
  -> Identity (Vector (Raw s (VertexId' (Wrap s)) v)))
 -> PlanarSubdivision s a e f r
 -> Identity (PlanarSubdivision s v e f r))
-> (Vector (Raw s (VertexId' (Wrap s)) a)
    -> Vector (Raw s (VertexId' (Wrap s)) v))
-> PlanarSubdivision s a e f r
-> PlanarSubdivision s v e f r
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (v -> Raw s (VertexId' (Wrap s)) a -> Raw s (VertexId' (Wrap s)) v)
-> Vector v
-> Vector (Raw s (VertexId' (Wrap s)) a)
-> Vector (Raw s (VertexId' (Wrap s)) v)
forall a b c. (a -> b -> c) -> Vector a -> Vector b -> Vector c
V.zipWith (\v
x' Raw s (VertexId' (Wrap s)) a
x -> Raw s (VertexId' (Wrap s)) a
xRaw s (VertexId' (Wrap s)) a
-> (Raw s (VertexId' (Wrap s)) a -> Raw s (VertexId' (Wrap s)) v)
-> Raw s (VertexId' (Wrap s)) v
forall a b. a -> (a -> b) -> b
&(a -> Identity v)
-> Raw s (VertexId' (Wrap s)) a
-> Identity (Raw s (VertexId' (Wrap s)) v)
forall k (s :: k) ia a b. Lens (Raw s ia a) (Raw s ia b) a b
dataVal ((a -> Identity v)
 -> Raw s (VertexId' (Wrap s)) a
 -> Identity (Raw s (VertexId' (Wrap s)) v))
-> v
-> Raw s (VertexId' (Wrap s)) a
-> Raw s (VertexId' (Wrap s)) v
forall s t a b. ASetter s t a b -> b -> s -> t
.~ v
x') Vector v
v'


-- | The tail of a dart, i.e. the vertex this dart is leaving from
--
-- running time: \(O(1)\)
tailOf      :: Dart s -> PlanarSubdivision s v e f r  -> VertexId' s
tailOf :: Dart s -> PlanarSubdivision s v e f r -> VertexId' s
tailOf Dart s
d PlanarSubdivision s v e f r
ps = let (ComponentId s
_,Dart (Wrap s)
d',PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g) = Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps
              in PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
gPlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Getting
     (VertexId' s)
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (VertexId' s)
-> VertexId' s
forall s a. s -> Getting a s a -> a
^.VertexId' (Wrap s)
-> Lens'
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (DataOf
        (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
        (VertexId' (Wrap s)))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf (Dart (Wrap s)
-> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> VertexId' (Wrap s)
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> VertexId' s
PG.tailOf Dart (Wrap s)
d' PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g)


-- | The vertex this dart is heading in to
--
-- running time: \(O(1)\)
headOf       :: Dart s -> PlanarSubdivision s v e f r  -> VertexId' s
headOf :: Dart s -> PlanarSubdivision s v e f r -> VertexId' s
headOf Dart s
d PlanarSubdivision s v e f r
ps = let (ComponentId s
_,Dart (Wrap s)
d',PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g) = Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps
              in PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
gPlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Getting
     (VertexId' s)
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (VertexId' s)
-> VertexId' s
forall s a. s -> Getting a s a -> a
^.VertexId' (Wrap s)
-> Lens'
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (DataOf
        (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
        (VertexId' (Wrap s)))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf (Dart (Wrap s)
-> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> VertexId' (Wrap s)
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> VertexId' s
PG.headOf Dart (Wrap s)
d' PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g)


-- | endPoints d g = (tailOf d g, headOf d g)
--
-- running time: \(O(1)\)
endPoints      :: Dart s -> PlanarSubdivision s v e f r
               -> (VertexId' s, VertexId' s)
endPoints :: Dart s -> PlanarSubdivision s v e f r -> (VertexId' s, VertexId' s)
endPoints Dart s
d PlanarSubdivision s v e f r
ps = (Dart s -> PlanarSubdivision s v e f r -> VertexId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> VertexId' s
tailOf Dart s
d PlanarSubdivision s v e f r
ps, Dart s -> PlanarSubdivision s v e f r -> VertexId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> VertexId' s
headOf Dart s
d PlanarSubdivision s v e f r
ps)


-- | All edges incident to vertex v, in counterclockwise order around v.
--
-- running time: \(O(k)\), where \(k\) is the number of edges reported.
incidentEdges                 :: VertexId' s -> PlanarSubdivision s v e f r
                              -> V.Vector (Dart s)
incidentEdges :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
incidentEdges VertexId' s
v PlanarSubdivision s v e f r
ps=  let (ComponentId s
_,VertexId' (Wrap s)
v',PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g) = VertexId' s
-> PlanarSubdivision s v e f r
-> (ComponentId s, VertexId' (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
VertexId' s
-> PlanarSubdivision s v e f r
-> (ComponentId s, VertexId' (Wrap s), Component s r)
asLocalV VertexId' s
v PlanarSubdivision s v e f r
ps
                         ds :: Vector (Dart (Wrap s))
ds       = VertexId' (Wrap s)
-> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Vector (Dart (Wrap s))
forall k (s :: k) v e f r.
VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s)
PG.incidentEdges VertexId' (Wrap s)
v' PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g
                     in (\Dart (Wrap s)
d -> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
gPlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Getting
     (Dart s)
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (Dart s)
-> Dart s
forall s a. s -> Getting a s a -> a
^.Dart (Wrap s)
-> Lens'
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (DataOf
        (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
        (Dart (Wrap s)))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart (Wrap s)
d) (Dart (Wrap s) -> Dart s)
-> Vector (Dart (Wrap s)) -> Vector (Dart s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Vector (Dart (Wrap s))
ds


-- | Given a dart d that points into some vertex v, report the next
-- dart e in the cyclic order around v.
--
-- running time: \(O(1)\)
nextIncidentEdge      :: Dart s -> PlanarSubdivision s v e f r -> Dart s
nextIncidentEdge :: Dart s -> PlanarSubdivision s v e f r -> Dart s
nextIncidentEdge Dart s
d PlanarSubdivision s v e f r
ps = let (ComponentId s
_,Dart (Wrap s)
d',PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g) = Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps
                            d'' :: Dart (Wrap s)
d''      = Dart (Wrap s)
-> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Dart (Wrap s)
forall k (s :: k) v e f r. Dart s -> PlaneGraph s v e f r -> Dart s
PG.nextIncidentEdge Dart (Wrap s)
d' PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g
                        in PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
gPlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Getting
     (Dart s)
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (Dart s)
-> Dart s
forall s a. s -> Getting a s a -> a
^.Dart (Wrap s)
-> Lens'
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (DataOf
        (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
        (Dart (Wrap s)))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart (Wrap s)
d''

-- | All edges incident to vertex v in incoming direction
-- (i.e. pointing into v) in counterclockwise order around v.
--
-- running time: \(O(k)\), where \(k) is the total number of incident edges of v
incomingEdges      :: VertexId' s -> PlanarSubdivision s v e f r -> V.Vector (Dart s)
incomingEdges :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
incomingEdges VertexId' s
v PlanarSubdivision s v e f r
ps = Dart s -> Dart s
orient (Dart s -> Dart s) -> Vector (Dart s) -> Vector (Dart s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
incidentEdges VertexId' s
v PlanarSubdivision s v e f r
ps
  where
    orient :: Dart s -> Dart s
orient Dart s
d = if Dart s -> PlanarSubdivision s v e f r -> VertexId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> VertexId' s
headOf Dart s
d PlanarSubdivision s v e f r
ps VertexId' s -> VertexId' s -> Bool
forall a. Eq a => a -> a -> Bool
== VertexId' s
v then Dart s
d else Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin Dart s
d

-- | All edges incident to vertex v in outgoing direction
-- (i.e. pointing away from v) in counterclockwise order around v.
--
-- running time: \(O(k)\), where \(k) is the total number of incident edges of v
outgoingEdges      :: VertexId' s -> PlanarSubdivision s v e f r  -> V.Vector (Dart s)
outgoingEdges :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
outgoingEdges VertexId' s
v PlanarSubdivision s v e f r
ps = Dart s -> Dart s
orient (Dart s -> Dart s) -> Vector (Dart s) -> Vector (Dart s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
incidentEdges VertexId' s
v PlanarSubdivision s v e f r
ps
  where
    orient :: Dart s -> Dart s
orient Dart s
d = if Dart s -> PlanarSubdivision s v e f r -> VertexId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> VertexId' s
tailOf Dart s
d PlanarSubdivision s v e f r
ps VertexId' s -> VertexId' s -> Bool
forall a. Eq a => a -> a -> Bool
== VertexId' s
v then Dart s
d else Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin Dart s
d


-- | Gets the neighbours of a particular vertex, in counterclockwise order
-- around the vertex.
--
-- running time: \(O(k)\), where \(k\) is the output size
neighboursOf      :: VertexId' s -> PlanarSubdivision s v e f r -> V.Vector (VertexId' s)
neighboursOf :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (VertexId' s)
neighboursOf VertexId' s
v PlanarSubdivision s v e f r
ps = (Dart s -> PlanarSubdivision s v e f r -> VertexId' s)
-> PlanarSubdivision s v e f r -> Dart s -> VertexId' s
forall a b c. (a -> b -> c) -> b -> a -> c
flip Dart s -> PlanarSubdivision s v e f r -> VertexId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> VertexId' s
tailOf PlanarSubdivision s v e f r
ps (Dart s -> VertexId' s) -> Vector (Dart s) -> Vector (VertexId' s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
incomingEdges VertexId' s
v PlanarSubdivision s v e f r
ps

-- | The face to the left of the dart
--
-- running time: \(O(1)\).
leftFace      :: Dart s -> PlanarSubdivision s v e f r  -> FaceId' s
leftFace :: Dart s -> PlanarSubdivision s v e f r -> FaceId' s
leftFace Dart s
d PlanarSubdivision s v e f r
ps = let (ComponentId s
_,Dart (Wrap s)
d',PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g) = Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps
                    fi :: FaceId' (Wrap s)
fi       = Dart (Wrap s)
-> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> FaceId' (Wrap s)
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> FaceId' s
PG.leftFace Dart (Wrap s)
d' PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g
                in PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
gPlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Getting
     (FaceId' s)
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (FaceId' s)
-> FaceId' s
forall s a. s -> Getting a s a -> a
^.FaceId' (Wrap s)
-> Lens'
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (DataOf
        (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
        (FaceId' (Wrap s)))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf FaceId' (Wrap s)
fi

-- | The face to the right of the dart
--
-- running time: \(O(1)\).
rightFace      :: Dart s -> PlanarSubdivision s v e f r  -> FaceId' s
rightFace :: Dart s -> PlanarSubdivision s v e f r -> FaceId' s
rightFace Dart s
d PlanarSubdivision s v e f r
ps = let (ComponentId s
_,Dart (Wrap s)
d',PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g) = Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps
                     fi :: FaceId' (Wrap s)
fi       = Dart (Wrap s)
-> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> FaceId' (Wrap s)
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> FaceId' s
PG.rightFace Dart (Wrap s)
d' PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g
                in PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
gPlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Getting
     (FaceId' s)
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (FaceId' s)
-> FaceId' s
forall s a. s -> Getting a s a -> a
^.FaceId' (Wrap s)
-> Lens'
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (DataOf
        (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
        (FaceId' (Wrap s)))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf FaceId' (Wrap s)
fi

-- | The darts on the outer boundary of the face, for internal faces
-- the darts are in clockwise order. For the outer face the darts are
-- in counterclockwise order, and the darts from various components are in no particular order.
--
--
-- running time: \(O(k)\), where \(k\) is the output size.
outerBoundaryDarts      :: FaceId' s -> PlanarSubdivision s v e f r  -> V.Vector (Dart s)
outerBoundaryDarts :: FaceId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
outerBoundaryDarts FaceId' s
f PlanarSubdivision s v e f r
ps = ((ComponentId s, FaceId' (Wrap s),
  PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
 -> Vector (Dart s))
-> Vector
     (ComponentId s, FaceId' (Wrap s),
      PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> Vector (Dart s)
forall a b. (a -> Vector b) -> Vector a -> Vector b
V.concatMap (ComponentId s, FaceId' (Wrap s),
 PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> Vector (Dart s)
forall k a (s :: k) v e f r.
(a, FaceId' s, PlaneGraph s v e f r) -> Vector e
single (Vector
   (ComponentId s, FaceId' (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
 -> Vector (Dart s))
-> (NonEmpty
      (ComponentId s, FaceId' (Wrap s),
       PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
    -> Vector
         (ComponentId s, FaceId' (Wrap s),
          PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r))
-> NonEmpty
     (ComponentId s, FaceId' (Wrap s),
      PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(ComponentId s, FaceId' (Wrap s),
  PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)]
-> Vector
     (ComponentId s, FaceId' (Wrap s),
      PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall a. [a] -> Vector a
V.fromList ([(ComponentId s, FaceId' (Wrap s),
   PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)]
 -> Vector
      (ComponentId s, FaceId' (Wrap s),
       PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r))
-> (NonEmpty
      (ComponentId s, FaceId' (Wrap s),
       PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
    -> [(ComponentId s, FaceId' (Wrap s),
         PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)])
-> NonEmpty
     (ComponentId s, FaceId' (Wrap s),
      PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> Vector
     (ComponentId s, FaceId' (Wrap s),
      PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty
  (ComponentId s, FaceId' (Wrap s),
   PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> [(ComponentId s, FaceId' (Wrap s),
     PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)]
forall a. NonEmpty a -> [a]
NonEmpty.toList (NonEmpty
   (ComponentId s, FaceId' (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
 -> Vector (Dart s))
-> NonEmpty
     (ComponentId s, FaceId' (Wrap s),
      PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
-> Vector (Dart s)
forall a b. (a -> b) -> a -> b
$ FaceId' s
-> PlanarSubdivision s v e f r
-> NonEmpty
     (ComponentId s, FaceId' (Wrap s),
      PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
FaceId' s
-> PlanarSubdivision s v e f r
-> NonEmpty (ComponentId s, FaceId' (Wrap s), Component s r)
asLocalF FaceId' s
f PlanarSubdivision s v e f r
ps
  where
    single :: (a, FaceId' s, PlaneGraph s v e f r) -> Vector e
single (a
_,FaceId' s
f',PlaneGraph s v e f r
g) = (\Dart s
d -> PlaneGraph s v e f r
gPlaneGraph s v e f r -> Getting e (PlaneGraph s v e f r) e -> e
forall s a. s -> Getting a s a -> a
^.Dart s
-> Lens'
     (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart s
d) (Dart s -> e) -> Vector (Dart s) -> Vector e
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> FaceId' s -> PlaneGraph s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
FaceId' s -> PlaneGraph s v e f r -> Vector (Dart s)
PG.boundary FaceId' s
f' PlaneGraph s v e f r
g

-- | Get the local face and component from a given face.
asLocalF                          :: FaceId' s -> PlanarSubdivision s v e f r
                                  -> NonEmpty (ComponentId s, FaceId' (Wrap s), Component s r)
asLocalF :: FaceId' s
-> PlanarSubdivision s v e f r
-> NonEmpty (ComponentId s, FaceId' (Wrap s), Component s r)
asLocalF (FaceId (VertexId Int
f)) PlanarSubdivision s v e f r
ps = case PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Endo (RawFace s f)) (PlanarSubdivision s v e f r) (RawFace s f)
-> RawFace s f
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (RawFace s f)
 -> Const (Endo (RawFace s f)) (Vector (RawFace s f)))
-> PlanarSubdivision s v e f r
-> Const (Endo (RawFace s f)) (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r f.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (RawFace s f))
  (Vector (RawFace s f))
rawFaceData((Vector (RawFace s f)
  -> Const (Endo (RawFace s f)) (Vector (RawFace s f)))
 -> PlanarSubdivision s v e f r
 -> Const (Endo (RawFace s f)) (PlanarSubdivision s v e f r))
-> ((RawFace s f -> Const (Endo (RawFace s f)) (RawFace s f))
    -> Vector (RawFace s f)
    -> Const (Endo (RawFace s f)) (Vector (RawFace s f)))
-> Getting
     (Endo (RawFace s f)) (PlanarSubdivision s v e f r) (RawFace s f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (RawFace s f))
-> Traversal'
     (Vector (RawFace s f)) (IxValue (Vector (RawFace s f)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (RawFace s f))
f of
      RawFace (Just (ComponentId s
ci,FaceId' (Wrap s)
f')) FaceData (Dart s) f
_        -> (ComponentId s
ci,FaceId' (Wrap s)
f',PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Component s r) (PlanarSubdivision s v e f r) (Component s r)
-> Component s r
forall s a. s -> Getting a s a -> a
^.ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
forall k (s :: k) v e f r.
ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
component ComponentId s
ci) (ComponentId s, FaceId' (Wrap s), Component s r)
-> [(ComponentId s, FaceId' (Wrap s), Component s r)]
-> NonEmpty (ComponentId s, FaceId' (Wrap s), Component s r)
forall a. a -> [a] -> NonEmpty a
:| []
      RawFace Maybe (ComponentId s, FaceId' (Wrap s))
Nothing (FaceData Seq (Dart s)
hs f
_) -> Dart s -> (ComponentId s, FaceId' (Wrap s), Component s r)
toLocalF (Dart s -> (ComponentId s, FaceId' (Wrap s), Component s r))
-> NonEmpty (Dart s)
-> NonEmpty (ComponentId s, FaceId' (Wrap s), Component s r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Dart s] -> NonEmpty (Dart s)
forall a. [a] -> NonEmpty a
NonEmpty.fromList (Seq (Dart s) -> [Dart s]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList Seq (Dart s)
hs)
  where
    toLocalF :: Dart s -> (ComponentId s, FaceId' (Wrap s), Component s r)
toLocalF Dart s
d = let (ComponentId s
ci,Dart (Wrap s)
d',Component s r
c) = Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps in (ComponentId s
ci,Dart (Wrap s) -> Component s r -> FaceId' (Wrap s)
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> FaceId' s
PG.leftFace Dart (Wrap s)
d' Component s r
c,Component s r
c)

-- | The vertices of the outer boundary of the face, for internal faces in
-- clockwise order, for the outer face in counter clockwise order.
--
--
-- running time: \(O(k)\), where \(k\) is the output size.
boundaryVertices      :: FaceId' s -> PlanarSubdivision s v e f r
                      -> V.Vector (VertexId' s)
boundaryVertices :: FaceId' s -> PlanarSubdivision s v e f r -> Vector (VertexId' s)
boundaryVertices FaceId' s
f PlanarSubdivision s v e f r
ps = (Dart s -> PlanarSubdivision s v e f r -> VertexId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> VertexId' s
`headOf` PlanarSubdivision s v e f r
ps) (Dart s -> VertexId' s) -> Vector (Dart s) -> Vector (VertexId' s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> FaceId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
FaceId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
outerBoundaryDarts FaceId' s
f PlanarSubdivision s v e f r
ps


-- | Lists the holes in this face, given as a list of darts to arbitrary darts
-- on those faces. The returned darts are on the outside of the hole, i.e. they are
-- incident to the given input face:
--
-- prop> all (\d -> leftFace d ps == fi) $ holesOf fi ps
--
-- running time: \(O(k)\), where \(k\) is the number of darts returned.
holesOf       :: FaceId' s -> PlanarSubdivision s v e f r -> Seq.Seq (Dart s)
holesOf :: FaceId' s -> PlanarSubdivision s v e f r -> Seq (Dart s)
holesOf FaceId' s
fi PlanarSubdivision s v e f r
ps = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Seq (Dart s)) (PlanarSubdivision s v e f r) (Seq (Dart s))
-> Seq (Dart s)
forall s a. s -> Getting a s a -> a
^.FaceId' s
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
forall k (s :: k) v e f r.
FaceId' s
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
faceDataOf FaceId' s
fi((FaceData (Dart s) f
  -> Const (Seq (Dart s)) (FaceData (Dart s) f))
 -> PlanarSubdivision s v e f r
 -> Const (Seq (Dart s)) (PlanarSubdivision s v e f r))
-> ((Seq (Dart s) -> Const (Seq (Dart s)) (Seq (Dart s)))
    -> FaceData (Dart s) f
    -> Const (Seq (Dart s)) (FaceData (Dart s) f))
-> Getting
     (Seq (Dart s)) (PlanarSubdivision s v e f r) (Seq (Dart s))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Seq (Dart s) -> Const (Seq (Dart s)) (Seq (Dart s)))
-> FaceData (Dart s) f
-> Const (Seq (Dart s)) (FaceData (Dart s) f)
forall h f1 h2.
Lens (FaceData h f1) (FaceData h2 f1) (Seq h) (Seq h2)
holes


--------------------------------------------------------------------------------
-- * Access data



asLocalD      :: Dart s -> PlanarSubdivision s v e f r
              -> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD :: Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps = let (Raw ComponentId s
ci Dart (Wrap s)
d' e
_) = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Endo (Raw s (Dart (Wrap s)) e))
     (PlanarSubdivision s v e f r)
     (Raw s (Dart (Wrap s)) e)
-> Raw s (Dart (Wrap s)) e
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Raw s (Dart (Wrap s)) e)
 -> Const
      (Endo (Raw s (Dart (Wrap s)) e))
      (Vector (Raw s (Dart (Wrap s)) e)))
-> PlanarSubdivision s v e f r
-> Const
     (Endo (Raw s (Dart (Wrap s)) e)) (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r e.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (Dart (Wrap s)) e))
  (Vector (Raw s (Dart (Wrap s)) e))
rawDartData((Vector (Raw s (Dart (Wrap s)) e)
  -> Const
       (Endo (Raw s (Dart (Wrap s)) e))
       (Vector (Raw s (Dart (Wrap s)) e)))
 -> PlanarSubdivision s v e f r
 -> Const
      (Endo (Raw s (Dart (Wrap s)) e)) (PlanarSubdivision s v e f r))
-> ((Raw s (Dart (Wrap s)) e
     -> Const
          (Endo (Raw s (Dart (Wrap s)) e)) (Raw s (Dart (Wrap s)) e))
    -> Vector (Raw s (Dart (Wrap s)) e)
    -> Const
         (Endo (Raw s (Dart (Wrap s)) e))
         (Vector (Raw s (Dart (Wrap s)) e)))
-> Getting
     (Endo (Raw s (Dart (Wrap s)) e))
     (PlanarSubdivision s v e f r)
     (Raw s (Dart (Wrap s)) e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Raw s (Dart (Wrap s)) e))
-> Traversal'
     (Vector (Raw s (Dart (Wrap s)) e))
     (IxValue (Vector (Raw s (Dart (Wrap s)) e)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (Dart s -> Int
forall a. Enum a => a -> Int
fromEnum Dart s
d)
                in (ComponentId s
ci,Dart (Wrap s)
d',PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Component s r) (PlanarSubdivision s v e f r) (Component s r)
-> Component s r
forall s a. s -> Getting a s a -> a
^.ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
forall k (s :: k) v e f r.
ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
component ComponentId s
ci)




asLocalV                 :: VertexId' s -> PlanarSubdivision s v e f r
                         -> (ComponentId s, VertexId' (Wrap s), Component s r)
asLocalV :: VertexId' s
-> PlanarSubdivision s v e f r
-> (ComponentId s, VertexId' (Wrap s), Component s r)
asLocalV (VertexId Int
v) PlanarSubdivision s v e f r
ps = let (Raw ComponentId s
ci VertexId' (Wrap s)
v' v
_) = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Endo (Raw s (VertexId' (Wrap s)) v))
     (PlanarSubdivision s v e f r)
     (Raw s (VertexId' (Wrap s)) v)
-> Raw s (VertexId' (Wrap s)) v
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Raw s (VertexId' (Wrap s)) v)
 -> Const
      (Endo (Raw s (VertexId' (Wrap s)) v))
      (Vector (Raw s (VertexId' (Wrap s)) v)))
-> PlanarSubdivision s v e f r
-> Const
     (Endo (Raw s (VertexId' (Wrap s)) v)) (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r v.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (VertexId' (Wrap s)) v))
  (Vector (Raw s (VertexId' (Wrap s)) v))
rawVertexData((Vector (Raw s (VertexId' (Wrap s)) v)
  -> Const
       (Endo (Raw s (VertexId' (Wrap s)) v))
       (Vector (Raw s (VertexId' (Wrap s)) v)))
 -> PlanarSubdivision s v e f r
 -> Const
      (Endo (Raw s (VertexId' (Wrap s)) v))
      (PlanarSubdivision s v e f r))
-> ((Raw s (VertexId' (Wrap s)) v
     -> Const
          (Endo (Raw s (VertexId' (Wrap s)) v))
          (Raw s (VertexId' (Wrap s)) v))
    -> Vector (Raw s (VertexId' (Wrap s)) v)
    -> Const
         (Endo (Raw s (VertexId' (Wrap s)) v))
         (Vector (Raw s (VertexId' (Wrap s)) v)))
-> Getting
     (Endo (Raw s (VertexId' (Wrap s)) v))
     (PlanarSubdivision s v e f r)
     (Raw s (VertexId' (Wrap s)) v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Raw s (VertexId' (Wrap s)) v))
-> Traversal'
     (Vector (Raw s (VertexId' (Wrap s)) v))
     (IxValue (Vector (Raw s (VertexId' (Wrap s)) v)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Raw s (VertexId' (Wrap s)) v))
v
                           in (ComponentId s
ci,VertexId' (Wrap s)
v',PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Component s r) (PlanarSubdivision s v e f r) (Component s r)
-> Component s r
forall s a. s -> Getting a s a -> a
^.ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
forall k (s :: k) v e f r.
ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
component ComponentId s
ci)

-- | Note that using the setting part of this lens may be very expensive!!
vertexDataOf               :: VertexId' s
                           -> Lens' (PlanarSubdivision s v e f r ) (VertexData r v)
vertexDataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
vertexDataOf (VertexId Int
vi) = (PlanarSubdivision s v e f r -> VertexData r v)
-> (PlanarSubdivision s v e f r
    -> VertexData r v -> PlanarSubdivision s v e f r)
-> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarSubdivision s v e f r -> VertexData r v
get' PlanarSubdivision s v e f r
-> VertexData r v -> PlanarSubdivision s v e f r
set''
  where
    get' :: PlanarSubdivision s v e f r -> VertexData r v
get' PlanarSubdivision s v e f r
ps = let (Raw ComponentId s
ci VertexId' (Wrap s)
wvdi v
x) = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Endo (Raw s (VertexId' (Wrap s)) v))
     (PlanarSubdivision s v e f r)
     (Raw s (VertexId' (Wrap s)) v)
-> Raw s (VertexId' (Wrap s)) v
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Raw s (VertexId' (Wrap s)) v)
 -> Const
      (Endo (Raw s (VertexId' (Wrap s)) v))
      (Vector (Raw s (VertexId' (Wrap s)) v)))
-> PlanarSubdivision s v e f r
-> Const
     (Endo (Raw s (VertexId' (Wrap s)) v)) (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r v.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (VertexId' (Wrap s)) v))
  (Vector (Raw s (VertexId' (Wrap s)) v))
rawVertexData((Vector (Raw s (VertexId' (Wrap s)) v)
  -> Const
       (Endo (Raw s (VertexId' (Wrap s)) v))
       (Vector (Raw s (VertexId' (Wrap s)) v)))
 -> PlanarSubdivision s v e f r
 -> Const
      (Endo (Raw s (VertexId' (Wrap s)) v))
      (PlanarSubdivision s v e f r))
-> ((Raw s (VertexId' (Wrap s)) v
     -> Const
          (Endo (Raw s (VertexId' (Wrap s)) v))
          (Raw s (VertexId' (Wrap s)) v))
    -> Vector (Raw s (VertexId' (Wrap s)) v)
    -> Const
         (Endo (Raw s (VertexId' (Wrap s)) v))
         (Vector (Raw s (VertexId' (Wrap s)) v)))
-> Getting
     (Endo (Raw s (VertexId' (Wrap s)) v))
     (PlanarSubdivision s v e f r)
     (Raw s (VertexId' (Wrap s)) v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Raw s (VertexId' (Wrap s)) v))
-> Traversal'
     (Vector (Raw s (VertexId' (Wrap s)) v))
     (IxValue (Vector (Raw s (VertexId' (Wrap s)) v)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Raw s (VertexId' (Wrap s)) v))
vi
                  vd :: VertexData r (VertexId' s)
vd              = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (VertexData r (VertexId' s))
     (PlanarSubdivision s v e f r)
     (VertexData r (VertexId' s))
-> VertexData r (VertexId' s)
forall s a. s -> Getting a s a -> a
^.ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
forall k (s :: k) v e f r.
ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
component ComponentId s
ci((Component s r
  -> Const (VertexData r (VertexId' s)) (Component s r))
 -> PlanarSubdivision s v e f r
 -> Const
      (VertexData r (VertexId' s)) (PlanarSubdivision s v e f r))
-> ((VertexData r (VertexId' s)
     -> Const (VertexData r (VertexId' s)) (VertexData r (VertexId' s)))
    -> Component s r
    -> Const (VertexData r (VertexId' s)) (Component s r))
-> Getting
     (VertexData r (VertexId' s))
     (PlanarSubdivision s v e f r)
     (VertexData r (VertexId' s))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.VertexId' (Wrap s)
-> Lens' (Component s r) (VertexData r (VertexId' s))
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlaneGraph s v e f r) (VertexData r v)
PG.vertexDataOf VertexId' (Wrap s)
wvdi
              in VertexData r (VertexId' s)
vdVertexData r (VertexId' s)
-> (VertexData r (VertexId' s) -> VertexData r v) -> VertexData r v
forall a b. a -> (a -> b) -> b
&(VertexId' s -> Identity v)
-> VertexData r (VertexId' s) -> Identity (VertexData r v)
forall r v1 v2. Lens (VertexData r v1) (VertexData r v2) v1 v2
vData ((VertexId' s -> Identity v)
 -> VertexData r (VertexId' s) -> Identity (VertexData r v))
-> v -> VertexData r (VertexId' s) -> VertexData r v
forall s t a b. ASetter s t a b -> b -> s -> t
.~ v
x
    set'' :: PlanarSubdivision s v e f r
-> VertexData r v -> PlanarSubdivision s v e f r
set'' PlanarSubdivision s v e f r
ps VertexData r v
x = let (Raw ComponentId s
ci VertexId' (Wrap s)
wvdi v
_)  = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Endo (Raw s (VertexId' (Wrap s)) v))
     (PlanarSubdivision s v e f r)
     (Raw s (VertexId' (Wrap s)) v)
-> Raw s (VertexId' (Wrap s)) v
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Raw s (VertexId' (Wrap s)) v)
 -> Const
      (Endo (Raw s (VertexId' (Wrap s)) v))
      (Vector (Raw s (VertexId' (Wrap s)) v)))
-> PlanarSubdivision s v e f r
-> Const
     (Endo (Raw s (VertexId' (Wrap s)) v)) (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r v.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (VertexId' (Wrap s)) v))
  (Vector (Raw s (VertexId' (Wrap s)) v))
rawVertexData((Vector (Raw s (VertexId' (Wrap s)) v)
  -> Const
       (Endo (Raw s (VertexId' (Wrap s)) v))
       (Vector (Raw s (VertexId' (Wrap s)) v)))
 -> PlanarSubdivision s v e f r
 -> Const
      (Endo (Raw s (VertexId' (Wrap s)) v))
      (PlanarSubdivision s v e f r))
-> ((Raw s (VertexId' (Wrap s)) v
     -> Const
          (Endo (Raw s (VertexId' (Wrap s)) v))
          (Raw s (VertexId' (Wrap s)) v))
    -> Vector (Raw s (VertexId' (Wrap s)) v)
    -> Const
         (Endo (Raw s (VertexId' (Wrap s)) v))
         (Vector (Raw s (VertexId' (Wrap s)) v)))
-> Getting
     (Endo (Raw s (VertexId' (Wrap s)) v))
     (PlanarSubdivision s v e f r)
     (Raw s (VertexId' (Wrap s)) v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Raw s (VertexId' (Wrap s)) v))
-> Traversal'
     (Vector (Raw s (VertexId' (Wrap s)) v))
     (IxValue (Vector (Raw s (VertexId' (Wrap s)) v)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Raw s (VertexId' (Wrap s)) v))
vi
                 in PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> (PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r)
-> PlanarSubdivision s v e f r
forall a b. a -> (a -> b) -> b
&(Vector (Raw s (VertexId' (Wrap s)) v)
 -> Identity (Vector (Raw s (VertexId' (Wrap s)) v)))
-> PlanarSubdivision s v e f r
-> Identity (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r v.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (VertexId' (Wrap s)) v))
  (Vector (Raw s (VertexId' (Wrap s)) v))
rawVertexData((Vector (Raw s (VertexId' (Wrap s)) v)
  -> Identity (Vector (Raw s (VertexId' (Wrap s)) v)))
 -> PlanarSubdivision s v e f r
 -> Identity (PlanarSubdivision s v e f r))
-> ((v -> Identity v)
    -> Vector (Raw s (VertexId' (Wrap s)) v)
    -> Identity (Vector (Raw s (VertexId' (Wrap s)) v)))
-> (v -> Identity v)
-> PlanarSubdivision s v e f r
-> Identity (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Raw s (VertexId' (Wrap s)) v))
-> Traversal'
     (Vector (Raw s (VertexId' (Wrap s)) v))
     (IxValue (Vector (Raw s (VertexId' (Wrap s)) v)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Raw s (VertexId' (Wrap s)) v))
vi((Raw s (VertexId' (Wrap s)) v
  -> Identity (Raw s (VertexId' (Wrap s)) v))
 -> Vector (Raw s (VertexId' (Wrap s)) v)
 -> Identity (Vector (Raw s (VertexId' (Wrap s)) v)))
-> ((v -> Identity v)
    -> Raw s (VertexId' (Wrap s)) v
    -> Identity (Raw s (VertexId' (Wrap s)) v))
-> (v -> Identity v)
-> Vector (Raw s (VertexId' (Wrap s)) v)
-> Identity (Vector (Raw s (VertexId' (Wrap s)) v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(v -> Identity v)
-> Raw s (VertexId' (Wrap s)) v
-> Identity (Raw s (VertexId' (Wrap s)) v)
forall k (s :: k) ia a b. Lens (Raw s ia a) (Raw s ia b) a b
dataVal                ((v -> Identity v)
 -> PlanarSubdivision s v e f r
 -> Identity (PlanarSubdivision s v e f r))
-> v -> PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r
forall s t a b. ASetter s t a b -> b -> s -> t
.~ (VertexData r v
xVertexData r v -> Getting v (VertexData r v) v -> v
forall s a. s -> Getting a s a -> a
^.Getting v (VertexData r v) v
forall r v1 v2. Lens (VertexData r v1) (VertexData r v2) v1 v2
vData)
                      PlanarSubdivision s v e f r
-> (PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r)
-> PlanarSubdivision s v e f r
forall a b. a -> (a -> b) -> b
&ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
forall k (s :: k) v e f r.
ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
component ComponentId s
ci((Component s r -> Identity (Component s r))
 -> PlanarSubdivision s v e f r
 -> Identity (PlanarSubdivision s v e f r))
-> ((Point 2 r -> Identity (Point 2 r))
    -> Component s r -> Identity (Component s r))
-> (Point 2 r -> Identity (Point 2 r))
-> PlanarSubdivision s v e f r
-> Identity (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.VertexId' (Wrap s)
-> Lens' (Component s r) (VertexData r (VertexId' s))
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlaneGraph s v e f r) (VertexData r v)
PG.vertexDataOf VertexId' (Wrap s)
wvdi((VertexData r (VertexId' s)
  -> Identity (VertexData r (VertexId' s)))
 -> Component s r -> Identity (Component s r))
-> ((Point 2 r -> Identity (Point 2 r))
    -> VertexData r (VertexId' s)
    -> Identity (VertexData r (VertexId' s)))
-> (Point 2 r -> Identity (Point 2 r))
-> Component s r
-> Identity (Component s r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Identity (Point 2 r))
-> VertexData r (VertexId' s)
-> Identity (VertexData r (VertexId' s))
forall r v1 r2.
Lens (VertexData r v1) (VertexData r2 v1) (Point 2 r) (Point 2 r2)
location ((Point 2 r -> Identity (Point 2 r))
 -> PlanarSubdivision s v e f r
 -> Identity (PlanarSubdivision s v e f r))
-> Point 2 r
-> PlanarSubdivision s v e f r
-> PlanarSubdivision s v e f r
forall s t a b. ASetter s t a b -> b -> s -> t
.~ (VertexData r v
xVertexData r v
-> Getting (Point 2 r) (VertexData r v) (Point 2 r) -> Point 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Point 2 r) (VertexData r v) (Point 2 r)
forall r v1 r2.
Lens (VertexData r v1) (VertexData r2 v1) (Point 2 r) (Point 2 r2)
location)

locationOf   :: VertexId' s -> Lens' (PlanarSubdivision s v e f r ) (Point 2 r)
locationOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (Point 2 r)
locationOf VertexId' s
v = VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
vertexDataOf VertexId' s
v((VertexData r v -> f (VertexData r v))
 -> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f r))
-> ((Point 2 r -> f (Point 2 r))
    -> VertexData r v -> f (VertexData r v))
-> (Point 2 r -> f (Point 2 r))
-> PlanarSubdivision s v e f r
-> f (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> f (Point 2 r))
-> VertexData r v -> f (VertexData r v)
forall r v1 r2.
Lens (VertexData r v1) (VertexData r2 v1) (Point 2 r) (Point 2 r2)
location


faceDataOf    :: FaceId' s -> Lens' (PlanarSubdivision s v e f r)
                                    (FaceData (Dart s) f)
faceDataOf :: FaceId' s
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
faceDataOf FaceId' s
fi = (PlanarSubdivision s v e f r -> FaceData (Dart s) f)
-> (PlanarSubdivision s v e f r
    -> FaceData (Dart s) f -> PlanarSubdivision s v e f r)
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens PlanarSubdivision s v e f r -> FaceData (Dart s) f
getF PlanarSubdivision s v e f r
-> FaceData (Dart s) f -> PlanarSubdivision s v e f r
setF
  where
    (FaceId (VertexId Int
i)) = FaceId' s
fi
    getF :: PlanarSubdivision s v e f r -> FaceData (Dart s) f
getF PlanarSubdivision s v e f r
ps = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Endo (FaceData (Dart s) f))
     (PlanarSubdivision s v e f r)
     (FaceData (Dart s) f)
-> FaceData (Dart s) f
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (RawFace s f)
 -> Const (Endo (FaceData (Dart s) f)) (Vector (RawFace s f)))
-> PlanarSubdivision s v e f r
-> Const (Endo (FaceData (Dart s) f)) (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r f.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (RawFace s f))
  (Vector (RawFace s f))
rawFaceData((Vector (RawFace s f)
  -> Const (Endo (FaceData (Dart s) f)) (Vector (RawFace s f)))
 -> PlanarSubdivision s v e f r
 -> Const
      (Endo (FaceData (Dart s) f)) (PlanarSubdivision s v e f r))
-> ((FaceData (Dart s) f
     -> Const (Endo (FaceData (Dart s) f)) (FaceData (Dart s) f))
    -> Vector (RawFace s f)
    -> Const (Endo (FaceData (Dart s) f)) (Vector (RawFace s f)))
-> Getting
     (Endo (FaceData (Dart s) f))
     (PlanarSubdivision s v e f r)
     (FaceData (Dart s) f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (RawFace s f))
-> Traversal'
     (Vector (RawFace s f)) (IxValue (Vector (RawFace s f)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (RawFace s f))
i((RawFace s f -> Const (Endo (FaceData (Dart s) f)) (RawFace s f))
 -> Vector (RawFace s f)
 -> Const (Endo (FaceData (Dart s) f)) (Vector (RawFace s f)))
-> ((FaceData (Dart s) f
     -> Const (Endo (FaceData (Dart s) f)) (FaceData (Dart s) f))
    -> RawFace s f -> Const (Endo (FaceData (Dart s) f)) (RawFace s f))
-> (FaceData (Dart s) f
    -> Const (Endo (FaceData (Dart s) f)) (FaceData (Dart s) f))
-> Vector (RawFace s f)
-> Const (Endo (FaceData (Dart s) f)) (Vector (RawFace s f))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(FaceData (Dart s) f
 -> Const (Endo (FaceData (Dart s) f)) (FaceData (Dart s) f))
-> RawFace s f -> Const (Endo (FaceData (Dart s) f)) (RawFace s f)
forall k (s :: k) f1 f2.
Lens
  (RawFace s f1)
  (RawFace s f2)
  (FaceData (Dart s) f1)
  (FaceData (Dart s) f2)
faceDataVal
    setF :: PlanarSubdivision s v e f r
-> FaceData (Dart s) f -> PlanarSubdivision s v e f r
setF PlanarSubdivision s v e f r
ps FaceData (Dart s) f
fd = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> (PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r)
-> PlanarSubdivision s v e f r
forall a b. a -> (a -> b) -> b
&(Vector (RawFace s f) -> Identity (Vector (RawFace s f)))
-> PlanarSubdivision s v e f r
-> Identity (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r f.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (RawFace s f))
  (Vector (RawFace s f))
rawFaceData((Vector (RawFace s f) -> Identity (Vector (RawFace s f)))
 -> PlanarSubdivision s v e f r
 -> Identity (PlanarSubdivision s v e f r))
-> ((FaceData (Dart s) f -> Identity (FaceData (Dart s) f))
    -> Vector (RawFace s f) -> Identity (Vector (RawFace s f)))
-> (FaceData (Dart s) f -> Identity (FaceData (Dart s) f))
-> PlanarSubdivision s v e f r
-> Identity (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (RawFace s f))
-> Traversal'
     (Vector (RawFace s f)) (IxValue (Vector (RawFace s f)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (RawFace s f))
i((RawFace s f -> Identity (RawFace s f))
 -> Vector (RawFace s f) -> Identity (Vector (RawFace s f)))
-> ((FaceData (Dart s) f -> Identity (FaceData (Dart s) f))
    -> RawFace s f -> Identity (RawFace s f))
-> (FaceData (Dart s) f -> Identity (FaceData (Dart s) f))
-> Vector (RawFace s f)
-> Identity (Vector (RawFace s f))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(FaceData (Dart s) f -> Identity (FaceData (Dart s) f))
-> RawFace s f -> Identity (RawFace s f)
forall k (s :: k) f1 f2.
Lens
  (RawFace s f1)
  (RawFace s f2)
  (FaceData (Dart s) f1)
  (FaceData (Dart s) f2)
faceDataVal ((FaceData (Dart s) f -> Identity (FaceData (Dart s) f))
 -> PlanarSubdivision s v e f r
 -> Identity (PlanarSubdivision s v e f r))
-> FaceData (Dart s) f
-> PlanarSubdivision s v e f r
-> PlanarSubdivision s v e f r
forall s t a b. ASetter s t a b -> b -> s -> t
.~ FaceData (Dart s) f
fd

instance HasDataOf (PlanarSubdivision s v e f r) (VertexId' s) where
  type DataOf (PlanarSubdivision s v e f r) (VertexId' s) = v
  dataOf :: VertexId' s
-> Lens'
     (PlanarSubdivision s v e f r)
     (DataOf (PlanarSubdivision s v e f r) (VertexId' s))
dataOf VertexId' s
v = VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
vertexDataOf VertexId' s
v((VertexData r v -> f (VertexData r v))
 -> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f r))
-> ((v -> f v) -> VertexData r v -> f (VertexData r v))
-> (v -> f v)
-> PlanarSubdivision s v e f r
-> f (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(v -> f v) -> VertexData r v -> f (VertexData r v)
forall r v1 v2. Lens (VertexData r v1) (VertexData r v2) v1 v2
vData

instance HasDataOf (PlanarSubdivision s v e f r) (Dart s) where
  type DataOf (PlanarSubdivision s v e f r) (Dart s) = e
  dataOf :: Dart s
-> Lens'
     (PlanarSubdivision s v e f r)
     (DataOf (PlanarSubdivision s v e f r) (Dart s))
dataOf Dart s
d = (Vector (Raw s (Dart (Wrap s)) e)
 -> f (Vector (Raw s (Dart (Wrap s)) e)))
-> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f r)
forall k (s :: k) v e f r e.
Lens
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f r)
  (Vector (Raw s (Dart (Wrap s)) e))
  (Vector (Raw s (Dart (Wrap s)) e))
rawDartData((Vector (Raw s (Dart (Wrap s)) e)
  -> f (Vector (Raw s (Dart (Wrap s)) e)))
 -> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f r))
-> ((e -> f e)
    -> Vector (Raw s (Dart (Wrap s)) e)
    -> f (Vector (Raw s (Dart (Wrap s)) e)))
-> (e -> f e)
-> PlanarSubdivision s v e f r
-> f (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Traversing
  (->)
  f
  (Vector (Raw s (Dart (Wrap s)) e))
  (Vector (Raw s (Dart (Wrap s)) e))
  (Raw s (Dart (Wrap s)) e)
  (Raw s (Dart (Wrap s)) e)
-> Over
     (->)
     f
     (Vector (Raw s (Dart (Wrap s)) e))
     (Vector (Raw s (Dart (Wrap s)) e))
     (Raw s (Dart (Wrap s)) e)
     (Raw s (Dart (Wrap s)) e)
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 (Index (Vector (Raw s (Dart (Wrap s)) e))
-> Traversal'
     (Vector (Raw s (Dart (Wrap s)) e))
     (IxValue (Vector (Raw s (Dart (Wrap s)) e)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (Dart s -> Int
forall a. Enum a => a -> Int
fromEnum Dart s
d))Over
  (->)
  f
  (Vector (Raw s (Dart (Wrap s)) e))
  (Vector (Raw s (Dart (Wrap s)) e))
  (Raw s (Dart (Wrap s)) e)
  (Raw s (Dart (Wrap s)) e)
-> ((e -> f e)
    -> Raw s (Dart (Wrap s)) e -> f (Raw s (Dart (Wrap s)) e))
-> (e -> f e)
-> Vector (Raw s (Dart (Wrap s)) e)
-> f (Vector (Raw s (Dart (Wrap s)) e))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(e -> f e)
-> Raw s (Dart (Wrap s)) e -> f (Raw s (Dart (Wrap s)) e)
forall k (s :: k) ia a b. Lens (Raw s ia a) (Raw s ia b) a b
dataVal

instance HasDataOf (PlanarSubdivision s v e f r) (FaceId' s) where
  type DataOf (PlanarSubdivision s v e f r) (FaceId' s) = f
  dataOf :: FaceId' s
-> Lens'
     (PlanarSubdivision s v e f r)
     (DataOf (PlanarSubdivision s v e f r) (FaceId' s))
dataOf FaceId' s
f = FaceId' s
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
forall k (s :: k) v e f r.
FaceId' s
-> Lens' (PlanarSubdivision s v e f r) (FaceData (Dart s) f)
faceDataOf FaceId' s
f((FaceData (Dart s) f -> f (FaceData (Dart s) f))
 -> PlanarSubdivision s v e f r -> f (PlanarSubdivision s v e f r))
-> ((f -> f f) -> FaceData (Dart s) f -> f (FaceData (Dart s) f))
-> (f -> f f)
-> PlanarSubdivision s v e f r
-> f (PlanarSubdivision s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(f -> f f) -> FaceData (Dart s) f -> f (FaceData (Dart s) f)
forall h f1 f2. Lens (FaceData h f1) (FaceData h f2) f1 f2
fData


-- -- | Traverse the vertices
-- --
-- traverseVertices   :: Applicative m
--                    => (VertexId' s -> v -> m v')
--                    -> PlanarSubdivision s v e f r
--                    -> m (PlanarSubdivision s v' e f r)
-- traverseVertices f = itraverseOf (vertexData.itraversed) (\i -> f (VertexId i))

-- -- | Traverses the darts
-- --
-- traverseDarts   :: Applicative m
--                 => (Dart s -> e -> m e')
--                 -> PlanarSubdivision s v e f r
--                 -> m (PlaneGraph s v e' f r)
-- traverseDarts f = traverseOf (dart) (PG.traverseDarts f)


-- -- | Traverses the faces
-- --
-- traverseFaces   :: Applicative m
--                 => (FaceId' s  -> f -> m f')
--                 -> PlaneGraph s v e f r
--                 -> m (PlaneGraph s v e f' r)
-- traverseFaces f = traverseOf graph (PG.traverseFaces f)


-- | Getter for the data at the endpoints of a dart
--
-- running time: \(O(1)\)
endPointsOf   :: Dart s -> Getter (PlanarSubdivision s v e f r )
                                  (VertexData r v, VertexData r v)
endPointsOf :: Dart s
-> Getter
     (PlanarSubdivision s v e f r) (VertexData r v, VertexData r v)
endPointsOf Dart s
d = (PlanarSubdivision s v e f r -> (VertexData r v, VertexData r v))
-> Optic'
     (->)
     f
     (PlanarSubdivision s v e f r)
     (VertexData r v, VertexData r v)
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to (Dart s
-> PlanarSubdivision s v e f r -> (VertexData r v, VertexData r v)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r -> (VertexData r v, VertexData r v)
endPointData Dart s
d)

-- | data corresponding to the endpoints of the dart
--
-- running time: \(O(1)\)
endPointData      :: Dart s -> PlanarSubdivision s v e f r
                  ->  (VertexData r v, VertexData r v)
endPointData :: Dart s
-> PlanarSubdivision s v e f r -> (VertexData r v, VertexData r v)
endPointData Dart s
d PlanarSubdivision s v e f r
ps = let (VertexId' s
u,VertexId' s
v) = Dart s -> PlanarSubdivision s v e f r -> (VertexId' s, VertexId' s)
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> (VertexId' s, VertexId' s)
endPoints Dart s
d PlanarSubdivision s v e f r
ps
                    in (PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (VertexData r v) (PlanarSubdivision s v e f r) (VertexData r v)
-> VertexData r v
forall s a. s -> Getting a s a -> a
^.VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
vertexDataOf VertexId' s
u, PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (VertexData r v) (PlanarSubdivision s v e f r) (VertexData r v)
-> VertexData r v
forall s a. s -> Getting a s a -> a
^.VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
vertexDataOf VertexId' s
v)


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

-- | gets the id of the outer face
--
-- running time: \(O(1)\)
outerFaceId :: PlanarSubdivision s v e f r -> FaceId' s
outerFaceId :: PlanarSubdivision s v e f r -> FaceId' s
outerFaceId = FaceId' s -> PlanarSubdivision s v e f r -> FaceId' s
forall a b. a -> b -> a
const (FaceId' s -> PlanarSubdivision s v e f r -> FaceId' s)
-> (Int -> FaceId' s)
-> Int
-> PlanarSubdivision s v e f r
-> FaceId' s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VertexId s 'Dual -> FaceId' s
forall k (s :: k) (w :: World). VertexId s (DualOf w) -> FaceId s w
FaceId (VertexId s 'Dual -> FaceId' s)
-> (Int -> VertexId s 'Dual) -> Int -> FaceId' s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> VertexId s 'Dual
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId (Int -> PlanarSubdivision s v e f r -> FaceId' s)
-> Int -> PlanarSubdivision s v e f r -> FaceId' s
forall a b. (a -> b) -> a -> b
$ Int
0
  -- our invariant tells us the outerface is always at faceId 0

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

-- | Reports all edges as line segments
edgeSegments    :: PlanarSubdivision s v e f r -> V.Vector (Dart s, LineSegment 2 v r :+ e)
edgeSegments :: PlanarSubdivision s v e f r
-> Vector (Dart s, LineSegment 2 v r :+ e)
edgeSegments PlanarSubdivision s v e f r
ps = (\Dart s
d -> (Dart s
d,Dart s -> PlanarSubdivision s v e f r -> LineSegment 2 v r :+ e
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> LineSegment 2 v r :+ e
edgeSegment Dart s
d PlanarSubdivision s v e f r
ps)) (Dart s -> (Dart s, LineSegment 2 v r :+ e))
-> Vector (Dart s) -> Vector (Dart s, LineSegment 2 v r :+ e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r -> Vector (Dart s)
edges' PlanarSubdivision s v e f r
ps


-- | Given a dart and the subdivision constructs the line segment representing it
--
-- \(O(1)\)
edgeSegment      :: Dart s -> PlanarSubdivision s v e f r -> LineSegment 2 v r :+ e
edgeSegment :: Dart s -> PlanarSubdivision s v e f r -> LineSegment 2 v r :+ e
edgeSegment Dart s
d PlanarSubdivision s v e f r
ps = let (Point 2 r :+ v
p,Point 2 r :+ v
q) = (VertexData r v -> Point 2 r :+ v)
-> (VertexData r v -> Point 2 r :+ v)
-> (VertexData r v, VertexData r v)
-> (Point 2 r :+ v, Point 2 r :+ v)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
PG.vtxDataToExt VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
PG.vtxDataToExt ((VertexData r v, VertexData r v)
 -> (Point 2 r :+ v, Point 2 r :+ v))
-> (VertexData r v, VertexData r v)
-> (Point 2 r :+ v, Point 2 r :+ v)
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (VertexData r v, VertexData r v)
     (PlanarSubdivision s v e f r)
     (VertexData r v, VertexData r v)
-> (VertexData r v, VertexData r v)
forall s a. s -> Getting a s a -> a
^.Dart s
-> Getter
     (PlanarSubdivision s v e f r) (VertexData r v, VertexData r v)
forall k (s :: k) v e f r.
Dart s
-> Getter
     (PlanarSubdivision s v e f r) (VertexData r v, VertexData r v)
endPointsOf Dart s
d
                   in (Point 2 r :+ v) -> (Point 2 r :+ v) -> LineSegment 2 v r
forall (d :: Nat) r p.
(Point d r :+ p) -> (Point d r :+ p) -> LineSegment d p r
ClosedLineSegment Point 2 r :+ v
p Point 2 r :+ v
q LineSegment 2 v r -> e -> LineSegment 2 v r :+ e
forall core extra. core -> extra -> core :+ extra
:+ PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting e (PlanarSubdivision s v e f r) e -> e
forall s a. s -> Getting a s a -> a
^.Dart s
-> Lens'
     (PlanarSubdivision s v e f r)
     (DataOf (PlanarSubdivision s v e f r) (Dart s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart s
d


-- | Generates the darts incident to a face, starting with the given dart.
--
--
-- \(O(k)\), where \(k\) is the number of darts reported
boundary'     :: Dart s -> PlanarSubdivision s v e f r -> V.Vector (Dart s)
boundary' :: Dart s -> PlanarSubdivision s v e f r -> Vector (Dart s)
boundary' Dart s
d PlanarSubdivision s v e f r
ps = let (ComponentId s
_,Dart (Wrap s)
d',PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g) = Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s),
    PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
forall k (s :: k) v e f r.
Dart s
-> PlanarSubdivision s v e f r
-> (ComponentId s, Dart (Wrap s), Component s r)
asLocalD Dart s
d PlanarSubdivision s v e f r
ps
                 in (\Dart (Wrap s)
d'' -> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
gPlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Getting
     (Dart s)
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (Dart s)
-> Dart s
forall s a. s -> Getting a s a -> a
^.Dart (Wrap s)
-> Lens'
     (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
     (DataOf
        (PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r)
        (Dart (Wrap s)))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart (Wrap s)
d'') (Dart (Wrap s) -> Dart s)
-> Vector (Dart (Wrap s)) -> Vector (Dart s)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Dart (Wrap s)
-> PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
-> Vector (Dart (Wrap s))
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> Vector (Dart s)
PG.boundary' Dart (Wrap s)
d' PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceId' s) r
g


-- | Constructs the outer boundary of the face
--
-- \(O(k)\), where \(k\) is the complexity of the outer boundary of the face
rawFaceBoundary      :: FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
rawFaceBoundary :: FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
rawFaceBoundary FaceId' s
i PlanarSubdivision s v e f r
ps = [Point 2 r :+ v] -> SimplePolygon v r
forall r p. [Point 2 r :+ p] -> SimplePolygon p r
unsafeFromPoints [Point 2 r :+ v]
pts SimplePolygon v r -> f -> SimplePolygon v r :+ f
forall core extra. core -> extra -> core :+ extra
:+ (PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting f (PlanarSubdivision s v e f r) f -> f
forall s a. s -> Getting a s a -> a
^.FaceId' s
-> Lens'
     (PlanarSubdivision s v e f r)
     (DataOf (PlanarSubdivision s v e f r) (FaceId' s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf FaceId' s
i)
  where
    d :: Dart s
d   = Vector (Dart s) -> Dart s
forall a. Vector a -> a
V.head (Vector (Dart s) -> Dart s) -> Vector (Dart s) -> Dart s
forall a b. (a -> b) -> a -> b
$ FaceId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
FaceId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)
outerBoundaryDarts FaceId' s
i PlanarSubdivision s v e f r
ps
    pts :: [Point 2 r :+ v]
pts = (\Dart s
d' -> VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
PG.vtxDataToExt (VertexData r v -> Point 2 r :+ v)
-> VertexData r v -> Point 2 r :+ v
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (VertexData r v) (PlanarSubdivision s v e f r) (VertexData r v)
-> VertexData r v
forall s a. s -> Getting a s a -> a
^.VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlanarSubdivision s v e f r) (VertexData r v)
vertexDataOf (Dart s -> PlanarSubdivision s v e f r -> VertexId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> VertexId' s
headOf Dart s
d' PlanarSubdivision s v e f r
ps))
       (Dart s -> Point 2 r :+ v) -> [Dart s] -> [Point 2 r :+ v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Vector (Dart s) -> [Dart s]
forall a. Vector a -> [a]
V.toList (Dart s -> PlanarSubdivision s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> Vector (Dart s)
boundary' Dart s
d PlanarSubdivision s v e f r
ps)


-- | Constructs the boundary of the given face
--
-- \(O(k)\), where \(k\) is the complexity of the face
rawFacePolygon      :: FaceId' s -> PlanarSubdivision s v e f r
                    -> SomePolygon v r :+ f
rawFacePolygon :: FaceId' s -> PlanarSubdivision s v e f r -> SomePolygon v r :+ f
rawFacePolygon FaceId' s
i PlanarSubdivision s v e f r
ps = case Seq (Dart s) -> [Dart s]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Seq (Dart s) -> [Dart s]) -> Seq (Dart s) -> [Dart s]
forall a b. (a -> b) -> a -> b
$ FaceId' s -> PlanarSubdivision s v e f r -> Seq (Dart s)
forall k (s :: k) v e f r.
FaceId' s -> PlanarSubdivision s v e f r -> Seq (Dart s)
holesOf FaceId' s
i PlanarSubdivision s v e f r
ps of
                        [] -> SimplePolygon v r -> SomePolygon v r
forall a b. a -> Either a b
Left  SimplePolygon v r
res                               SomePolygon v r -> f -> SomePolygon v r :+ f
forall core extra. core -> extra -> core :+ extra
:+ f
x
                        [Dart s]
hs -> MultiPolygon v r -> SomePolygon v r
forall a b. b -> Either a b
Right (SimplePolygon v r -> [SimplePolygon v r] -> MultiPolygon v r
forall p r.
SimplePolygon p r -> [SimplePolygon p r] -> MultiPolygon p r
MultiPolygon SimplePolygon v r
res ([SimplePolygon v r] -> MultiPolygon v r)
-> [SimplePolygon v r] -> MultiPolygon v r
forall a b. (a -> b) -> a -> b
$ (Dart s -> SimplePolygon v r) -> [Dart s] -> [SimplePolygon v r]
forall a b. (a -> b) -> [a] -> [b]
map Dart s -> SimplePolygon v r
toHole [Dart s]
hs) SomePolygon v r -> f -> SomePolygon v r :+ f
forall core extra. core -> extra -> core :+ extra
:+ f
x
  where
    SimplePolygon v r
res :+ f
x = FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
forall k (s :: k) v e f r.
FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
rawFaceBoundary FaceId' s
i PlanarSubdivision s v e f r
ps
    toHole :: Dart s -> SimplePolygon v r
toHole Dart s
d = FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
forall k (s :: k) v e f r.
FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
rawFaceBoundary (Dart s -> PlanarSubdivision s v e f r -> FaceId' s
forall k (s :: k) v e f r.
Dart s -> PlanarSubdivision s v e f r -> FaceId' s
leftFace Dart s
d PlanarSubdivision s v e f r
ps) PlanarSubdivision s v e f r
ps (SimplePolygon v r :+ f)
-> Getting
     (SimplePolygon v r) (SimplePolygon v r :+ f) (SimplePolygon v r)
-> SimplePolygon v r
forall s a. s -> Getting a s a -> a
^. Getting
  (SimplePolygon v r) (SimplePolygon v r :+ f) (SimplePolygon v r)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core

-- | Lists all *internal* faces of the planar subdivision.
rawFacePolygons    :: PlanarSubdivision s v e f r
                   -> V.Vector (FaceId' s, SomePolygon v r :+ f)
rawFacePolygons :: PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon v r :+ f)
rawFacePolygons PlanarSubdivision s v e f r
ps = ((FaceId' s, FaceData (Dart s) f)
 -> (FaceId' s, SomePolygon v r :+ f))
-> Vector (FaceId' s, FaceData (Dart s) f)
-> Vector (FaceId' s, SomePolygon v r :+ f)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(FaceId' s
i,FaceData (Dart s) f
_) -> (FaceId' s
i,FaceId' s -> PlanarSubdivision s v e f r -> SomePolygon v r :+ f
forall k (s :: k) v e f r.
FaceId' s -> PlanarSubdivision s v e f r -> SomePolygon v r :+ f
rawFacePolygon FaceId' s
i PlanarSubdivision s v e f r
ps)) (Vector (FaceId' s, FaceData (Dart s) f)
 -> Vector (FaceId' s, SomePolygon v r :+ f))
-> (PlanarSubdivision s v e f r
    -> Vector (FaceId' s, FaceData (Dart s) f))
-> PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon v r :+ f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r
-> Vector (FaceId' s, FaceData (Dart s) f)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r
-> Vector (FaceId' s, FaceData (Dart s) f)
internalFaces (PlanarSubdivision s v e f r
 -> Vector (FaceId' s, SomePolygon v r :+ f))
-> PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon v r :+ f)
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r
ps



dartMapping    :: PlanarSubdivision s v e f r -> V.Vector (Dart (Wrap s), Dart s)
dartMapping :: PlanarSubdivision s v e f r -> Vector (Dart (Wrap s), Dart s)
dartMapping PlanarSubdivision s v e f r
ps = PlanarSubdivision s v e f r
psPlanarSubdivision s v e f r
-> Getting
     (Vector (Dart (Wrap s), Dart s))
     (PlanarSubdivision s v e f r)
     (Vector (Dart (Wrap s), Dart s))
-> Vector (Dart (Wrap s), Dart s)
forall s a. s -> Getting a s a -> a
^.ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
forall k (s :: k) v e f r.
ComponentId s
-> Lens' (PlanarSubdivision s v e f r) (Component s r)
component (Int -> ComponentId s
forall k (s :: k). Int -> ComponentId s
ComponentId Int
0)((Component s r
  -> Const (Vector (Dart (Wrap s), Dart s)) (Component s r))
 -> PlanarSubdivision s v e f r
 -> Const
      (Vector (Dart (Wrap s), Dart s)) (PlanarSubdivision s v e f r))
-> ((Vector (Dart (Wrap s), Dart s)
     -> Const
          (Vector (Dart (Wrap s), Dart s)) (Vector (Dart (Wrap s), Dart s)))
    -> Component s r
    -> Const (Vector (Dart (Wrap s), Dart s)) (Component s r))
-> Getting
     (Vector (Dart (Wrap s), Dart s))
     (PlanarSubdivision s v e f r)
     (Vector (Dart (Wrap s), Dart s))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (Dart (Wrap s), Dart s)
 -> Const
      (Vector (Dart (Wrap s), Dart s)) (Vector (Dart (Wrap s), Dart s)))
-> Component s r
-> Const (Vector (Dart (Wrap s), Dart s)) (Component s r)
forall k (s :: k) v e f r e'.
Lens
  (PlaneGraph s v e f r)
  (PlaneGraph s v e' f r)
  (Vector (Dart s, e))
  (Vector (Dart s, e'))
PG.dartData



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

-- data Id a = Id a
-- data Test = Test

-- triangle :: PlanarSubdivision Test () () PolygonFaceData Rational
-- triangle = (\pg -> fromSimplePolygon (Id Test) pg Inside Outside)
--          $ trianglePG

-- trianglePG = fromPoints . map ext $ [origin, Point2 10 0, Point2 10 10]