{-# LANGUAGE TemplateHaskell #-}
{-# 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', internalFaces', faces, internalFaces
                                            , darts'
                                            , traverseVertices, traverseDarts, traverseFaces
                                            , mapVertices, mapDarts, mapFaces

                                            , headOf, tailOf, twin, endPoints

                                            , incidentEdges, incomingEdges, outgoingEdges
                                            , nextIncidentEdge, prevIncidentEdge
                                            , nextIncidentEdgeFrom, prevIncidentEdgeFrom
                                            , neighboursOf

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

                                            , locationOf
                                            , HasDataOf(..)

                                            , endPointsOf, endPointData

                                            , faceDataOf

                                            , edgeSegment, edgeSegments
                                            , faceBoundary
                                            , internalFacePolygon, internalFacePolygons
                                            , outerFacePolygon, outerFacePolygon'
                                            , facePolygons

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

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

                                            , dartMapping, Raw(..)

                                            , asLocalD, asLocalV, asLocalF
                                            , Incident (incidences)
                                            , common, commonVertices, commonDarts, commonFaces
                                            ) where

import           Control.Lens hiding (holes, holesOf, (.=))
import           Data.Bifunctor (first, second)
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.Set as Set
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


-- | Lens to access a particular component of the planar subdivision.
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.
internalFaces'    :: PlanarSubdivision s v e f r -> V.Vector (FaceId' s)
internalFaces' :: PlanarSubdivision s v e f r -> Vector (FaceId' s)
internalFaces' = Vector (FaceId' s) -> Vector (FaceId' s)
forall a. Vector a -> Vector a
V.tail (Vector (FaceId' s) -> Vector (FaceId' s))
-> (PlanarSubdivision s v e f r -> Vector (FaceId' s))
-> PlanarSubdivision s v e f r
-> Vector (FaceId' s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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'

-- | \( 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 in the
-- cyclic (counterclockwise) 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''

-- | Given a dart d that points into some vertex v, report the
-- previous dart in the cyclic (counterclockwise) order around v.
--
-- running time: \(O(1)\)
--
-- >>> prevIncidentEdge (dart 1 "+1") smallG
-- Dart (Arc 3) +1
prevIncidentEdge      :: Dart s -> PlanarSubdivision s v e f r -> Dart s
prevIncidentEdge :: Dart s -> PlanarSubdivision s v e f r -> Dart s
prevIncidentEdge 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.prevIncidentEdge 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''

-- | Given a dart d that points away from some vertex v, report the
-- next dart in the cyclic (counterclockwise) order around v.
--
--
-- running time: \(O(1)\)
--
nextIncidentEdgeFrom      :: Dart s -> PlanarSubdivision s v e f r -> Dart s
nextIncidentEdgeFrom :: Dart s -> PlanarSubdivision s v e f r -> Dart s
nextIncidentEdgeFrom 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.nextIncidentEdgeFrom 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''

-- | Given a dart d that points into away from vertex v, report the previous dart in the
-- cyclic (counterclockwise) order around v.
--
-- running time: \(O(1)\)
--
prevIncidentEdgeFrom      :: Dart s -> PlanarSubdivision s v e f r -> Dart s
prevIncidentEdgeFrom :: Dart s -> PlanarSubdivision s v e f r -> Dart s
prevIncidentEdgeFrom 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.prevIncidentEdgeFrom 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 this face. The darts are
-- reported in order along the face. This means that for internal
-- faces the darts are reported in *clockwise* order along the
-- boundary, whereas for the outer face the darts are reported in
-- counter clockwise 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)

-- | Lens to access the vertex data
--
-- Note that using the setting part of this lens may be very
-- expensive!!  (O(n))
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)


-- | Get the location of a vertex in the planar subdivision.
--
-- Note that the setting part of this lens may be very expensive!
-- Moreover, use with care (as this may destroy planarity etc.)
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


-- | Lens to get the face data of a particular face. Note that the
-- setting part of this lens may be very expensive! (O(n))
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 of the planar subdivision
traverseVertices :: Applicative g
                 => (VertexId' s -> v -> g v')
                 -> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v' e f r)
traverseVertices :: (VertexId' s -> v -> g v')
-> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v' e f r)
traverseVertices VertexId' s -> v -> g v'
h = LensLike
  g
  (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'))
-> LensLike
     g
     (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'))
forall (f :: * -> *) s t a b.
LensLike f s t a b -> LensLike f s t a b
traverseOf LensLike
  g
  (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'))
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 ((Int -> VertexId' s)
-> (VertexId' s -> v -> g v')
-> Vector (Raw s (VertexId' (Wrap s)) v)
-> g (Vector (Raw s (VertexId' (Wrap s)) v'))
forall k k (g :: * -> *) (w :: k -> *) (s :: k) v v' (ci :: k) i.
Applicative g =>
(Int -> w s)
-> (w s -> v -> g v')
-> Vector (Raw ci i v)
-> g (Vector (Raw ci i v'))
traverseWith Int -> VertexId' s
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId VertexId' s -> v -> g v'
h)

-- | Traverse the darts of the Planar subdivision
traverseDarts   :: Applicative g
                => (Dart s -> e -> g e')
                -> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v e' f r)
traverseDarts :: (Dart s -> e -> g e')
-> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v e' f r)
traverseDarts Dart s -> e -> g e'
h = LensLike
  g
  (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'))
-> LensLike
     g
     (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'))
forall (f :: * -> *) s t a b.
LensLike f s t a b -> LensLike f s t a b
traverseOf LensLike
  g
  (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'))
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 ((Int -> Dart s)
-> (Dart s -> e -> g e')
-> Vector (Raw s (Dart (Wrap s)) e)
-> g (Vector (Raw s (Dart (Wrap s)) e'))
forall k k (g :: * -> *) (w :: k -> *) (s :: k) v v' (ci :: k) i.
Applicative g =>
(Int -> w s)
-> (w s -> v -> g v')
-> Vector (Raw ci i v)
-> g (Vector (Raw ci i v'))
traverseWith Int -> Dart s
forall a. Enum a => Int -> a
toEnum Dart s -> e -> g e'
h)


-- | Traverse the faces of the planar subdivision.
traverseFaces   :: Applicative g
                => (FaceId' s -> f -> g f')
                -> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v e f' r)
traverseFaces :: (FaceId' s -> f -> g f')
-> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v e f' r)
traverseFaces FaceId' s -> f -> g f'
h = LensLike
  g
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f' r)
  (Vector (RawFace s f))
  (Vector (RawFace s f'))
-> LensLike
     g
     (PlanarSubdivision s v e f r)
     (PlanarSubdivision s v e f' r)
     (Vector (RawFace s f))
     (Vector (RawFace s f'))
forall (f :: * -> *) s t a b.
LensLike f s t a b -> LensLike f s t a b
traverseOf LensLike
  g
  (PlanarSubdivision s v e f r)
  (PlanarSubdivision s v e f' r)
  (Vector (RawFace s f))
  (Vector (RawFace s f'))
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 ((FaceId' s -> f -> g f')
-> Vector (RawFace s f) -> g (Vector (RawFace s f'))
forall k (t :: * -> *) (f :: * -> *) (t :: * -> *) (s :: k)
       (w :: World) a b.
(TraversableWithIndex Int t, Applicative f, Traversable t) =>
(FaceId s w -> a -> f b) -> t (t a) -> f (t (t b))
traverseFaces' FaceId' s -> f -> g f'
h)
  where
    traverseFaces' :: (FaceId s w -> a -> f b) -> t (t a) -> f (t (t b))
traverseFaces' FaceId s w -> a -> f b
h' = (Int -> t a -> f (t b)) -> t (t a) -> f (t (t b))
forall i (t :: * -> *) (f :: * -> *) a b.
(TraversableWithIndex i t, Applicative f) =>
(i -> a -> f b) -> t a -> f (t b)
itraverse (\Int
i -> (a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (FaceId s w -> a -> f b
h' (VertexId s (DualOf w) -> FaceId s w
forall k (s :: k) (w :: World). VertexId s (DualOf w) -> FaceId s w
FaceId (VertexId s (DualOf w) -> FaceId s w)
-> (Int -> VertexId s (DualOf w)) -> Int -> FaceId s w
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> VertexId s (DualOf w)
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId (Int -> FaceId s w) -> Int -> FaceId s w
forall a b. (a -> b) -> a -> b
$ Int
i)))

-- | Helper function to implement traver(vertertices|darts|faces)
traverseWith         :: Applicative g
                     => (Int -> w s)
                     -> (w s -> v -> g v')
                     -> V.Vector (Raw ci i v)
                     -> g (V.Vector (Raw ci i v'))
traverseWith :: (Int -> w s)
-> (w s -> v -> g v')
-> Vector (Raw ci i v)
-> g (Vector (Raw ci i v'))
traverseWith Int -> w s
mkIdx w s -> v -> g v'
h = (Int -> Raw ci i v -> g (Raw ci i v'))
-> Vector (Raw ci i v) -> g (Vector (Raw ci i v'))
forall i (t :: * -> *) (f :: * -> *) a b.
(TraversableWithIndex i t, Applicative f) =>
(i -> a -> f b) -> t a -> f (t b)
itraverse (\Int
i -> (v -> g v') -> Raw ci i v -> g (Raw ci i v')
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (w s -> v -> g v'
h (w s -> v -> g v') -> w s -> v -> g v'
forall a b. (a -> b) -> a -> b
$ Int -> w s
mkIdx Int
i))

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

-- | Map with index over all faces
mapFaces   :: (FaceId' s -> t -> f')
           -> PlanarSubdivision s v e t r -> PlanarSubdivision s v e f' r
mapFaces :: (FaceId' s -> t -> f')
-> PlanarSubdivision s v e t r -> PlanarSubdivision s v e f' r
mapFaces FaceId' s -> t -> f'
h = Identity (PlanarSubdivision s v e f' r)
-> PlanarSubdivision s v e f' r
forall a. Identity a -> a
runIdentity (Identity (PlanarSubdivision s v e f' r)
 -> PlanarSubdivision s v e f' r)
-> (PlanarSubdivision s v e t r
    -> Identity (PlanarSubdivision s v e f' r))
-> PlanarSubdivision s v e t r
-> PlanarSubdivision s v e f' r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (FaceId' s -> t -> Identity f')
-> PlanarSubdivision s v e t r
-> Identity (PlanarSubdivision s v e f' r)
forall k (g :: * -> *) (s :: k) f f' v e r.
Applicative g =>
(FaceId' s -> f -> g f')
-> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v e f' r)
traverseFaces (\FaceId' s
i t
x -> f' -> Identity f'
forall a. a -> Identity a
Identity (f' -> Identity f') -> f' -> Identity f'
forall a b. (a -> b) -> a -> b
$ FaceId' s -> t -> f'
h FaceId' s
i t
x)

-- | Map with index over all vertices
mapVertices   :: (VertexId' s -> t -> v')
              -> PlanarSubdivision s t e f r -> PlanarSubdivision s v' e f r
mapVertices :: (VertexId' s -> t -> v')
-> PlanarSubdivision s t e f r -> PlanarSubdivision s v' e f r
mapVertices VertexId' s -> t -> v'
h = Identity (PlanarSubdivision s v' e f r)
-> PlanarSubdivision s v' e f r
forall a. Identity a -> a
runIdentity (Identity (PlanarSubdivision s v' e f r)
 -> PlanarSubdivision s v' e f r)
-> (PlanarSubdivision s t e f r
    -> Identity (PlanarSubdivision s v' e f r))
-> PlanarSubdivision s t e f r
-> PlanarSubdivision s v' e f r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (VertexId' s -> t -> Identity v')
-> PlanarSubdivision s t e f r
-> Identity (PlanarSubdivision s v' e f r)
forall k (g :: * -> *) (s :: k) v v' e f r.
Applicative g =>
(VertexId' s -> v -> g v')
-> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v' e f r)
traverseVertices (\VertexId' s
i t
x -> v' -> Identity v'
forall a. a -> Identity a
Identity (v' -> Identity v') -> v' -> Identity v'
forall a b. (a -> b) -> a -> b
$ VertexId' s -> t -> v'
h VertexId' s
i t
x)

-- | Map with index over all darts
mapDarts   :: (Dart s -> t -> e')
           -> PlanarSubdivision s v t f r -> PlanarSubdivision s v e' f r
mapDarts :: (Dart s -> t -> e')
-> PlanarSubdivision s v t f r -> PlanarSubdivision s v e' f r
mapDarts Dart s -> t -> e'
h = Identity (PlanarSubdivision s v e' f r)
-> PlanarSubdivision s v e' f r
forall a. Identity a -> a
runIdentity (Identity (PlanarSubdivision s v e' f r)
 -> PlanarSubdivision s v e' f r)
-> (PlanarSubdivision s v t f r
    -> Identity (PlanarSubdivision s v e' f r))
-> PlanarSubdivision s v t f r
-> PlanarSubdivision s v e' f r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Dart s -> t -> Identity e')
-> PlanarSubdivision s v t f r
-> Identity (PlanarSubdivision s v e' f r)
forall k (g :: * -> *) (s :: k) e e' v f r.
Applicative g =>
(Dart s -> e -> g e')
-> PlanarSubdivision s v e f r -> g (PlanarSubdivision s v e' f r)
traverseDarts (\Dart s
i t
x -> e' -> Identity e'
forall a. a -> Identity a
Identity (e' -> Identity e') -> e' -> Identity e'
forall a b. (a -> b) -> a -> b
$ Dart s -> t -> e'
h Dart s
i t
x)

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

-- | 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. The segment \(\overline{uv})\) is has \(u\) as its
-- tail and \(v\) as its head.
--
-- \(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


-- | Given a dart d, generates the darts on (the current component of)
-- the boundary of the the face that is to the right of the given
-- dart. The darts are reported in order along the face. This means
-- that for
--
-- - (the outer boundary of an) internal faces the darts are reported
--   in *clockwise* order along the boundary,
-- - the "inner" boundary of a face, i.e. the boundary of ahole, the
--   darts are reported in *counter clockwise* order.
--
-- Note that this latter case means that in the darts of a a component
-- of the outer face are reported in counter clockwise order.
--
-- \(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

-- | The outerboundary of the face as a simple polygon. For internal
-- faces the polygon that is reported has its vertices stored in CCW
-- order (as expected).
--
-- pre: FaceId refers to an internal face.
--
-- \(O(k)\), where \(k\) is the complexity of the outer boundary of
-- the face
faceBoundary      :: FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
faceBoundary :: FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f
faceBoundary 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] -> [Point 2 r :+ v]
forall a. [a] -> [a]
reverse [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)
    -- for internal faces boundary' produces the boundary darts in
    -- clockwise order. Hence, we reverse the sequence of points we
    -- obtain to get the points/vertices in CCW order, so that we can
    -- construct a simplepolygon out of them.

-- | Constructs the boundary of the given face.
--
-- \(O(k)\), where \(k\) is the complexity of the face
internalFacePolygon      :: FaceId' s -> PlanarSubdivision s v e f r
                         -> SomePolygon v r :+ f
internalFacePolygon :: FaceId' s -> PlanarSubdivision s v e f r -> SomePolygon v r :+ f
internalFacePolygon 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
faceBoundary 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
faceBoundary (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
-- TODO: Verify that holes are in the right orientation.


-- | Returns a sufficiently large, rectangular, polygon that contains
-- the entire planar subdivision. Each component corresponds to a hole
-- in this polygon.
outerFacePolygon    :: (Num r, Ord r)
                    => PlanarSubdivision s v e f r -> MultiPolygon (Maybe v) r :+ f
outerFacePolygon :: PlanarSubdivision s v e f r -> MultiPolygon (Maybe v) r :+ f
outerFacePolygon PlanarSubdivision s v e f r
ps = SimplePolygon () r
-> PlanarSubdivision s v e f r -> MultiPolygon (Either () v) r :+ f
forall k v' r (s :: k) v e f.
SimplePolygon v' r
-> PlanarSubdivision s v e f r -> MultiPolygon (Either v' v) r :+ f
outerFacePolygon' SimplePolygon () r
outer PlanarSubdivision s v e f r
ps (MultiPolygon (Either () v) r :+ f)
-> ((MultiPolygon (Either () v) r :+ f)
    -> MultiPolygon (Maybe v) r :+ f)
-> MultiPolygon (Maybe v) r :+ f
forall a b. a -> (a -> b) -> b
& (MultiPolygon (Either () v) r
 -> Identity (MultiPolygon (Maybe v) r))
-> (MultiPolygon (Either () v) r :+ f)
-> Identity (MultiPolygon (Maybe v) r :+ f)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core ((MultiPolygon (Either () v) r
  -> Identity (MultiPolygon (Maybe v) r))
 -> (MultiPolygon (Either () v) r :+ f)
 -> Identity (MultiPolygon (Maybe v) r :+ f))
-> (MultiPolygon (Either () v) r -> MultiPolygon (Maybe v) r)
-> (MultiPolygon (Either () v) r :+ f)
-> MultiPolygon (Maybe v) r :+ f
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (Either () v -> Maybe v)
-> MultiPolygon (Either () v) r -> MultiPolygon (Maybe v) r
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first ((() -> Maybe v) -> (v -> Maybe v) -> Either () v -> Maybe v
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (Maybe v -> () -> Maybe v
forall a b. a -> b -> a
const Maybe v
forall a. Maybe a
Nothing) v -> Maybe v
forall a. a -> Maybe a
Just)
  where
    outer :: SimplePolygon () r
outer = Rectangle () r -> SimplePolygon () r
forall p. Rectangle p r -> SimplePolygon p r
rectToPolygon (Rectangle () r -> SimplePolygon () r)
-> (PlanarSubdivision s v e f r -> Rectangle () r)
-> PlanarSubdivision s v e f r
-> SimplePolygon () r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. r -> Rectangle () r -> Rectangle () r
forall r (d :: Nat) p.
(Num r, Arity d) =>
r -> Box d p r -> Box d p r
grow r
1 (Rectangle () r -> Rectangle () r)
-> (PlanarSubdivision s v e f r -> Rectangle () r)
-> PlanarSubdivision s v e f r
-> Rectangle () r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision s v e f r -> Rectangle () r
forall g.
(IsBoxable g, Ord (NumType g)) =>
g -> Box (Dimension g) () (NumType g)
boundingBox (PlanarSubdivision s v e f r -> SimplePolygon () r)
-> PlanarSubdivision s v e f r -> SimplePolygon () r
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r
ps
    rectToPolygon :: Rectangle p r -> SimplePolygon p r
rectToPolygon = [Point 2 r :+ p] -> SimplePolygon p r
forall r p. [Point 2 r :+ p] -> SimplePolygon p r
unsafeFromPoints ([Point 2 r :+ p] -> SimplePolygon p r)
-> (Rectangle p r -> [Point 2 r :+ p])
-> Rectangle p r
-> SimplePolygon p r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Point 2 r :+ p] -> [Point 2 r :+ p]
forall a. [a] -> [a]
reverse ([Point 2 r :+ p] -> [Point 2 r :+ p])
-> (Rectangle p r -> [Point 2 r :+ p])
-> Rectangle p r
-> [Point 2 r :+ p]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Corners (Point 2 r :+ p) -> [Point 2 r :+ p]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Corners (Point 2 r :+ p) -> [Point 2 r :+ p])
-> (Rectangle p r -> Corners (Point 2 r :+ p))
-> Rectangle p r
-> [Point 2 r :+ p]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rectangle p r -> Corners (Point 2 r :+ p)
forall r p. Num r => Rectangle p r -> Corners (Point 2 r :+ p)
corners

-- | Given a sufficiently large outer boundary, draw the outerface as
-- a polygon with a hole.
outerFacePolygon'          :: SimplePolygon v' r
                           -> PlanarSubdivision s v e f r -> MultiPolygon (Either v' v) r :+ f
outerFacePolygon' :: SimplePolygon v' r
-> PlanarSubdivision s v e f r -> MultiPolygon (Either v' v) r :+ f
outerFacePolygon' SimplePolygon v' r
outer PlanarSubdivision s v e f r
ps = SimplePolygon (Either v' v) r
-> [SimplePolygon (Either v' v) r] -> MultiPolygon (Either v' v) r
forall p r.
SimplePolygon p r -> [SimplePolygon p r] -> MultiPolygon p r
MultiPolygon ((v' -> Either v' v)
-> SimplePolygon v' r -> SimplePolygon (Either v' v) r
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first v' -> Either v' v
forall a b. a -> Either a b
Left SimplePolygon v' r
outer) [SimplePolygon (Either v' v) r]
holePgs MultiPolygon (Either v' v) r
-> f -> MultiPolygon (Either v' 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
    i :: FaceId' s
i       = PlanarSubdivision s v e f r -> FaceId' s
forall k (s :: k) v e f r. PlanarSubdivision s v e f r -> FaceId' s
outerFaceId PlanarSubdivision s v e f r
ps
    holePgs :: [SimplePolygon (Either v' v) r]
holePgs = (Dart s -> SimplePolygon (Either v' v) r)
-> [Dart s] -> [SimplePolygon (Either v' v) r]
forall a b. (a -> b) -> [a] -> [b]
map Dart s -> SimplePolygon (Either v' v) r
getBoundary ([Dart s] -> [SimplePolygon (Either v' v) r])
-> (Seq (Dart s) -> [Dart s])
-> Seq (Dart s)
-> [SimplePolygon (Either v' v) r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq (Dart s) -> [Dart s]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Seq (Dart s) -> [SimplePolygon (Either v' v) r])
-> Seq (Dart s) -> [SimplePolygon (Either v' v) r]
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
    -- get the bondary of a hole. Note that for holes, the function
    -- 'boundary' promisses to report the darts, and therefore the
    -- vertices in CCW order. Hence, we can directly construct a SimplePolygon out of it.
    getBoundary :: Dart s -> SimplePolygon (Either v' v) r
getBoundary Dart s
d = [Point 2 r :+ Either v' v] -> SimplePolygon (Either v' v) r
forall r p. [Point 2 r :+ p] -> SimplePolygon p r
unsafeFromPoints ([Point 2 r :+ Either v' v] -> SimplePolygon (Either v' v) r)
-> ([Point 2 r :+ v] -> [Point 2 r :+ Either v' v])
-> [Point 2 r :+ v]
-> SimplePolygon (Either v' v) r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Point 2 r :+ v) -> Point 2 r :+ Either v' v)
-> [Point 2 r :+ v] -> [Point 2 r :+ Either v' v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((v -> Either v' v) -> (Point 2 r :+ v) -> Point 2 r :+ Either v' v
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second v -> Either v' v
forall a b. b -> Either a b
Right) ([Point 2 r :+ v] -> SimplePolygon (Either v' v) r)
-> [Point 2 r :+ v] -> SimplePolygon (Either v' v) r
forall a b. (a -> b) -> a -> b
$ Dart s -> [Point 2 r :+ v]
faceBoundary' (Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin Dart s
d)
    faceBoundary' :: Dart s -> [Point 2 r :+ v]
faceBoundary' Dart s
d = (\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)

-- | Procuces a polygon for each *internal* face of the planar
-- subdivision.
internalFacePolygons    :: PlanarSubdivision s v e f r
                        -> V.Vector (FaceId' s, SomePolygon v r :+ f)
internalFacePolygons :: PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon v r :+ f)
internalFacePolygons 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
internalFacePolygon 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


-- | Procuces a polygon for each face of the planar subdivision.
facePolygons    :: (Num r, Ord r)
                => PlanarSubdivision s v e f r
                -> V.Vector (FaceId' s, SomePolygon (Maybe v) r :+ f)
facePolygons :: PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon (Maybe v) r :+ f)
facePolygons PlanarSubdivision s v e f r
ps = (FaceId' s, SomePolygon (Maybe v) r :+ f)
-> Vector (FaceId' s, SomePolygon (Maybe v) r :+ f)
-> Vector (FaceId' s, SomePolygon (Maybe v) r :+ f)
forall a. a -> Vector a -> Vector a
V.cons (PlanarSubdivision s v e f r -> FaceId' s
forall k (s :: k) v e f r. PlanarSubdivision s v e f r -> FaceId' s
outerFaceId PlanarSubdivision s v e f r
ps, (MultiPolygon (Maybe v) r -> SomePolygon (Maybe v) r)
-> (MultiPolygon (Maybe v) r :+ f) -> SomePolygon (Maybe v) r :+ f
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first MultiPolygon (Maybe v) r -> SomePolygon (Maybe v) r
forall a b. b -> Either a b
Right ((MultiPolygon (Maybe v) r :+ f) -> SomePolygon (Maybe v) r :+ f)
-> (MultiPolygon (Maybe v) r :+ f) -> SomePolygon (Maybe v) r :+ f
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r -> MultiPolygon (Maybe v) r :+ f
forall k r (s :: k) v e f.
(Num r, Ord r) =>
PlanarSubdivision s v e f r -> MultiPolygon (Maybe v) r :+ f
outerFacePolygon PlanarSubdivision s v e f r
ps) Vector (FaceId' s, SomePolygon (Maybe v) r :+ f)
ifs
  where
    ifs :: Vector (FaceId' s, SomePolygon (Maybe v) r :+ f)
ifs = (FaceId' s, SomePolygon v r :+ f)
-> (FaceId' s, SomePolygon (Maybe v) r :+ f)
forall k (s :: k) v r f.
(FaceId' s, SomePolygon v r :+ f)
-> (FaceId' s, SomePolygon (Maybe v) r :+ f)
wrapJust ((FaceId' s, SomePolygon v r :+ f)
 -> (FaceId' s, SomePolygon (Maybe v) r :+ f))
-> Vector (FaceId' s, SomePolygon v r :+ f)
-> Vector (FaceId' s, SomePolygon (Maybe v) r :+ f)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon v r :+ f)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon v r :+ f)
internalFacePolygons PlanarSubdivision s v e f r
ps
    g :: Bifunctor g => g a b -> g (Maybe a) b
    g :: g a b -> g (Maybe a) b
g = (a -> Maybe a) -> g a b -> g (Maybe a) b
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first a -> Maybe a
forall a. a -> Maybe a
Just

    wrapJust                 :: (FaceId' s, SomePolygon v r :+ f)
                             -> (FaceId' s, SomePolygon (Maybe v) r :+ f)
    wrapJust :: (FaceId' s, SomePolygon v r :+ f)
-> (FaceId' s, SomePolygon (Maybe v) r :+ f)
wrapJust (FaceId' s
i,(SomePolygon v r
spg :+ f
f)) = (FaceId' s
i,(Polygon 'Simple v r -> Polygon 'Simple (Maybe v) r)
-> (Polygon 'Multi v r -> Polygon 'Multi (Maybe v) r)
-> SomePolygon v r
-> SomePolygon (Maybe v) r
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap Polygon 'Simple v r -> Polygon 'Simple (Maybe v) r
forall (g :: * -> * -> *) a b.
Bifunctor g =>
g a b -> g (Maybe a) b
g Polygon 'Multi v r -> Polygon 'Multi (Maybe v) r
forall (g :: * -> * -> *) a b.
Bifunctor g =>
g a b -> g (Maybe a) b
g SomePolygon v r
spg SomePolygon (Maybe v) r -> f -> SomePolygon (Maybe v) r :+ f
forall core extra. core -> extra -> core :+ extra
:+ f
f)



-- | Mapping between the internal and extenral darts
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]














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


-- | A class for describing which features (vertex, edge, face) of a planar subdivision
--   can be incident to each other.
class Incident s a b where
  incidences :: PlanarSubdivision s v e f r -> a -> [b]

instance Incident s (VertexId' s) (Dart s) where
  incidences :: PlanarSubdivision s v e f r -> VertexId' s -> [Dart s]
incidences PlanarSubdivision s v e f r
psd VertexId' s
i = Vector (Dart s) -> [Dart s]
forall a. Vector a -> [a]
V.toList (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
i PlanarSubdivision s v e f r
psd) [Dart s] -> [Dart s] -> [Dart s]
forall a. [a] -> [a] -> [a]
++ (Dart s -> Dart s) -> [Dart s] -> [Dart s]
forall a b. (a -> b) -> [a] -> [b]
map Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin (Vector (Dart s) -> [Dart s]
forall a. Vector a -> [a]
V.toList (Vector (Dart s) -> [Dart s]) -> Vector (Dart s) -> [Dart s]
forall a b. (a -> b) -> a -> 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
i PlanarSubdivision s v e f r
psd)

instance Incident s (VertexId' s) (FaceId' s) where
  incidences :: PlanarSubdivision s v e f r -> VertexId' s -> [FaceId' s]
incidences PlanarSubdivision s v e f r
psd VertexId' s
i = (Dart s -> FaceId' s) -> [Dart s] -> [FaceId' s]
forall a b. (a -> b) -> [a] -> [b]
map (((Dart s -> PlanarSubdivision s v e f r -> FaceId' s)
-> PlanarSubdivision s v e f r -> Dart s -> FaceId' s
forall a b c. (a -> b -> c) -> b -> a -> c
flip 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) PlanarSubdivision s v e f r
psd) ([Dart s] -> [FaceId' s]) -> [Dart s] -> [FaceId' s]
forall a b. (a -> b) -> a -> b
$ Vector (Dart s) -> [Dart s]
forall a. Vector a -> [a]
V.toList (Vector (Dart s) -> [Dart s]) -> Vector (Dart s) -> [Dart s]
forall a b. (a -> b) -> a -> 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
i PlanarSubdivision s v e f r
psd

instance Incident s (Dart s) (VertexId' s) where
  incidences :: PlanarSubdivision s v e f r -> Dart s -> [VertexId' s]
incidences PlanarSubdivision s v e f r
psd Dart s
i = [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
i PlanarSubdivision s v e f r
psd, 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
i PlanarSubdivision s v e f r
psd]

instance Incident s (Dart s) (FaceId' s) where
  incidences :: PlanarSubdivision s v e f r -> Dart s -> [FaceId' s]
incidences PlanarSubdivision s v e f r
psd Dart s
i = [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
i PlanarSubdivision s v e f r
psd, 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
rightFace Dart s
i PlanarSubdivision s v e f r
psd]

instance Incident s (FaceId' s) (VertexId' s) where
  incidences :: PlanarSubdivision s v e f r -> FaceId' s -> [VertexId' s]
incidences PlanarSubdivision s v e f r
psd FaceId' s
i = Vector (VertexId' s) -> [VertexId' s]
forall a. Vector a -> [a]
V.toList (Vector (VertexId' s) -> [VertexId' s])
-> Vector (VertexId' s) -> [VertexId' s]
forall a b. (a -> b) -> a -> b
$ FaceId' s -> PlanarSubdivision s v e f r -> Vector (VertexId' s)
forall k (s :: k) v e f r.
FaceId' s -> PlanarSubdivision s v e f r -> Vector (VertexId' s)
boundaryVertices FaceId' s
i PlanarSubdivision s v e f r
psd

instance Incident s (FaceId' s) (Dart s) where
  incidences :: PlanarSubdivision s v e f r -> FaceId' s -> [Dart s]
incidences PlanarSubdivision s v e f r
psd FaceId' s
i = Vector (Dart s) -> [Dart s]
forall a. Vector a -> [a]
V.toList (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
psd) [Dart s] -> [Dart s] -> [Dart s]
forall a. [a] -> [a] -> [a]
++ (Dart s -> Dart s) -> [Dart s] -> [Dart s]
forall a b. (a -> b) -> [a] -> [b]
map Dart s -> Dart s
forall k (s :: k). Dart s -> Dart s
twin (Vector (Dart s) -> [Dart s]
forall a. Vector a -> [a]
V.toList (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
psd)

-- | Given two features (vertex, edge, or face) of a subdivision,
--   report all features of a given type that are incident to both.
common :: (Incident s a c, Incident s b c, Ord c) => PlanarSubdivision s v e f r -> a -> b -> [c]
common :: PlanarSubdivision s v e f r -> a -> b -> [c]
common PlanarSubdivision s v e f r
psd a
a b
b = Set c -> [c]
forall a. Set a -> [a]
Set.toList (Set c -> [c]) -> Set c -> [c]
forall a b. (a -> b) -> a -> b
$ Set c -> Set c -> Set c
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection ([c] -> Set c
forall a. Ord a => [a] -> Set a
Set.fromList ([c] -> Set c) -> [c] -> Set c
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r -> a -> [c]
forall k (s :: k) a b v e f r.
Incident s a b =>
PlanarSubdivision s v e f r -> a -> [b]
incidences PlanarSubdivision s v e f r
psd a
a) ([c] -> Set c
forall a. Ord a => [a] -> Set a
Set.fromList ([c] -> Set c) -> [c] -> Set c
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision s v e f r -> b -> [c]
forall k (s :: k) a b v e f r.
Incident s a b =>
PlanarSubdivision s v e f r -> a -> [b]
incidences PlanarSubdivision s v e f r
psd b
b)

-- | Given two features (edge or face) of a subdivision, report all
-- vertices that are incident to both.
commonVertices :: (Incident s a (VertexId' s), Incident s b (VertexId' s)) => PlanarSubdivision s v e f r -> a -> b -> [VertexId' s]
commonVertices :: PlanarSubdivision s v e f r -> a -> b -> [VertexId' s]
commonVertices = PlanarSubdivision s v e f r -> a -> b -> [VertexId' s]
forall k (s :: k) a c b v e f r.
(Incident s a c, Incident s b c, Ord c) =>
PlanarSubdivision s v e f r -> a -> b -> [c]
common

-- | Given two features (vertex or face) of a subdivision, report all
--   edges that are incident to both.  Returns both darts of each
--   qualifying edge.
commonDarts :: (Incident s a (Dart s), Incident s b (Dart s)) => PlanarSubdivision s v e f r -> a -> b -> [Dart s]
commonDarts :: PlanarSubdivision s v e f r -> a -> b -> [Dart s]
commonDarts = PlanarSubdivision s v e f r -> a -> b -> [Dart s]
forall k (s :: k) a c b v e f r.
(Incident s a c, Incident s b c, Ord c) =>
PlanarSubdivision s v e f r -> a -> b -> [c]
common

-- | Given two features (vertex or edge) of a subdivision, report all
-- faces that are incident to both.
commonFaces :: (Incident s a (FaceId' s), Incident s b (FaceId' s)) => PlanarSubdivision s v e f r -> a -> b -> [FaceId' s]
commonFaces :: PlanarSubdivision s v e f r -> a -> b -> [FaceId' s]
commonFaces = PlanarSubdivision s v e f r -> a -> b -> [FaceId' s]
forall k (s :: k) a c b v e f r.
(Incident s a c, Incident s b c, Ord c) =>
PlanarSubdivision s v e f r -> a -> b -> [c]
common