{-# LANGUAGE OverloadedStrings   #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TemplateHaskell     #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  Data.PlaneGraph.Core
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- Data type for planar graphs embedded in \(\mathbb{R}^2\). For functions that
-- export faces and edges etc, we assume the graph has a (planar) straight line
-- embedding.
--
--------------------------------------------------------------------------------
module Data.PlaneGraph.Core( -- $setup
                             PlaneGraph(PlaneGraph), graph
                           , PlanarGraph
                           , VertexData(VertexData), vData, location, vtxDataToExt
                           , fromSimplePolygon, fromConnectedSegments
                           , PG.fromAdjacencyLists

                           , numVertices, numEdges, numFaces, numDarts
                           , dual

                           , vertices', vertices
                           , edges', edges
                           , faces', faces, internalFaces, faces''
                           , darts', darts
                           , traverseVertices, traverseDarts, traverseFaces

                           , headOf, tailOf, twin, endPoints

                           , incidentEdges, incomingEdges, outgoingEdges
                           , neighboursOf
                           , nextIncidentEdge, prevIncidentEdge


                           , leftFace, rightFace
                           , nextEdge, prevEdge
                           , boundary, boundary', boundaryDart, boundaryVertices
                           , outerFaceId, outerFaceDart

                           , vertexDataOf, locationOf, HasDataOf(..)

                           , endPointsOf, endPointData
                           , vertexData, faceData, dartData, rawDartData

                           , edgeSegment, edgeSegments
                           , rawFacePolygon, rawFaceBoundary
                           , rawFacePolygons

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


                           , withEdgeDistances
                           -- , writePlaneGraph, readPlaneGraph
                           ) where


import           Control.Lens              hiding (holes, holesOf, (.=))
import           Data.Aeson
import           Data.Ext
import qualified Data.Foldable             as F
import           Data.Function             (on)
import           Data.Geometry.Box
import           Data.Geometry.Interval
import           Data.Geometry.Line        (cmpSlope, supportingLine)
import           Data.Geometry.LineSegment hiding (endPoints)
import           Data.Geometry.Point
import           Data.Geometry.Polygon
import           Data.Geometry.Properties
import qualified Data.List.NonEmpty        as NonEmpty
import qualified Data.Map                  as M
import           Data.Ord                  (comparing)
import           Data.PlanarGraph          (Arc (..), Dart (..), Direction (..), FaceId (..),
                                            FaceId', HasDataOf (..), PlanarGraph, VertexId (..),
                                            VertexId', World (..), dual, planarGraph, twin)
import qualified Data.PlanarGraph          as PG
import           Data.Util
import qualified Data.Vector               as V
import           Data.Vector.Circular      (CircularVector)
import           GHC.Generics              (Generic)

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

-- $setup
-- >>> import Data.Proxy
-- >>> import Data.PlaneGraph.AdjRep(Gr(Gr),Face(Face),Vtx(Vtx))
-- >>> import Data.PlaneGraph.IO(fromAdjRep)
-- >>> import Data.PlanarGraph.Dart(Dart(..),Arc(..))
-- >>> :{
-- let dart i s = Dart (Arc i) (read s)
--     small :: Gr (Vtx Int String Int) (Face String)
--     small = Gr [ Vtx 0 (Point2 0 0) [ (2,"0->2")
--                                     , (1,"0->1")
--                                     , (3,"0->3")
--                                     ] 0
--                , Vtx 1 (Point2 2 2) [ (0,"1->0")
--                                     , (2,"1->2")
--                                     , (3,"1->3")
--                                     ] 1
--                , Vtx 2 (Point2 2 0) [ (0,"2->0")
--                                     , (1,"2->1")
--                                     ] 2
--                , Vtx 3 (Point2 (-1) 4) [ (0,"3->0")
--                                        , (1,"3->1")
--                                        ] 3
--                ]
--                [ Face (2,1) "OuterFace"
--                , Face (0,1) "A"
--                , Face (1,0) "B"
--                ]
--     smallG = fromAdjRep (Proxy :: Proxy ()) small
-- :}
--
--
-- This represents the following graph. Note that the graph is undirected, the
-- arrows are just to indicate what the Positive direction of the darts is.
--
-- ![myGraph](docs/Data/PlaneGraph/small.png)


--------------------------------------------------------------------------------
-- * Vertex Data

-- | Note that the functor instance is in v
data VertexData r v = VertexData { VertexData r v -> Point 2 r
_location :: !(Point 2 r)
                                 , VertexData r v -> v
_vData    :: !v
                                 } deriving (Int -> VertexData r v -> ShowS
[VertexData r v] -> ShowS
VertexData r v -> String
(Int -> VertexData r v -> ShowS)
-> (VertexData r v -> String)
-> ([VertexData r v] -> ShowS)
-> Show (VertexData r v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall r v. (Show r, Show v) => Int -> VertexData r v -> ShowS
forall r v. (Show r, Show v) => [VertexData r v] -> ShowS
forall r v. (Show r, Show v) => VertexData r v -> String
showList :: [VertexData r v] -> ShowS
$cshowList :: forall r v. (Show r, Show v) => [VertexData r v] -> ShowS
show :: VertexData r v -> String
$cshow :: forall r v. (Show r, Show v) => VertexData r v -> String
showsPrec :: Int -> VertexData r v -> ShowS
$cshowsPrec :: forall r v. (Show r, Show v) => Int -> VertexData r v -> ShowS
Show,VertexData r v -> VertexData r v -> Bool
(VertexData r v -> VertexData r v -> Bool)
-> (VertexData r v -> VertexData r v -> Bool)
-> Eq (VertexData r v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall r v.
(Eq r, Eq v) =>
VertexData r v -> VertexData r v -> Bool
/= :: VertexData r v -> VertexData r v -> Bool
$c/= :: forall r v.
(Eq r, Eq v) =>
VertexData r v -> VertexData r v -> Bool
== :: VertexData r v -> VertexData r v -> Bool
$c== :: forall r v.
(Eq r, Eq v) =>
VertexData r v -> VertexData r v -> Bool
Eq,Eq (VertexData r v)
Eq (VertexData r v)
-> (VertexData r v -> VertexData r v -> Ordering)
-> (VertexData r v -> VertexData r v -> Bool)
-> (VertexData r v -> VertexData r v -> Bool)
-> (VertexData r v -> VertexData r v -> Bool)
-> (VertexData r v -> VertexData r v -> Bool)
-> (VertexData r v -> VertexData r v -> VertexData r v)
-> (VertexData r v -> VertexData r v -> VertexData r v)
-> Ord (VertexData r v)
VertexData r v -> VertexData r v -> Bool
VertexData r v -> VertexData r v -> Ordering
VertexData r v -> VertexData r v -> VertexData r v
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall r v. (Ord r, Ord v) => Eq (VertexData r v)
forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> Bool
forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> Ordering
forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> VertexData r v
min :: VertexData r v -> VertexData r v -> VertexData r v
$cmin :: forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> VertexData r v
max :: VertexData r v -> VertexData r v -> VertexData r v
$cmax :: forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> VertexData r v
>= :: VertexData r v -> VertexData r v -> Bool
$c>= :: forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> Bool
> :: VertexData r v -> VertexData r v -> Bool
$c> :: forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> Bool
<= :: VertexData r v -> VertexData r v -> Bool
$c<= :: forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> Bool
< :: VertexData r v -> VertexData r v -> Bool
$c< :: forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> Bool
compare :: VertexData r v -> VertexData r v -> Ordering
$ccompare :: forall r v.
(Ord r, Ord v) =>
VertexData r v -> VertexData r v -> Ordering
$cp1Ord :: forall r v. (Ord r, Ord v) => Eq (VertexData r v)
Ord,(forall x. VertexData r v -> Rep (VertexData r v) x)
-> (forall x. Rep (VertexData r v) x -> VertexData r v)
-> Generic (VertexData r v)
forall x. Rep (VertexData r v) x -> VertexData r v
forall x. VertexData r v -> Rep (VertexData r v) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall r v x. Rep (VertexData r v) x -> VertexData r v
forall r v x. VertexData r v -> Rep (VertexData r v) x
$cto :: forall r v x. Rep (VertexData r v) x -> VertexData r v
$cfrom :: forall r v x. VertexData r v -> Rep (VertexData r v) x
Generic
                                            ,a -> VertexData r b -> VertexData r a
(a -> b) -> VertexData r a -> VertexData r b
(forall a b. (a -> b) -> VertexData r a -> VertexData r b)
-> (forall a b. a -> VertexData r b -> VertexData r a)
-> Functor (VertexData r)
forall a b. a -> VertexData r b -> VertexData r a
forall a b. (a -> b) -> VertexData r a -> VertexData r b
forall r a b. a -> VertexData r b -> VertexData r a
forall r a b. (a -> b) -> VertexData r a -> VertexData r b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> VertexData r b -> VertexData r a
$c<$ :: forall r a b. a -> VertexData r b -> VertexData r a
fmap :: (a -> b) -> VertexData r a -> VertexData r b
$cfmap :: forall r a b. (a -> b) -> VertexData r a -> VertexData r b
Functor,VertexData r a -> Bool
(a -> m) -> VertexData r a -> m
(a -> b -> b) -> b -> VertexData r a -> b
(forall m. Monoid m => VertexData r m -> m)
-> (forall m a. Monoid m => (a -> m) -> VertexData r a -> m)
-> (forall m a. Monoid m => (a -> m) -> VertexData r a -> m)
-> (forall a b. (a -> b -> b) -> b -> VertexData r a -> b)
-> (forall a b. (a -> b -> b) -> b -> VertexData r a -> b)
-> (forall b a. (b -> a -> b) -> b -> VertexData r a -> b)
-> (forall b a. (b -> a -> b) -> b -> VertexData r a -> b)
-> (forall a. (a -> a -> a) -> VertexData r a -> a)
-> (forall a. (a -> a -> a) -> VertexData r a -> a)
-> (forall a. VertexData r a -> [a])
-> (forall a. VertexData r a -> Bool)
-> (forall a. VertexData r a -> Int)
-> (forall a. Eq a => a -> VertexData r a -> Bool)
-> (forall a. Ord a => VertexData r a -> a)
-> (forall a. Ord a => VertexData r a -> a)
-> (forall a. Num a => VertexData r a -> a)
-> (forall a. Num a => VertexData r a -> a)
-> Foldable (VertexData r)
forall a. Eq a => a -> VertexData r a -> Bool
forall a. Num a => VertexData r a -> a
forall a. Ord a => VertexData r a -> a
forall m. Monoid m => VertexData r m -> m
forall a. VertexData r a -> Bool
forall a. VertexData r a -> Int
forall a. VertexData r a -> [a]
forall a. (a -> a -> a) -> VertexData r a -> a
forall r a. Eq a => a -> VertexData r a -> Bool
forall r a. Num a => VertexData r a -> a
forall r a. Ord a => VertexData r a -> a
forall m a. Monoid m => (a -> m) -> VertexData r a -> m
forall r m. Monoid m => VertexData r m -> m
forall r a. VertexData r a -> Bool
forall r a. VertexData r a -> Int
forall r a. VertexData r a -> [a]
forall b a. (b -> a -> b) -> b -> VertexData r a -> b
forall a b. (a -> b -> b) -> b -> VertexData r a -> b
forall r a. (a -> a -> a) -> VertexData r a -> a
forall r m a. Monoid m => (a -> m) -> VertexData r a -> m
forall r b a. (b -> a -> b) -> b -> VertexData r a -> b
forall r a b. (a -> b -> b) -> b -> VertexData r a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: VertexData r a -> a
$cproduct :: forall r a. Num a => VertexData r a -> a
sum :: VertexData r a -> a
$csum :: forall r a. Num a => VertexData r a -> a
minimum :: VertexData r a -> a
$cminimum :: forall r a. Ord a => VertexData r a -> a
maximum :: VertexData r a -> a
$cmaximum :: forall r a. Ord a => VertexData r a -> a
elem :: a -> VertexData r a -> Bool
$celem :: forall r a. Eq a => a -> VertexData r a -> Bool
length :: VertexData r a -> Int
$clength :: forall r a. VertexData r a -> Int
null :: VertexData r a -> Bool
$cnull :: forall r a. VertexData r a -> Bool
toList :: VertexData r a -> [a]
$ctoList :: forall r a. VertexData r a -> [a]
foldl1 :: (a -> a -> a) -> VertexData r a -> a
$cfoldl1 :: forall r a. (a -> a -> a) -> VertexData r a -> a
foldr1 :: (a -> a -> a) -> VertexData r a -> a
$cfoldr1 :: forall r a. (a -> a -> a) -> VertexData r a -> a
foldl' :: (b -> a -> b) -> b -> VertexData r a -> b
$cfoldl' :: forall r b a. (b -> a -> b) -> b -> VertexData r a -> b
foldl :: (b -> a -> b) -> b -> VertexData r a -> b
$cfoldl :: forall r b a. (b -> a -> b) -> b -> VertexData r a -> b
foldr' :: (a -> b -> b) -> b -> VertexData r a -> b
$cfoldr' :: forall r a b. (a -> b -> b) -> b -> VertexData r a -> b
foldr :: (a -> b -> b) -> b -> VertexData r a -> b
$cfoldr :: forall r a b. (a -> b -> b) -> b -> VertexData r a -> b
foldMap' :: (a -> m) -> VertexData r a -> m
$cfoldMap' :: forall r m a. Monoid m => (a -> m) -> VertexData r a -> m
foldMap :: (a -> m) -> VertexData r a -> m
$cfoldMap :: forall r m a. Monoid m => (a -> m) -> VertexData r a -> m
fold :: VertexData r m -> m
$cfold :: forall r m. Monoid m => VertexData r m -> m
Foldable,Functor (VertexData r)
Foldable (VertexData r)
Functor (VertexData r)
-> Foldable (VertexData r)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> VertexData r a -> f (VertexData r b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    VertexData r (f a) -> f (VertexData r a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> VertexData r a -> m (VertexData r b))
-> (forall (m :: * -> *) a.
    Monad m =>
    VertexData r (m a) -> m (VertexData r a))
-> Traversable (VertexData r)
(a -> f b) -> VertexData r a -> f (VertexData r b)
forall r. Functor (VertexData r)
forall r. Foldable (VertexData r)
forall r (m :: * -> *) a.
Monad m =>
VertexData r (m a) -> m (VertexData r a)
forall r (f :: * -> *) a.
Applicative f =>
VertexData r (f a) -> f (VertexData r a)
forall r (m :: * -> *) a b.
Monad m =>
(a -> m b) -> VertexData r a -> m (VertexData r b)
forall r (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> VertexData r a -> f (VertexData r b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
VertexData r (m a) -> m (VertexData r a)
forall (f :: * -> *) a.
Applicative f =>
VertexData r (f a) -> f (VertexData r a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> VertexData r a -> m (VertexData r b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> VertexData r a -> f (VertexData r b)
sequence :: VertexData r (m a) -> m (VertexData r a)
$csequence :: forall r (m :: * -> *) a.
Monad m =>
VertexData r (m a) -> m (VertexData r a)
mapM :: (a -> m b) -> VertexData r a -> m (VertexData r b)
$cmapM :: forall r (m :: * -> *) a b.
Monad m =>
(a -> m b) -> VertexData r a -> m (VertexData r b)
sequenceA :: VertexData r (f a) -> f (VertexData r a)
$csequenceA :: forall r (f :: * -> *) a.
Applicative f =>
VertexData r (f a) -> f (VertexData r a)
traverse :: (a -> f b) -> VertexData r a -> f (VertexData r b)
$ctraverse :: forall r (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> VertexData r a -> f (VertexData r b)
$cp2Traversable :: forall r. Foldable (VertexData r)
$cp1Traversable :: forall r. Functor (VertexData r)
Traversable)
makeLenses ''VertexData

vtxDataToExt                  :: VertexData r v -> Point 2 r :+ v
vtxDataToExt :: VertexData r v -> Point 2 r :+ v
vtxDataToExt (VertexData Point 2 r
p v
v) = Point 2 r
p Point 2 r -> v -> Point 2 r :+ v
forall core extra. core -> extra -> core :+ extra
:+ v
v

instance Bifunctor VertexData where
  bimap :: (a -> b) -> (c -> d) -> VertexData a c -> VertexData b d
bimap a -> b
f c -> d
g (VertexData Point 2 a
p c
v) = Point 2 b -> d -> VertexData b d
forall r v. Point 2 r -> v -> VertexData r v
VertexData ((a -> b) -> Point 2 a -> Point 2 b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Point 2 a
p) (c -> d
g c
v)

instance (FromJSON r, FromJSON v) => FromJSON (VertexData r v) where
  parseJSON :: Value -> Parser (VertexData r v)
parseJSON = ((Point 2 r :+ v) -> VertexData r v)
-> Parser (Point 2 r :+ v) -> Parser (VertexData r v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(Point 2 r
l :+ v
d) -> Point 2 r -> v -> VertexData r v
forall r v. Point 2 r -> v -> VertexData r v
VertexData Point 2 r
l v
d) (Parser (Point 2 r :+ v) -> Parser (VertexData r v))
-> (Value -> Parser (Point 2 r :+ v))
-> Value
-> Parser (VertexData r v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Value -> Parser (Point 2 r :+ v)
forall a. FromJSON a => Value -> Parser a
parseJSON

instance (ToJSON r, ToJSON v) => ToJSON (VertexData r v) where
  toJSON :: VertexData r v -> Value
toJSON     = (Point 2 r :+ v) -> Value
forall a. ToJSON a => a -> Value
toJSON     ((Point 2 r :+ v) -> Value)
-> (VertexData r v -> Point 2 r :+ v) -> VertexData r v -> Value
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
vtxDataToExt
  toEncoding :: VertexData r v -> Encoding
toEncoding = (Point 2 r :+ v) -> Encoding
forall a. ToJSON a => a -> Encoding
toEncoding ((Point 2 r :+ v) -> Encoding)
-> (VertexData r v -> Point 2 r :+ v) -> VertexData r v -> Encoding
forall b c a. (b -> c) -> (a -> b) -> a -> c
. VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
vtxDataToExt

--------------------------------------------------------------------------------
-- * The PlaneGraph type

-- | Embedded, *connected*, planar graph
newtype PlaneGraph s v e f r =
    PlaneGraph { PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph :: PlanarGraph s Primal (VertexData r v) e f }
      deriving (Int -> PlaneGraph s v e f r -> ShowS
[PlaneGraph s v e f r] -> ShowS
PlaneGraph s v e f r -> String
(Int -> PlaneGraph s v e f r -> ShowS)
-> (PlaneGraph s v e f r -> String)
-> ([PlaneGraph s v e f r] -> ShowS)
-> Show (PlaneGraph 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 -> PlaneGraph s v e f r -> ShowS
forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
[PlaneGraph s v e f r] -> ShowS
forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
PlaneGraph s v e f r -> String
showList :: [PlaneGraph s v e f r] -> ShowS
$cshowList :: forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
[PlaneGraph s v e f r] -> ShowS
show :: PlaneGraph s v e f r -> String
$cshow :: forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
PlaneGraph s v e f r -> String
showsPrec :: Int -> PlaneGraph s v e f r -> ShowS
$cshowsPrec :: forall k (s :: k) v e f r.
(Show r, Show v, Show e, Show f) =>
Int -> PlaneGraph s v e f r -> ShowS
Show,PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool
(PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool)
-> (PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool)
-> Eq (PlaneGraph 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) =>
PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool
/= :: PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool
$c/= :: forall k (s :: k) v e f r.
(Eq r, Eq v, Eq e, Eq f) =>
PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool
== :: PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool
$c== :: forall k (s :: k) v e f r.
(Eq r, Eq v, Eq e, Eq f) =>
PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool
Eq,(forall x. PlaneGraph s v e f r -> Rep (PlaneGraph s v e f r) x)
-> (forall x. Rep (PlaneGraph s v e f r) x -> PlaneGraph s v e f r)
-> Generic (PlaneGraph s v e f r)
forall x. Rep (PlaneGraph s v e f r) x -> PlaneGraph s v e f r
forall x. PlaneGraph s v e f r -> Rep (PlaneGraph 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 (PlaneGraph s v e f r) x -> PlaneGraph s v e f r
forall k (s :: k) v e f r x.
PlaneGraph s v e f r -> Rep (PlaneGraph s v e f r) x
$cto :: forall k (s :: k) v e f r x.
Rep (PlaneGraph s v e f r) x -> PlaneGraph s v e f r
$cfrom :: forall k (s :: k) v e f r x.
PlaneGraph s v e f r -> Rep (PlaneGraph s v e f r) x
Generic)
makeLenses ''PlaneGraph

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

instance Functor (PlaneGraph s v e f) where
  fmap :: (a -> b) -> PlaneGraph s v e f a -> PlaneGraph s v e f b
fmap a -> b
f PlaneGraph s v e f a
pg = PlaneGraph s v e f a
pgPlaneGraph s v e f a
-> (PlaneGraph s v e f a -> PlaneGraph s v e f b)
-> PlaneGraph s v e f b
forall a b. a -> (a -> b) -> b
&(PlanarGraph s 'Primal (VertexData a v) e f
 -> Identity (PlanarGraph s 'Primal (VertexData b v) e f))
-> PlaneGraph s v e f a -> Identity (PlaneGraph s v e f b)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData a v) e f
  -> Identity (PlanarGraph s 'Primal (VertexData b v) e f))
 -> PlaneGraph s v e f a -> Identity (PlaneGraph s v e f b))
-> ((Point 2 a -> Identity (Point 2 b))
    -> PlanarGraph s 'Primal (VertexData a v) e f
    -> Identity (PlanarGraph s 'Primal (VertexData b v) e f))
-> (Point 2 a -> Identity (Point 2 b))
-> PlaneGraph s v e f a
-> Identity (PlaneGraph s v e f b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (VertexData a v) -> Identity (Vector (VertexData b v)))
-> PlanarGraph s 'Primal (VertexData a v) e f
-> Identity (PlanarGraph s 'Primal (VertexData b v) e f)
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
PG.vertexData((Vector (VertexData a v) -> Identity (Vector (VertexData b v)))
 -> PlanarGraph s 'Primal (VertexData a v) e f
 -> Identity (PlanarGraph s 'Primal (VertexData b v) e f))
-> ((Point 2 a -> Identity (Point 2 b))
    -> Vector (VertexData a v) -> Identity (Vector (VertexData b v)))
-> (Point 2 a -> Identity (Point 2 b))
-> PlanarGraph s 'Primal (VertexData a v) e f
-> Identity (PlanarGraph s 'Primal (VertexData b v) e f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(VertexData a v -> Identity (VertexData b v))
-> Vector (VertexData a v) -> Identity (Vector (VertexData b v))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse((VertexData a v -> Identity (VertexData b v))
 -> Vector (VertexData a v) -> Identity (Vector (VertexData b v)))
-> ((Point 2 a -> Identity (Point 2 b))
    -> VertexData a v -> Identity (VertexData b v))
-> (Point 2 a -> Identity (Point 2 b))
-> Vector (VertexData a v)
-> Identity (Vector (VertexData b v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 a -> Identity (Point 2 b))
-> VertexData a v -> Identity (VertexData b v)
forall r v r.
Lens (VertexData r v) (VertexData r v) (Point 2 r) (Point 2 r)
location ((Point 2 a -> Identity (Point 2 b))
 -> PlaneGraph s v e f a -> Identity (PlaneGraph s v e f b))
-> (Point 2 a -> Point 2 b)
-> PlaneGraph s v e f a
-> PlaneGraph s v e f b
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (a -> b) -> Point 2 a -> Point 2 b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f

instance IsBoxable (PlaneGraph s v e f r) where
  boundingBox :: PlaneGraph s v e f r
-> Box
     (Dimension (PlaneGraph s v e f r))
     ()
     (NumType (PlaneGraph s v e f r))
boundingBox = [Point 2 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' ([Point 2 r] -> Box 2 () r)
-> (PlaneGraph s v e f r -> [Point 2 r])
-> PlaneGraph s v e f r
-> Box 2 () r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (Point 2 r) -> [Point 2 r]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Vector (Point 2 r) -> [Point 2 r])
-> (PlaneGraph s v e f r -> Vector (Point 2 r))
-> PlaneGraph s v e f r
-> [Point 2 r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((VertexId' s, VertexData r v) -> Point 2 r)
-> Vector (VertexId' s, VertexData r v) -> Vector (Point 2 r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((VertexId' s, VertexData r v)
-> Getting (Point 2 r) (VertexId' s, VertexData r v) (Point 2 r)
-> Point 2 r
forall s a. s -> Getting a s a -> a
^.(VertexData r v -> Const (Point 2 r) (VertexData r v))
-> (VertexId' s, VertexData r v)
-> Const (Point 2 r) (VertexId' s, VertexData r v)
forall s t a b. Field2 s t a b => Lens s t a b
_2((VertexData r v -> Const (Point 2 r) (VertexData r v))
 -> (VertexId' s, VertexData r v)
 -> Const (Point 2 r) (VertexId' s, VertexData r v))
-> ((Point 2 r -> Const (Point 2 r) (Point 2 r))
    -> VertexData r v -> Const (Point 2 r) (VertexData r v))
-> Getting (Point 2 r) (VertexId' s, VertexData r v) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const (Point 2 r) (Point 2 r))
-> VertexData r v -> Const (Point 2 r) (VertexData r v)
forall r v r.
Lens (VertexData r v) (VertexData r v) (Point 2 r) (Point 2 r)
location) (Vector (VertexId' s, VertexData r v) -> Vector (Point 2 r))
-> (PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v))
-> PlaneGraph s v e f r
-> Vector (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v)
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v)
vertices


--------------------------------------------------------------------------------
-- * Constructing a Plane Graph

-- | 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                            :: proxy s
                                             -> SimplePolygon p r
                                             -> f -- ^ data inside
                                             -> f -- ^ data outside the polygon
                                             -> PlaneGraph s p () f r
fromSimplePolygon :: proxy s -> SimplePolygon p r -> f -> f -> PlaneGraph s p () f r
fromSimplePolygon proxy s
p SimplePolygon p r
poly f
iD f
oD = PlanarGraph s 'Primal (VertexData r p) () f
-> PlaneGraph s p () f r
forall k (s :: k) v e f r.
PlanarGraph s 'Primal (VertexData r v) e f -> PlaneGraph s v e f r
PlaneGraph PlanarGraph s 'Primal (VertexData r p) () f
g'
  where
    vs :: CircularVector (Point 2 r :+ p)
vs     = SimplePolygon p r
poly SimplePolygon p r
-> Getting
     (CircularVector (Point 2 r :+ p))
     (SimplePolygon p r)
     (CircularVector (Point 2 r :+ p))
-> CircularVector (Point 2 r :+ p)
forall s a. s -> Getting a s a -> a
^. Getting
  (CircularVector (Point 2 r :+ p))
  (SimplePolygon p r)
  (CircularVector (Point 2 r :+ p))
forall (t :: PolygonType) p r.
Getter (Polygon t p r) (CircularVector (Point 2 r :+ p))
outerBoundaryVector
    g :: PlanarGraph s 'Primal (VertexData r p) () ()
g      = proxy s
-> CircularVector (Point 2 r :+ p)
-> PlanarGraph s 'Primal (VertexData r p) () ()
forall k (proxy :: k -> *) (s :: k) r p.
proxy s
-> CircularVector (Point 2 r :+ p)
-> PlanarGraph s 'Primal (VertexData r p) () ()
fromVertices proxy s
p CircularVector (Point 2 r :+ p)
vs
    fData' :: Vector f
fData' = [f] -> Vector f
forall a. [a] -> Vector a
V.fromList [f
iD, f
oD]
    g' :: PlanarGraph s 'Primal (VertexData r p) () f
g'     = PlanarGraph s 'Primal (VertexData r p) () ()
g PlanarGraph s 'Primal (VertexData r p) () ()
-> (PlanarGraph s 'Primal (VertexData r p) () ()
    -> PlanarGraph s 'Primal (VertexData r p) () f)
-> PlanarGraph s 'Primal (VertexData r p) () f
forall a b. a -> (a -> b) -> b
& (Vector () -> Identity (Vector f))
-> PlanarGraph s 'Primal (VertexData r p) () ()
-> Identity (PlanarGraph s 'Primal (VertexData r p) () f)
forall k (s :: k) (w :: World) v e f f'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e f')
  (Vector f)
  (Vector f')
PG.faceData ((Vector () -> Identity (Vector f))
 -> PlanarGraph s 'Primal (VertexData r p) () ()
 -> Identity (PlanarGraph s 'Primal (VertexData r p) () f))
-> Vector f
-> PlanarGraph s 'Primal (VertexData r p) () ()
-> PlanarGraph s 'Primal (VertexData r p) () f
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Vector f
fData'

-- | Constructs a planar from the given vertices
fromVertices      :: proxy s
                  -> CircularVector (Point 2 r :+ p)
                  -> PlanarGraph s Primal (VertexData r p) () ()
fromVertices :: proxy s
-> CircularVector (Point 2 r :+ p)
-> PlanarGraph s 'Primal (VertexData r p) () ()
fromVertices proxy s
_ CircularVector (Point 2 r :+ p)
vs = PlanarGraph s 'Primal () () ()
gPlanarGraph s 'Primal () () ()
-> (PlanarGraph s 'Primal () () ()
    -> PlanarGraph s 'Primal (VertexData r p) () ())
-> PlanarGraph s 'Primal (VertexData r p) () ()
forall a b. a -> (a -> b) -> b
&(Vector () -> Identity (Vector (VertexData r p)))
-> PlanarGraph s 'Primal () () ()
-> Identity (PlanarGraph s 'Primal (VertexData r p) () ())
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
PG.vertexData ((Vector () -> Identity (Vector (VertexData r p)))
 -> PlanarGraph s 'Primal () () ()
 -> Identity (PlanarGraph s 'Primal (VertexData r p) () ()))
-> Vector (VertexData r p)
-> PlanarGraph s 'Primal () () ()
-> PlanarGraph s 'Primal (VertexData r p) () ()
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Vector (VertexData r p)
vData'
  where
    n :: Int
n = CircularVector (Point 2 r :+ p) -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length CircularVector (Point 2 r :+ p)
vs
    g :: PlanarGraph s 'Primal () () ()
g = [[(Dart s, ())]] -> PlanarGraph s 'Primal () () ()
forall k (s :: k) e.
[[(Dart s, e)]] -> PlanarGraph s 'Primal () e ()
planarGraph [ [ (Arc s -> Direction -> Dart s
forall k (s :: k). Arc s -> Direction -> Dart s
Dart (Int -> Arc s
forall k (s :: k). Int -> Arc s
Arc Int
i)               Direction
Positive, ())
                      , (Arc s -> Direction -> Dart s
forall k (s :: k). Arc s -> Direction -> Dart s
Dart (Int -> Arc s
forall k (s :: k). Int -> Arc s
Arc (Int -> Arc s) -> Int -> Arc s
forall a b. (a -> b) -> a -> b
$ (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
n) Direction
Negative, ())
                      ]
                    | Int
i <- [Int
0..(Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)]]
    vData' :: Vector (VertexData r p)
vData' = [VertexData r p] -> Vector (VertexData r p)
forall a. [a] -> Vector a
V.fromList ([VertexData r p] -> Vector (VertexData r p))
-> (CircularVector (Point 2 r :+ p) -> [VertexData r p])
-> CircularVector (Point 2 r :+ p)
-> Vector (VertexData r p)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Point 2 r :+ p) -> VertexData r p)
-> [Point 2 r :+ p] -> [VertexData r p]
forall a b. (a -> b) -> [a] -> [b]
map (\(Point 2 r
p :+ p
e) -> Point 2 r -> p -> VertexData r p
forall r v. Point 2 r -> v -> VertexData r v
VertexData Point 2 r
p p
e) ([Point 2 r :+ p] -> [VertexData r p])
-> (CircularVector (Point 2 r :+ p) -> [Point 2 r :+ p])
-> CircularVector (Point 2 r :+ p)
-> [VertexData r p]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CircularVector (Point 2 r :+ p) -> [Point 2 r :+ p]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (CircularVector (Point 2 r :+ p) -> Vector (VertexData r p))
-> CircularVector (Point 2 r :+ p) -> Vector (VertexData r p)
forall a b. (a -> b) -> a -> b
$ CircularVector (Point 2 r :+ p)
vs

-- | Constructs a connected plane graph
--
-- pre: The segments form a single connected component
--
-- running time: \(O(n\log n)\)
fromConnectedSegments      :: (Foldable f, Ord r, Num r)
                           => proxy s
                           -> f (LineSegment 2 p r :+ e)
                           -> PlaneGraph s (NonEmpty.NonEmpty p) e () r
fromConnectedSegments :: proxy s
-> f (LineSegment 2 p r :+ e) -> PlaneGraph s (NonEmpty p) e () r
fromConnectedSegments proxy s
_ f (LineSegment 2 p r :+ e)
ss = PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ()
-> PlaneGraph s (NonEmpty p) e () r
forall k (s :: k) v e f r.
PlanarGraph s 'Primal (VertexData r v) e f -> PlaneGraph s v e f r
PlaneGraph (PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ()
 -> PlaneGraph s (NonEmpty p) e () r)
-> PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ()
-> PlaneGraph s (NonEmpty p) e () r
forall a b. (a -> b) -> a -> b
$ [[(Dart s, e)]] -> PlanarGraph s 'Primal () e ()
forall k (s :: k) e.
[[(Dart s, e)]] -> PlanarGraph s 'Primal () e ()
planarGraph [[(Dart s, e)]]
dts PlanarGraph s 'Primal () e ()
-> (PlanarGraph s 'Primal () e ()
    -> PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ())
-> PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ()
forall a b. a -> (a -> b) -> b
& (Vector () -> Identity (Vector (VertexData r (NonEmpty p))))
-> PlanarGraph s 'Primal () e ()
-> Identity
     (PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ())
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
PG.vertexData ((Vector () -> Identity (Vector (VertexData r (NonEmpty p))))
 -> PlanarGraph s 'Primal () e ()
 -> Identity
      (PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ()))
-> Vector (VertexData r (NonEmpty p))
-> PlanarGraph s 'Primal () e ()
-> PlanarGraph s 'Primal (VertexData r (NonEmpty p)) e ()
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Vector (VertexData r (NonEmpty p))
vxData
  where
    pts :: Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
pts         = (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
 -> SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
 -> SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
-> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
-> Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
M.fromListWith SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
-> SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
-> SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
forall a. Semigroup a => a -> a -> a
(<>) ([(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
 -> Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]))
-> (f (LineSegment 2 p r :+ e)
    -> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])])
-> f (LineSegment 2 p r :+ e)
-> Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((LineSegment 2 p r :+ (Arc s :+ e))
 -> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])])
-> [LineSegment 2 p r :+ (Arc s :+ e)]
-> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (LineSegment 2 p r :+ (Arc s :+ e))
-> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
forall k s (s :: k) b.
(HasStart s, HasEnd s, StartExtra s ~ EndExtra s,
 EndCore s ~ StartCore s) =>
(s :+ (Arc s :+ b))
-> [(StartCore s,
     SP (NonEmpty (EndExtra s)) [StartCore s :+ (Dart s, b)])]
f ([LineSegment 2 p r :+ (Arc s :+ e)]
 -> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])])
-> (f (LineSegment 2 p r :+ e)
    -> [LineSegment 2 p r :+ (Arc s :+ e)])
-> f (LineSegment 2 p r :+ e)
-> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int
 -> (LineSegment 2 p r :+ e) -> LineSegment 2 p r :+ (Arc s :+ e))
-> [Int]
-> [LineSegment 2 p r :+ e]
-> [LineSegment 2 p r :+ (Arc s :+ e)]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int
-> (LineSegment 2 p r :+ e) -> LineSegment 2 p r :+ (Arc s :+ e)
forall k core extra (s :: k).
Int -> (core :+ extra) -> core :+ (Arc s :+ extra)
g [Int
0..] ([LineSegment 2 p r :+ e] -> [LineSegment 2 p r :+ (Arc s :+ e)])
-> (f (LineSegment 2 p r :+ e) -> [LineSegment 2 p r :+ e])
-> f (LineSegment 2 p r :+ e)
-> [LineSegment 2 p r :+ (Arc s :+ e)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f (LineSegment 2 p r :+ e) -> [LineSegment 2 p r :+ e]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (f (LineSegment 2 p r :+ e)
 -> Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]))
-> f (LineSegment 2 p r :+ e)
-> Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
forall a b. (a -> b) -> a -> b
$ f (LineSegment 2 p r :+ e)
ss
    f :: (s :+ (Arc s :+ b))
-> [(StartCore s,
     SP (NonEmpty (EndExtra s)) [StartCore s :+ (Dart s, b)])]
f (s
s :+ Arc s :+ b
e)  = [ ( s
ss -> Getting (StartCore s) s (StartCore s) -> StartCore s
forall s a. s -> Getting a s a -> a
^.((StartCore s :+ EndExtra s)
 -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> s -> Const (StartCore s) s
forall t. HasStart t => Lens' t (StartCore t :+ StartExtra t)
start(((StartCore s :+ EndExtra s)
  -> Const (StartCore s) (StartCore s :+ EndExtra s))
 -> s -> Const (StartCore s) s)
-> ((StartCore s -> Const (StartCore s) (StartCore s))
    -> (StartCore s :+ EndExtra s)
    -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> Getting (StartCore s) s (StartCore s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(StartCore s -> Const (StartCore s) (StartCore s))
-> (StartCore s :+ EndExtra s)
-> Const (StartCore s) (StartCore s :+ EndExtra s)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core
                    , NonEmpty (EndExtra s)
-> [StartCore s :+ (Dart s, b)]
-> SP (NonEmpty (EndExtra s)) [StartCore s :+ (Dart s, b)]
forall a b. a -> b -> SP a b
SP (EndExtra s -> NonEmpty (EndExtra s)
forall a. a -> NonEmpty a
sing (EndExtra s -> NonEmpty (EndExtra s))
-> EndExtra s -> NonEmpty (EndExtra s)
forall a b. (a -> b) -> a -> b
$ s
ss -> Getting (EndExtra s) s (EndExtra s) -> EndExtra s
forall s a. s -> Getting a s a -> a
^.((StartCore s :+ EndExtra s)
 -> Const (EndExtra s) (StartCore s :+ EndExtra s))
-> s -> Const (EndExtra s) s
forall t. HasStart t => Lens' t (StartCore t :+ StartExtra t)
start(((StartCore s :+ EndExtra s)
  -> Const (EndExtra s) (StartCore s :+ EndExtra s))
 -> s -> Const (EndExtra s) s)
-> ((EndExtra s -> Const (EndExtra s) (EndExtra s))
    -> (StartCore s :+ EndExtra s)
    -> Const (EndExtra s) (StartCore s :+ EndExtra s))
-> Getting (EndExtra s) s (EndExtra s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(EndExtra s -> Const (EndExtra s) (EndExtra s))
-> (StartCore s :+ EndExtra s)
-> Const (EndExtra s) (StartCore s :+ EndExtra s)
forall core extra extra'.
Lens (core :+ extra) (core :+ extra') extra extra'
extra) [(s
ss -> Getting (StartCore s) s (StartCore s) -> StartCore s
forall s a. s -> Getting a s a -> a
^.((StartCore s :+ EndExtra s)
 -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> s -> Const (StartCore s) s
forall t. HasEnd t => Lens' t (EndCore t :+ EndExtra t)
end(((StartCore s :+ EndExtra s)
  -> Const (StartCore s) (StartCore s :+ EndExtra s))
 -> s -> Const (StartCore s) s)
-> ((StartCore s -> Const (StartCore s) (StartCore s))
    -> (StartCore s :+ EndExtra s)
    -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> Getting (StartCore s) s (StartCore s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(StartCore s -> Const (StartCore s) (StartCore s))
-> (StartCore s :+ EndExtra s)
-> Const (StartCore s) (StartCore s :+ EndExtra s)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core)   StartCore s -> (Dart s, b) -> StartCore s :+ (Dart s, b)
forall core extra. core -> extra -> core :+ extra
:+ Direction -> (Arc s :+ b) -> (Dart s, b)
forall k (s :: k) b. Direction -> (Arc s :+ b) -> (Dart s, b)
h Direction
Positive Arc s :+ b
e])
                  , ( s
ss -> Getting (StartCore s) s (StartCore s) -> StartCore s
forall s a. s -> Getting a s a -> a
^.((StartCore s :+ EndExtra s)
 -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> s -> Const (StartCore s) s
forall t. HasEnd t => Lens' t (EndCore t :+ EndExtra t)
end(((StartCore s :+ EndExtra s)
  -> Const (StartCore s) (StartCore s :+ EndExtra s))
 -> s -> Const (StartCore s) s)
-> ((StartCore s -> Const (StartCore s) (StartCore s))
    -> (StartCore s :+ EndExtra s)
    -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> Getting (StartCore s) s (StartCore s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(StartCore s -> Const (StartCore s) (StartCore s))
-> (StartCore s :+ EndExtra s)
-> Const (StartCore s) (StartCore s :+ EndExtra s)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core
                    , NonEmpty (EndExtra s)
-> [StartCore s :+ (Dart s, b)]
-> SP (NonEmpty (EndExtra s)) [StartCore s :+ (Dart s, b)]
forall a b. a -> b -> SP a b
SP (EndExtra s -> NonEmpty (EndExtra s)
forall a. a -> NonEmpty a
sing (EndExtra s -> NonEmpty (EndExtra s))
-> EndExtra s -> NonEmpty (EndExtra s)
forall a b. (a -> b) -> a -> b
$ s
ss -> Getting (EndExtra s) s (EndExtra s) -> EndExtra s
forall s a. s -> Getting a s a -> a
^.((StartCore s :+ EndExtra s)
 -> Const (EndExtra s) (StartCore s :+ EndExtra s))
-> s -> Const (EndExtra s) s
forall t. HasEnd t => Lens' t (EndCore t :+ EndExtra t)
end(((StartCore s :+ EndExtra s)
  -> Const (EndExtra s) (StartCore s :+ EndExtra s))
 -> s -> Const (EndExtra s) s)
-> ((EndExtra s -> Const (EndExtra s) (EndExtra s))
    -> (StartCore s :+ EndExtra s)
    -> Const (EndExtra s) (StartCore s :+ EndExtra s))
-> Getting (EndExtra s) s (EndExtra s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(EndExtra s -> Const (EndExtra s) (EndExtra s))
-> (StartCore s :+ EndExtra s)
-> Const (EndExtra s) (StartCore s :+ EndExtra s)
forall core extra extra'.
Lens (core :+ extra) (core :+ extra') extra extra'
extra)   [(s
ss -> Getting (StartCore s) s (StartCore s) -> StartCore s
forall s a. s -> Getting a s a -> a
^.((StartCore s :+ EndExtra s)
 -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> s -> Const (StartCore s) s
forall t. HasStart t => Lens' t (StartCore t :+ StartExtra t)
start(((StartCore s :+ EndExtra s)
  -> Const (StartCore s) (StartCore s :+ EndExtra s))
 -> s -> Const (StartCore s) s)
-> ((StartCore s -> Const (StartCore s) (StartCore s))
    -> (StartCore s :+ EndExtra s)
    -> Const (StartCore s) (StartCore s :+ EndExtra s))
-> Getting (StartCore s) s (StartCore s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(StartCore s -> Const (StartCore s) (StartCore s))
-> (StartCore s :+ EndExtra s)
-> Const (StartCore s) (StartCore s :+ EndExtra s)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core) StartCore s -> (Dart s, b) -> StartCore s :+ (Dart s, b)
forall core extra. core -> extra -> core :+ extra
:+ Direction -> (Arc s :+ b) -> (Dart s, b)
forall k (s :: k) b. Direction -> (Arc s :+ b) -> (Dart s, b)
h Direction
Negative Arc s :+ b
e])
                  ]
    g :: Int -> (core :+ extra) -> core :+ (Arc s :+ extra)
g Int
i (core
s :+ extra
e) = core
s core -> (Arc s :+ extra) -> core :+ (Arc s :+ extra)
forall core extra. core -> extra -> core :+ extra
:+ (Int -> Arc s
forall k (s :: k). Int -> Arc s
Arc Int
i Arc s -> extra -> Arc s :+ extra
forall core extra. core -> extra -> core :+ extra
:+ extra
e)
    h :: Direction -> (Arc s :+ b) -> (Dart s, b)
h Direction
d (Arc s
a :+ b
e) = (Arc s -> Direction -> Dart s
forall k (s :: k). Arc s -> Direction -> Dart s
Dart Arc s
a Direction
d, b
e)

    sing :: a -> NonEmpty a
sing a
x = a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
NonEmpty.:| []

    vts :: [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
vts    = ((Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
 -> (Point 2 r, SP (NonEmpty p) [(Dart s, e)]))
-> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
-> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
forall a b. (a -> b) -> [a] -> [b]
map (\(Point 2 r
p,SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
sp) -> (Point 2 r
p,((Point 2 r :+ (Dart s, e)) -> (Dart s, e))
-> [Point 2 r :+ (Dart s, e)] -> [(Dart s, e)]
forall a b. (a -> b) -> [a] -> [b]
map ((Point 2 r :+ (Dart s, e))
-> Getting (Dart s, e) (Point 2 r :+ (Dart s, e)) (Dart s, e)
-> (Dart s, e)
forall s a. s -> Getting a s a -> a
^.Getting (Dart s, e) (Point 2 r :+ (Dart s, e)) (Dart s, e)
forall core extra extra'.
Lens (core :+ extra) (core :+ extra') extra extra'
extra) ([Point 2 r :+ (Dart s, e)] -> [(Dart s, e)])
-> ([Point 2 r :+ (Dart s, e)] -> [Point 2 r :+ (Dart s, e)])
-> [Point 2 r :+ (Dart s, e)]
-> [(Dart s, e)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Point 2 r :+ ())
-> [Point 2 r :+ (Dart s, e)] -> [Point 2 r :+ (Dart s, e)]
forall r q p.
(Ord r, Num r) =>
(Point 2 r :+ q) -> [Point 2 r :+ p] -> [Point 2 r :+ p]
sortAround' (Point 2 r -> Point 2 r :+ ()
forall a. a -> a :+ ()
ext Point 2 r
p) ([Point 2 r :+ (Dart s, e)] -> [(Dart s, e)])
-> SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
-> SP (NonEmpty p) [(Dart s, e)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> SP (NonEmpty p) [Point 2 r :+ (Dart s, e)]
sp))
           ([(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
 -> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])])
-> (Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
    -> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])])
-> Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
-> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
-> [(Point 2 r, SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])]
forall k a. Map k a -> [(k, a)]
M.assocs (Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
 -> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])])
-> Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
-> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
forall a b. (a -> b) -> a -> b
$ Map (Point 2 r) (SP (NonEmpty p) [Point 2 r :+ (Dart s, e)])
pts
    -- vertex Data
    vxData :: Vector (VertexData r (NonEmpty p))
vxData = [VertexData r (NonEmpty p)] -> Vector (VertexData r (NonEmpty p))
forall a. [a] -> Vector a
V.fromList ([VertexData r (NonEmpty p)] -> Vector (VertexData r (NonEmpty p)))
-> ([(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
    -> [VertexData r (NonEmpty p)])
-> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
-> Vector (VertexData r (NonEmpty p))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Point 2 r, SP (NonEmpty p) [(Dart s, e)])
 -> VertexData r (NonEmpty p))
-> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
-> [VertexData r (NonEmpty p)]
forall a b. (a -> b) -> [a] -> [b]
map (\(Point 2 r
p,SP (NonEmpty p) [(Dart s, e)]
sp) -> Point 2 r -> NonEmpty p -> VertexData r (NonEmpty p)
forall r v. Point 2 r -> v -> VertexData r v
VertexData Point 2 r
p (SP (NonEmpty p) [(Dart s, e)]
spSP (NonEmpty p) [(Dart s, e)]
-> Getting
     (NonEmpty p) (SP (NonEmpty p) [(Dart s, e)]) (NonEmpty p)
-> NonEmpty p
forall s a. s -> Getting a s a -> a
^.Getting (NonEmpty p) (SP (NonEmpty p) [(Dart s, e)]) (NonEmpty p)
forall s t a b. Field1 s t a b => Lens s t a b
_1)) ([(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
 -> Vector (VertexData r (NonEmpty p)))
-> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
-> Vector (VertexData r (NonEmpty p))
forall a b. (a -> b) -> a -> b
$ [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
vts
    -- The darts
    dts :: [[(Dart s, e)]]
dts    = ((Point 2 r, SP (NonEmpty p) [(Dart s, e)]) -> [(Dart s, e)])
-> [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])] -> [[(Dart s, e)]]
forall a b. (a -> b) -> [a] -> [b]
map ((Point 2 r, SP (NonEmpty p) [(Dart s, e)])
-> Getting
     [(Dart s, e)]
     (Point 2 r, SP (NonEmpty p) [(Dart s, e)])
     [(Dart s, e)]
-> [(Dart s, e)]
forall s a. s -> Getting a s a -> a
^.(SP (NonEmpty p) [(Dart s, e)]
 -> Const [(Dart s, e)] (SP (NonEmpty p) [(Dart s, e)]))
-> (Point 2 r, SP (NonEmpty p) [(Dart s, e)])
-> Const [(Dart s, e)] (Point 2 r, SP (NonEmpty p) [(Dart s, e)])
forall s t a b. Field2 s t a b => Lens s t a b
_2((SP (NonEmpty p) [(Dart s, e)]
  -> Const [(Dart s, e)] (SP (NonEmpty p) [(Dart s, e)]))
 -> (Point 2 r, SP (NonEmpty p) [(Dart s, e)])
 -> Const [(Dart s, e)] (Point 2 r, SP (NonEmpty p) [(Dart s, e)]))
-> (([(Dart s, e)] -> Const [(Dart s, e)] [(Dart s, e)])
    -> SP (NonEmpty p) [(Dart s, e)]
    -> Const [(Dart s, e)] (SP (NonEmpty p) [(Dart s, e)]))
-> Getting
     [(Dart s, e)]
     (Point 2 r, SP (NonEmpty p) [(Dart s, e)])
     [(Dart s, e)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.([(Dart s, e)] -> Const [(Dart s, e)] [(Dart s, e)])
-> SP (NonEmpty p) [(Dart s, e)]
-> Const [(Dart s, e)] (SP (NonEmpty p) [(Dart s, e)])
forall s t a b. Field2 s t a b => Lens s t a b
_2) [(Point 2 r, SP (NonEmpty p) [(Dart s, e)])]
vts


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

-- | Get the number of vertices
--
-- >>> numVertices smallG
-- 4
numVertices :: PlaneGraph s v e f r  -> Int
numVertices :: PlaneGraph s v e f r -> Int
numVertices = PlanarGraph s 'Primal (VertexData r v) e f -> Int
forall k (s :: k) (w :: World) v e f. PlanarGraph s w v e f -> Int
PG.numVertices (PlanarGraph s 'Primal (VertexData r v) e f -> Int)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Get the number of Darts
--
-- >>> numDarts smallG
-- 10
numDarts :: PlaneGraph s v e f r  -> Int
numDarts :: PlaneGraph s v e f r -> Int
numDarts = PlanarGraph s 'Primal (VertexData r v) e f -> Int
forall k (s :: k) (w :: World) v e f. PlanarGraph s w v e f -> Int
PG.numDarts (PlanarGraph s 'Primal (VertexData r v) e f -> Int)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Get the number of Edges
--
-- >>> numEdges smallG
-- 5
numEdges :: PlaneGraph s v e f r  -> Int
numEdges :: PlaneGraph s v e f r -> Int
numEdges = PlanarGraph s 'Primal (VertexData r v) e f -> Int
forall k (s :: k) (w :: World) v e f. PlanarGraph s w v e f -> Int
PG.numEdges (PlanarGraph s 'Primal (VertexData r v) e f -> Int)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Get the number of faces
--
-- >>> numFaces smallG
-- 3
numFaces :: PlaneGraph s v e f r  -> Int
numFaces :: PlaneGraph s v e f r -> Int
numFaces = PlanarGraph s 'Primal (VertexData r v) e f -> Int
forall k (s :: k) (w :: World) v e f. PlanarGraph s w v e f -> Int
PG.numFaces (PlanarGraph s 'Primal (VertexData r v) e f -> Int)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Enumerate all vertices
--
-- >>> vertices' smallG
-- [VertexId 0,VertexId 1,VertexId 2,VertexId 3]
vertices'   :: PlaneGraph s v e f r  -> V.Vector (VertexId' s)
vertices' :: PlaneGraph s v e f r -> Vector (VertexId' s)
vertices' = PlanarGraph s 'Primal (VertexData r v) e f -> Vector (VertexId' s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (VertexId s w)
PG.vertices' (PlanarGraph s 'Primal (VertexData r v) e f
 -> Vector (VertexId' s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (VertexId' s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Enumerate all vertices, together with their vertex data
--
-- >>> mapM_ print $ vertices smallG
-- (VertexId 0,VertexData {_location = Point2 0 0, _vData = 0})
-- (VertexId 1,VertexData {_location = Point2 2 2, _vData = 1})
-- (VertexId 2,VertexData {_location = Point2 2 0, _vData = 2})
-- (VertexId 3,VertexData {_location = Point2 (-1) 4, _vData = 3})
vertices   :: PlaneGraph s v e f r  -> V.Vector (VertexId' s, VertexData r v)
vertices :: PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v)
vertices = PlanarGraph s 'Primal (VertexData r v) e f
-> Vector (VertexId' s, VertexData r v)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (VertexId s w, v)
PG.vertices (PlanarGraph s 'Primal (VertexData r v) e f
 -> Vector (VertexId' s, VertexData r v))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (VertexId' s, VertexData r v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Enumerate all darts
darts' :: PlaneGraph s v e f r  -> V.Vector (Dart s)
darts' :: PlaneGraph s v e f r -> Vector (Dart s)
darts' = PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s)
PG.darts' (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Get all darts together with their data
darts :: PlaneGraph s v e f r  -> V.Vector (Dart s, e)
darts :: PlaneGraph s v e f r -> Vector (Dart s, e)
darts = PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s, e)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s, e)
PG.darts (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s, e))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s, e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Enumerate all edges. We report only the Positive darts
edges' :: PlaneGraph s v e f r  -> V.Vector (Dart s)
edges' :: PlaneGraph s v e f r -> Vector (Dart s)
edges' = PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s)
PG.edges' (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Lens to access the raw dart data, use at your own risk
rawDartData :: Lens (PlaneGraph s v e f r) (PlaneGraph s v e' f r)
                    (V.Vector e) (V.Vector e')
rawDartData :: (Vector e -> f (Vector e'))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e' f r)
rawDartData = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e' f))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e' f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e' f))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e' f r))
-> ((Vector e -> f (Vector e'))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e' f))
-> (Vector e -> f (Vector e'))
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e' f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector e -> f (Vector e'))
-> PlanarGraph s 'Primal (VertexData r v) e f
-> f (PlanarGraph s 'Primal (VertexData r v) e' f)
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector e)
  (Vector e')
PG.rawDartData

-- | lens to access the Dart Data
dartData :: Lens (PlaneGraph s v e f r) (PlaneGraph 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')))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e' f r)
dartData = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e' f))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e' f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e' f))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e' f r))
-> ((Vector (Dart s, e) -> f (Vector (Dart s, e')))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e' f))
-> (Vector (Dart s, e) -> f (Vector (Dart s, e')))
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e' f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (Dart s, e) -> f (Vector (Dart s, e')))
-> PlanarGraph s 'Primal (VertexData r v) e f
-> f (PlanarGraph s 'Primal (VertexData r v) e' f)
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector (Dart s, e))
  (Vector (Dart s, e'))
PG.dartData

-- | Lens to access face data
faceData :: Lens (PlaneGraph s v e f r) (PlaneGraph s v e f' r)
                 (V.Vector f) (V.Vector f')
faceData :: (Vector f -> f (Vector f'))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e f' r)
faceData = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e f'))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e f' r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e f'))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e f' r))
-> ((Vector f -> f (Vector f'))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e f'))
-> (Vector f -> f (Vector f'))
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e f' r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector f -> f (Vector f'))
-> PlanarGraph s 'Primal (VertexData r v) e f
-> f (PlanarGraph s 'Primal (VertexData r v) e f')
forall k (s :: k) (w :: World) v e f f'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e f')
  (Vector f)
  (Vector f')
PG.faceData

vertexData :: Lens (PlaneGraph s v e f r) (PlaneGraph s v' e f r)
                   (V.Vector v) (V.Vector v')
vertexData :: (Vector v -> f (Vector v'))
-> PlaneGraph s v e f r -> f (PlaneGraph s v' e f r)
vertexData = (PlaneGraph s v e f r -> Vector v)
-> (PlaneGraph s v e f r -> Vector v' -> PlaneGraph s v' e f r)
-> Lens
     (PlaneGraph s v e f r)
     (PlaneGraph 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 PlaneGraph s v e f r -> Vector v
forall k (s :: k) v e f r. PlaneGraph s v e f r -> Vector v
get'' PlaneGraph s v e f r -> Vector v' -> PlaneGraph s v' e f r
forall k (s :: k) v e f r v.
PlaneGraph s v e f r -> Vector v -> PlaneGraph s v e f r
set''
  where
    get'' :: PlaneGraph s v e f r -> Vector v
get'' PlaneGraph s v e f r
pg    = let v :: Vector (VertexData r v)
v = PlaneGraph s v e f r
pgPlaneGraph s v e f r
-> Getting
     (Vector (VertexData r v))
     (PlaneGraph s v e f r)
     (Vector (VertexData r v))
-> Vector (VertexData r v)
forall s a. s -> Getting a s a -> a
^.(PlanarGraph s 'Primal (VertexData r v) e f
 -> Const
      (Vector (VertexData r v))
      (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r
-> Const (Vector (VertexData r v)) (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> Const
       (Vector (VertexData r v))
       (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r
 -> Const (Vector (VertexData r v)) (PlaneGraph s v e f r))
-> ((Vector (VertexData r v)
     -> Const (Vector (VertexData r v)) (Vector (VertexData r v)))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> Const
         (Vector (VertexData r v))
         (PlanarGraph s 'Primal (VertexData r v) e f))
-> Getting
     (Vector (VertexData r v))
     (PlaneGraph s v e f r)
     (Vector (VertexData r v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (VertexData r v)
 -> Const (Vector (VertexData r v)) (Vector (VertexData r v)))
-> PlanarGraph s 'Primal (VertexData r v) e f
-> Const
     (Vector (VertexData r v))
     (PlanarGraph s 'Primal (VertexData r v) e f)
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
PG.vertexData in (VertexData 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 v v. Lens (VertexData r v) (VertexData r v) v v
vData) (VertexData r v -> v) -> Vector (VertexData r v) -> Vector v
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Vector (VertexData r v)
v
    set'' :: PlaneGraph s v e f r -> Vector v -> PlaneGraph s v e f r
set'' PlaneGraph s v e f r
pg Vector v
v' = PlaneGraph s v e f r
pgPlaneGraph s v e f r
-> (PlaneGraph s v e f r -> PlaneGraph s v e f r)
-> PlaneGraph s v e f r
forall a b. a -> (a -> b) -> b
&(PlanarGraph s 'Primal (VertexData r v) e f
 -> Identity (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r -> Identity (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> Identity (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r -> Identity (PlaneGraph s v e f r))
-> ((Vector (VertexData r v) -> Identity (Vector (VertexData r v)))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> Identity (PlanarGraph s 'Primal (VertexData r v) e f))
-> (Vector (VertexData r v) -> Identity (Vector (VertexData r v)))
-> PlaneGraph s v e f r
-> Identity (PlaneGraph s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (VertexData r v) -> Identity (Vector (VertexData r v)))
-> PlanarGraph s 'Primal (VertexData r v) e f
-> Identity (PlanarGraph s 'Primal (VertexData r v) e f)
forall k (s :: k) (w :: World) v e f v'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v' e f)
  (Vector v)
  (Vector v')
PG.vertexData ((Vector (VertexData r v) -> Identity (Vector (VertexData r v)))
 -> PlaneGraph s v e f r -> Identity (PlaneGraph s v e f r))
-> (Vector (VertexData r v) -> Vector (VertexData r v))
-> PlaneGraph s v e f r
-> PlaneGraph s v e f r
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ (v -> VertexData r v -> VertexData r v)
-> Vector v -> Vector (VertexData r v) -> Vector (VertexData r v)
forall a b c. (a -> b -> c) -> Vector a -> Vector b -> Vector c
V.zipWith v -> VertexData r v -> VertexData r v
forall v r v. v -> VertexData r v -> VertexData r v
f Vector v
v'
    f :: v -> VertexData r v -> VertexData r v
f v
x (VertexData Point 2 r
l v
_) = Point 2 r -> v -> VertexData r v
forall r v. Point 2 r -> v -> VertexData r v
VertexData Point 2 r
l v
x

-- | Enumerate all edges with their edge data. We report only the Positive
-- darts.
--
-- >>> mapM_ print $ edges smallG
-- (Dart (Arc 0) +1,"0->2")
-- (Dart (Arc 1) +1,"0->1")
-- (Dart (Arc 2) +1,"0->3")
-- (Dart (Arc 4) +1,"1->2")
-- (Dart (Arc 3) +1,"1->3")
edges :: PlaneGraph s v e f r  -> V.Vector (Dart s, e)
edges :: PlaneGraph s v e f r -> Vector (Dart s, e)
edges = PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s, e)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (Dart s, e)
PG.edges (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s, e))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s, e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Enumerate all faces in the plane graph
faces' :: PlaneGraph s v e f r  -> V.Vector (FaceId' s)
faces' :: PlaneGraph s v e f r -> Vector (FaceId' s)
faces' = PlanarGraph s 'Primal (VertexData r v) e f -> Vector (FaceId' s)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (FaceId s w)
PG.faces' (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (FaceId' s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (FaceId' s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | All faces with their face data.
--
-- >>> mapM_ print $ faces smallG
-- (FaceId 0,"OuterFace")
-- (FaceId 1,"A")
-- (FaceId 2,"B")
faces :: PlaneGraph s v e f r  -> V.Vector (FaceId' s, f)
faces :: PlaneGraph s v e f r -> Vector (FaceId' s, f)
faces = PlanarGraph s 'Primal (VertexData r v) e f -> Vector (FaceId' s, f)
forall k (s :: k) (w :: World) v e f.
PlanarGraph s w v e f -> Vector (FaceId s w, f)
PG.faces (PlanarGraph s 'Primal (VertexData r v) e f
 -> Vector (FaceId' s, f))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (FaceId' s, f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph


-- | Reports the outerface and all internal faces separately.
-- running time: \(O(n)\)
faces''   :: (Ord r, Fractional r)
          => PlaneGraph s v e f r -> ((FaceId' s, f), V.Vector (FaceId' s, f))
faces'' :: PlaneGraph s v e f r -> ((FaceId' s, f), Vector (FaceId' s, f))
faces'' PlaneGraph s v e f r
g = let i :: FaceId' s
i = PlaneGraph s v e f r -> FaceId' s
forall k r (s :: k) v e f.
(Ord r, Fractional r) =>
PlaneGraph s v e f r -> FaceId' s
outerFaceId PlaneGraph s v e f r
g
            in ((FaceId' s
i,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
i), ((FaceId' s, f) -> Bool)
-> Vector (FaceId' s, f) -> Vector (FaceId' s, f)
forall a. (a -> Bool) -> Vector a -> Vector a
V.filter (\(FaceId' s
j,f
_) -> FaceId' s
i FaceId' s -> FaceId' s -> Bool
forall a. Eq a => a -> a -> Bool
/= FaceId' s
j) (Vector (FaceId' s, f) -> Vector (FaceId' s, f))
-> Vector (FaceId' s, f) -> Vector (FaceId' s, f)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r -> Vector (FaceId' s, f)
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> Vector (FaceId' s, f)
faces PlaneGraph s v e f r
g)

-- | Reports all internal faces.
-- running time: \(O(n)\)
internalFaces :: (Ord r, Fractional r)
              => PlaneGraph s v e f r -> V.Vector (FaceId' s, f)
internalFaces :: PlaneGraph s v e f r -> Vector (FaceId' s, f)
internalFaces = ((FaceId' s, f), Vector (FaceId' s, f)) -> Vector (FaceId' s, f)
forall a b. (a, b) -> b
snd (((FaceId' s, f), Vector (FaceId' s, f)) -> Vector (FaceId' s, f))
-> (PlaneGraph s v e f r
    -> ((FaceId' s, f), Vector (FaceId' s, f)))
-> PlaneGraph s v e f r
-> Vector (FaceId' s, f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> ((FaceId' s, f), Vector (FaceId' s, f))
forall k r (s :: k) v e f.
(Ord r, Fractional r) =>
PlaneGraph s v e f r -> ((FaceId' s, f), Vector (FaceId' s, f))
faces''

-- | The tail of a dart, i.e. the vertex this dart is leaving from
--
-- running time: \(O(1)\)
--
-- >>> tailOf (dart 0 "+1") smallG
-- VertexId 0
tailOf   :: Dart s -> PlaneGraph s v e f r  -> VertexId' s
tailOf :: Dart s -> PlaneGraph s v e f r -> VertexId' s
tailOf Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> VertexId' s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
PG.tailOf Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> VertexId' s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> VertexId' s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | The vertex this dart is heading in to
--
-- running time: \(O(1)\)
--
-- >>> headOf (dart 0 "+1") smallG
-- VertexId 2
headOf   :: Dart s -> PlaneGraph s v e f r  -> VertexId' s
headOf :: Dart s -> PlaneGraph s v e f r -> VertexId' s
headOf Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> VertexId' s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> VertexId s w
PG.headOf Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> VertexId' s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> VertexId' s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | endPoints d g = (tailOf d g, headOf d g)
--
-- running time: \(O(1)\)
--
-- >>> endPoints (dart 0 "+1") smallG
-- (VertexId 0,VertexId 2)
endPoints   :: Dart s -> PlaneGraph s v e f r
            -> (VertexId' s, VertexId' s)
endPoints :: Dart s -> PlaneGraph s v e f r -> (VertexId' s, VertexId' s)
endPoints Dart s
d = Dart s
-> PlanarGraph s 'Primal (VertexData r v) e f
-> (VertexId' s, VertexId' s)
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> (VertexId s w, VertexId s w)
PG.endPoints Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f
 -> (VertexId' s, VertexId' s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> (VertexId' s, VertexId' s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | All edges incident to vertex v, in counterclockwise order around v.
--
-- running time: \(O(k)\), where \(k\) is the output size
--
-- >>> incidentEdges (VertexId 1) smallG
-- [Dart (Arc 1) -1,Dart (Arc 4) +1,Dart (Arc 3) +1]
incidentEdges   :: VertexId' s -> PlaneGraph s v e f r -> V.Vector (Dart s)
incidentEdges :: VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s)
incidentEdges VertexId' s
v = VertexId' s
-> PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
PG.incidentEdges VertexId' s
v (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph


-- | 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 1) smallG
-- [Dart (Arc 1) +1,Dart (Arc 4) -1,Dart (Arc 3) -1]
incomingEdges   :: VertexId' s -> PlaneGraph s v e f r -> V.Vector (Dart s)
incomingEdges :: VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s)
incomingEdges VertexId' s
v = VertexId' s
-> PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
PG.incomingEdges VertexId' s
v (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph



-- | 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
--
-- >>> outgoingEdges (VertexId 1) smallG
-- [Dart (Arc 1) -1,Dart (Arc 4) +1,Dart (Arc 3) +1]
outgoingEdges   :: VertexId' s -> PlaneGraph s v e f r  -> V.Vector (Dart s)
outgoingEdges :: VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s)
outgoingEdges VertexId' s
v = VertexId' s
-> PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (Dart s)
PG.outgoingEdges VertexId' s
v (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | 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 1) smallG
-- [VertexId 0,VertexId 2,VertexId 3]
neighboursOf   :: VertexId' s -> PlaneGraph s v e f r
               -> V.Vector (VertexId' s)
neighboursOf :: VertexId' s -> PlaneGraph s v e f r -> Vector (VertexId' s)
neighboursOf VertexId' s
v = VertexId' s
-> PlanarGraph s 'Primal (VertexData r v) e f
-> Vector (VertexId' s)
forall k (s :: k) (w :: World) v e f.
VertexId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)
PG.neighboursOf VertexId' s
v (PlanarGraph s 'Primal (VertexData r v) e f
 -> Vector (VertexId' s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (VertexId' s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Given a dart d that points into some vertex v, report the next dart in the
-- cyclic order around v in clockwise direction.
--
-- running time: \(O(1)\)
--
-- >>> nextIncidentEdge (dart 1 "+1") smallG
-- Dart (Arc 2) +1
nextIncidentEdge   :: Dart s -> PlaneGraph s v e f r -> Dart s
nextIncidentEdge :: Dart s -> PlaneGraph s v e f r -> Dart s
nextIncidentEdge Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> Dart s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> Dart s
PG.nextIncidentEdge Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> Dart s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Dart s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Given a dart d that points into some vertex v, report the next dart in the
-- cyclic order around v (in clockwise order)
--
-- running time: \(O(1)\)
--
-- >>> prevIncidentEdge (dart 1 "+1") smallG
-- Dart (Arc 0) +1
prevIncidentEdge   :: Dart s -> PlaneGraph s v e f r -> Dart s
prevIncidentEdge :: Dart s -> PlaneGraph s v e f r -> Dart s
prevIncidentEdge Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> Dart s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> Dart s
PG.prevIncidentEdge Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> Dart s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Dart s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph


-- | The face to the left of the dart
--
-- running time: \(O(1)\).
--
-- >>> leftFace (dart 1 "+1") smallG
-- FaceId 2
-- >>> leftFace (dart 1 "-1") smallG
-- FaceId 1
-- >>> leftFace (dart 2 "+1") smallG
-- FaceId 0
-- >>> leftFace (dart 2 "-1") smallG
-- FaceId 2
leftFace   :: Dart s -> PlaneGraph s v e f r  -> FaceId' s
leftFace :: Dart s -> PlaneGraph s v e f r -> FaceId' s
leftFace Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> FaceId' s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> FaceId s w
PG.leftFace Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> FaceId' s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> FaceId' s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | The face to the right of the dart
--
-- running time: \(O(1)\).
--
-- >>> rightFace (dart 1 "+1") smallG
-- FaceId 1
-- >>> rightFace (dart 1 "-1") smallG
-- FaceId 2
-- >>> rightFace (dart 2 "+1") smallG
-- FaceId 2
-- >>> rightFace (dart 2 "-1") smallG
-- FaceId 0
rightFace   :: Dart s -> PlaneGraph s v e f r  -> FaceId' s
rightFace :: Dart s -> PlaneGraph s v e f r -> FaceId' s
rightFace Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> FaceId' s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> FaceId s w
PG.rightFace Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> FaceId' s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> FaceId' s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph


-- | Get the next edge along the face
--
--
-- running time: \(O(1)\).
--
-- >>> nextEdge (dart 1 "+1") smallG
-- Dart (Arc 4) +1
nextEdge   :: Dart s -> PlaneGraph s v e f r -> Dart s
nextEdge :: Dart s -> PlaneGraph s v e f r -> Dart s
nextEdge Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> Dart s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> Dart s
PG.nextEdge Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> Dart s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Dart s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Get the previous edge along the face
--
--
-- running time: \(O(1)\).
--
-- >>> prevEdge (dart 1 "+1") smallG
-- Dart (Arc 0) -1
prevEdge   :: Dart s -> PlaneGraph s v e f r -> Dart s
prevEdge :: Dart s -> PlaneGraph s v e f r -> Dart s
prevEdge Dart s
d = Dart s -> PlanarGraph s 'Primal (VertexData r v) e f -> Dart s
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> Dart s
PG.prevEdge Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> Dart s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Dart s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph


-- | The darts bounding this 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.
--
--
boundary   :: FaceId' s -> PlaneGraph s v e f r  -> V.Vector (Dart s)
boundary :: FaceId' s -> PlaneGraph s v e f r -> Vector (Dart s)
boundary FaceId' s
f = FaceId' s
-> PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
FaceId s w -> PlanarGraph s w v e f -> Vector (Dart s)
PG.boundary FaceId' s
f (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Generates the darts incident to a face, starting with the given dart.
--
--
-- \(O(k)\), where \(k\) is the number of darts reported
boundary'   :: Dart s -> PlaneGraph s v e f r -> V.Vector (Dart s)
boundary' :: Dart s -> PlaneGraph s v e f r -> Vector (Dart s)
boundary' Dart s
d = Dart s
-> PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s)
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> Vector (Dart s)
PG.boundary' Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f -> Vector (Dart s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (Dart s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | Gets a dart bounding this face. I.e. a dart d such that the face lies to
-- the right of the dart.
boundaryDart   :: FaceId' s -> PlaneGraph s v e f r -> Dart s
boundaryDart :: FaceId' s -> PlaneGraph s v e f r -> Dart s
boundaryDart FaceId' s
f = FaceId' s -> PlanarGraph s 'Primal (VertexData r v) e f -> Dart s
forall k (s :: k) (w :: World) v e f.
FaceId s w -> PlanarGraph s w v e f -> Dart s
PG.boundaryDart FaceId' s
f (PlanarGraph s 'Primal (VertexData r v) e f -> Dart s)
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Dart s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

-- | The vertices bounding this 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 -> PlaneGraph s v e f r
                   -> V.Vector (VertexId' s)
boundaryVertices :: FaceId' s -> PlaneGraph s v e f r -> Vector (VertexId' s)
boundaryVertices FaceId' s
f = FaceId' s
-> PlanarGraph s 'Primal (VertexData r v) e f
-> Vector (VertexId' s)
forall k (s :: k) (w :: World) v e f.
FaceId s w -> PlanarGraph s w v e f -> Vector (VertexId s w)
PG.boundaryVertices FaceId' s
f (PlanarGraph s 'Primal (VertexData r v) e f
 -> Vector (VertexId' s))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> Vector (VertexId' s)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph


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

vertexDataOf   :: VertexId' s -> Lens' (PlaneGraph s v e f r ) (VertexData r v)
vertexDataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (VertexData r v)
vertexDataOf VertexId' s
v = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e f r))
-> ((VertexData r v -> f (VertexData r v))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> (VertexData r v -> f (VertexData r v))
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.VertexId' s
-> Lens'
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (DataOf (PlanarGraph s 'Primal (VertexData r v) e f) (VertexId' s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
PG.dataOf VertexId' s
v

locationOf   :: VertexId' s -> Lens' (PlaneGraph s v e f r ) (Point 2 r)
locationOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (Point 2 r)
locationOf VertexId' s
v = VertexId' s -> Lens' (PlaneGraph s v e f r) (VertexData r v)
forall k (s :: k) v e f r.
VertexId' s -> Lens' (PlaneGraph s v e f r) (VertexData r v)
vertexDataOf VertexId' s
v((VertexData r v -> f (VertexData r v))
 -> PlaneGraph s v e f r -> f (PlaneGraph 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))
-> PlaneGraph s v e f r
-> f (PlaneGraph 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 v r.
Lens (VertexData r v) (VertexData r v) (Point 2 r) (Point 2 r)
location


instance HasDataOf (PlaneGraph s v e f r) (VertexId' s) where
  type DataOf (PlaneGraph s v e f r) (VertexId' s) = v
  dataOf :: VertexId' s
-> Lens'
     (PlaneGraph s v e f r)
     (DataOf (PlaneGraph s v e f r) (VertexId' s))
dataOf VertexId' s
v = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e f r))
-> ((v -> f v)
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> (v -> f v)
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.VertexId' s
-> Lens'
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (DataOf (PlanarGraph s 'Primal (VertexData r v) e f) (VertexId' s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf VertexId' s
v((VertexData r v -> f (VertexData r v))
 -> PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> ((v -> f v) -> VertexData r v -> f (VertexData r v))
-> (v -> f v)
-> PlanarGraph s 'Primal (VertexData r v) e f
-> f (PlanarGraph s 'Primal (VertexData r v) e f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(v -> f v) -> VertexData r v -> f (VertexData r v)
forall r v v. Lens (VertexData r v) (VertexData r v) v v
vData

instance HasDataOf (PlaneGraph s v e f r) (Dart s) where
  type DataOf (PlaneGraph s v e f r) (Dart s) = e
  dataOf :: Dart s
-> Lens'
     (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s))
dataOf Dart s
d = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e f r))
-> ((e -> f e)
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> (e -> f e)
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Dart s
-> Lens'
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (DataOf (PlanarGraph s 'Primal (VertexData r v) e f) (Dart s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf Dart s
d

instance HasDataOf (PlaneGraph s v e f r) (FaceId' s) where
  type DataOf (PlaneGraph s v e f r) (FaceId' s) = f
  dataOf :: FaceId' s
-> Lens'
     (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s))
dataOf FaceId' s
f = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e f r))
-> ((f -> f f)
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> (f -> f f)
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.FaceId' s
-> Lens'
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (DataOf (PlanarGraph s 'Primal (VertexData r v) e f) (FaceId' s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf FaceId' s
f


-- | Traverse the vertices
--
-- (^.vertexData) <$> traverseVertices (\i x -> Just (i,x)) smallG
-- Just [(VertexId 0,0),(VertexId 1,1),(VertexId 2,2),(VertexId 3,3)]
-- >>> traverseVertices (\i x -> print (i,x)) smallG >> pure ()
-- (VertexId 0,0)
-- (VertexId 1,1)
-- (VertexId 2,2)
-- (VertexId 3,3)
traverseVertices   :: Applicative m
                   => (VertexId' s -> v -> m v')
                   -> PlaneGraph s v e f r
                   -> m (PlaneGraph s v' e f r)
traverseVertices :: (VertexId' s -> v -> m v')
-> PlaneGraph s v e f r -> m (PlaneGraph s v' e f r)
traverseVertices VertexId' s -> v -> m v'
f = (Indexed Int v (m v')
 -> PlaneGraph s v e f r -> m (PlaneGraph s v' e f r))
-> (Int -> v -> m v')
-> PlaneGraph s v e f r
-> m (PlaneGraph s v' e f r)
forall i a (f :: * -> *) b s t.
(Indexed i a (f b) -> s -> f t) -> (i -> a -> f b) -> s -> f t
itraverseOf ((Vector v -> m (Vector v'))
-> PlaneGraph s v e f r -> m (PlaneGraph s v' e f 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')
vertexData((Vector v -> m (Vector v'))
 -> PlaneGraph s v e f r -> m (PlaneGraph s v' e f r))
-> (Indexed Int v (m v') -> Vector v -> m (Vector v'))
-> Indexed Int v (m v')
-> PlaneGraph s v e f r
-> m (PlaneGraph s v' e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Indexed Int v (m v') -> Vector v -> m (Vector v')
forall i (t :: * -> *) a b.
TraversableWithIndex i t =>
IndexedTraversal i (t a) (t b) a b
itraversed) (VertexId' s -> v -> m v'
f (VertexId' s -> v -> m v')
-> (Int -> VertexId' s) -> Int -> v -> m v'
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> VertexId' s
forall k (s :: k) (w :: World). Int -> VertexId s w
VertexId)

-- | Traverses the darts
--
-- >>> traverseDarts (\d x -> print (d,x)) smallG >> pure ()
-- (Dart (Arc 0) +1,"0->2")
-- (Dart (Arc 0) -1,"2->0")
-- (Dart (Arc 1) +1,"0->1")
-- (Dart (Arc 1) -1,"1->0")
-- (Dart (Arc 2) +1,"0->3")
-- (Dart (Arc 2) -1,"3->0")
-- (Dart (Arc 3) +1,"1->3")
-- (Dart (Arc 3) -1,"3->1")
-- (Dart (Arc 4) +1,"1->2")
-- (Dart (Arc 4) -1,"2->1")
traverseDarts   :: Applicative m
                => (Dart s -> e -> m e')
                -> PlaneGraph s v e f r
                -> m (PlaneGraph s v e' f r)
traverseDarts :: (Dart s -> e -> m e')
-> PlaneGraph s v e f r -> m (PlaneGraph s v e' f r)
traverseDarts Dart s -> e -> m e'
f = LensLike
  m
  (PlaneGraph s v e f r)
  (PlaneGraph s v e' f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e' f)
-> LensLike
     m
     (PlaneGraph s v e f r)
     (PlaneGraph s v e' f r)
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (PlanarGraph s 'Primal (VertexData r v) e' f)
forall (f :: * -> *) s t a b.
LensLike f s t a b -> LensLike f s t a b
traverseOf LensLike
  m
  (PlaneGraph s v e f r)
  (PlaneGraph s v e' f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e' f)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph ((Dart s -> e -> m e')
-> PlanarGraph s 'Primal (VertexData r v) e f
-> m (PlanarGraph s 'Primal (VertexData r v) e' f)
forall k (m :: * -> *) (s :: k) e e' (w :: World) v f.
Applicative m =>
(Dart s -> e -> m e')
-> PlanarGraph s w v e f -> m (PlanarGraph s w v e' f)
PG.traverseDarts Dart s -> e -> m e'
f)


-- | Traverses the faces
--
-- >>> traverseFaces (\i x -> print (i,x)) smallG >> pure ()
-- (FaceId 0,"OuterFace")
-- (FaceId 1,"A")
-- (FaceId 2,"B")
traverseFaces   :: Applicative m
                => (FaceId' s  -> f -> m f')
                -> PlaneGraph s v e f r
                -> m (PlaneGraph s v e f' r)
traverseFaces :: (FaceId' s -> f -> m f')
-> PlaneGraph s v e f r -> m (PlaneGraph s v e f' r)
traverseFaces FaceId' s -> f -> m f'
f = LensLike
  m
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f' r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f')
-> LensLike
     m
     (PlaneGraph s v e f r)
     (PlaneGraph s v e f' r)
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (PlanarGraph s 'Primal (VertexData r v) e f')
forall (f :: * -> *) s t a b.
LensLike f s t a b -> LensLike f s t a b
traverseOf LensLike
  m
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f' r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f')
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph ((FaceId' s -> f -> m f')
-> PlanarGraph s 'Primal (VertexData r v) e f
-> m (PlanarGraph s 'Primal (VertexData r v) e f')
forall k (m :: * -> *) (s :: k) (w :: World) f f' v e.
Applicative m =>
(FaceId s w -> f -> m f')
-> PlanarGraph s w v e f -> m (PlanarGraph s w v e f')
PG.traverseFaces FaceId' s -> f -> m f'
f)


-- | Getter for the data at the endpoints of a dart
--
-- running time: \(O(1)\)
endPointsOf   :: Dart s -> Getter (PlaneGraph s v e f r )
                                  (VertexData r v, VertexData r v)
endPointsOf :: Dart s
-> Getter (PlaneGraph s v e f r) (VertexData r v, VertexData r v)
endPointsOf Dart s
d = (PlanarGraph s 'Primal (VertexData r v) e f
 -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r -> f (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> f (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r -> f (PlaneGraph s v e f r))
-> (((VertexData r v, VertexData r v)
     -> f (VertexData r v, VertexData r v))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> f (PlanarGraph s 'Primal (VertexData r v) e f))
-> ((VertexData r v, VertexData r v)
    -> f (VertexData r v, VertexData r v))
-> PlaneGraph s v e f r
-> f (PlaneGraph s v e f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Dart s
-> Getter
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (VertexData r v, VertexData r v)
forall k (s :: k) (w :: World) v e f.
Dart s -> Getter (PlanarGraph s w v e f) (v, v)
PG.endPointDataOf Dart s
d

-- | Data corresponding to the endpoints of the dart
--
-- running time: \(O(1)\)
endPointData   :: Dart s -> PlaneGraph s v e f r
               ->  (VertexData r v, VertexData r v)
endPointData :: Dart s -> PlaneGraph s v e f r -> (VertexData r v, VertexData r v)
endPointData Dart s
d = Dart s
-> PlanarGraph s 'Primal (VertexData r v) e f
-> (VertexData r v, VertexData r v)
forall k (s :: k) (w :: World) v e f.
Dart s -> PlanarGraph s w v e f -> (v, v)
PG.endPointData Dart s
d (PlanarGraph s 'Primal (VertexData r v) e f
 -> (VertexData r v, VertexData r v))
-> (PlaneGraph s v e f r
    -> PlanarGraph s 'Primal (VertexData r v) e f)
-> PlaneGraph s v e f r
-> (VertexData r v, VertexData r v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> PlanarGraph s 'Primal (VertexData r v) e f
_graph

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

-- | gets the id of the outer face
--
-- running time: \(O(n)\)
--
outerFaceId    :: (Ord r, Fractional r) => PlaneGraph s v e f r -> FaceId' s
outerFaceId :: PlaneGraph s v e f r -> FaceId' s
outerFaceId PlaneGraph s v e f r
ps = 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
leftFace (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
outerFaceDart PlaneGraph s v e f r
ps) PlaneGraph s v e f r
ps


-- | gets a dart incident to the outer face (in particular, that has the
-- outerface on its left)
--
-- running time: \(O(n)\)
--
outerFaceDart    :: (Ord r, Fractional r) => PlaneGraph s v e f r -> Dart s
outerFaceDart :: PlaneGraph s v e f r -> Dart s
outerFaceDart PlaneGraph s v e f r
ps = Dart s
d
  where
    (VertexId' s
v,VertexData r v
_)  = ((VertexId' s, VertexData r v)
 -> (VertexId' s, VertexData r v) -> Ordering)
-> Vector (VertexId' s, VertexData r v)
-> (VertexId' s, VertexData r v)
forall a. (a -> a -> Ordering) -> Vector a -> a
V.minimumBy (((VertexId' s, VertexData r v) -> Point 2 r)
-> (VertexId' s, VertexData r v)
-> (VertexId' s, VertexData r v)
-> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing ((VertexId' s, VertexData r v)
-> Getting (Point 2 r) (VertexId' s, VertexData r v) (Point 2 r)
-> Point 2 r
forall s a. s -> Getting a s a -> a
^.(VertexData r v -> Const (Point 2 r) (VertexData r v))
-> (VertexId' s, VertexData r v)
-> Const (Point 2 r) (VertexId' s, VertexData r v)
forall s t a b. Field2 s t a b => Lens s t a b
_2((VertexData r v -> Const (Point 2 r) (VertexData r v))
 -> (VertexId' s, VertexData r v)
 -> Const (Point 2 r) (VertexId' s, VertexData r v))
-> ((Point 2 r -> Const (Point 2 r) (Point 2 r))
    -> VertexData r v -> Const (Point 2 r) (VertexData r v))
-> Getting (Point 2 r) (VertexId' s, VertexData r v) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const (Point 2 r) (Point 2 r))
-> VertexData r v -> Const (Point 2 r) (VertexData r v)
forall r v r.
Lens (VertexData r v) (VertexData r v) (Point 2 r) (Point 2 r)
location)) (Vector (VertexId' s, VertexData r v)
 -> (VertexId' s, VertexData r v))
-> (PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v))
-> PlaneGraph s v e f r
-> (VertexId' s, VertexData r v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v)
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v)
vertices (PlaneGraph s v e f r -> (VertexId' s, VertexData r v))
-> PlaneGraph s v e f r -> (VertexId' s, VertexData r v)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r
ps
           -- compare lexicographically; i.e. if same x-coord prefer the one with the
           -- smallest y-coord
    Dart s
d :+ Line 2 r
_ = ((Dart s :+ Line 2 r) -> (Dart s :+ Line 2 r) -> Ordering)
-> Vector (Dart s :+ Line 2 r) -> Dart s :+ Line 2 r
forall a. (a -> a -> Ordering) -> Vector a -> a
V.maximumBy (Line 2 r -> Line 2 r -> Ordering
forall r. (Num r, Ord r) => Line 2 r -> Line 2 r -> Ordering
cmpSlope (Line 2 r -> Line 2 r -> Ordering)
-> ((Dart s :+ Line 2 r) -> Line 2 r)
-> (Dart s :+ Line 2 r)
-> (Dart s :+ Line 2 r)
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` ((Dart s :+ Line 2 r)
-> Getting (Line 2 r) (Dart s :+ Line 2 r) (Line 2 r) -> Line 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Line 2 r) (Dart s :+ Line 2 r) (Line 2 r)
forall core extra extra'.
Lens (core :+ extra) (core :+ extra') extra extra'
extra))
           (Vector (Dart s :+ Line 2 r) -> Dart s :+ Line 2 r)
-> (Vector (Dart s) -> Vector (Dart s :+ Line 2 r))
-> Vector (Dart s)
-> Dart s :+ Line 2 r
forall b c a. (b -> c) -> (a -> b) -> a -> c
.  (Dart s -> Dart s :+ Line 2 r)
-> Vector (Dart s) -> Vector (Dart s :+ Line 2 r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Dart s
d' -> Dart s
d' Dart s -> Line 2 r -> Dart s :+ Line 2 r
forall core extra. core -> extra -> core :+ extra
:+ Dart s -> PlaneGraph s v e f r -> LineSegment 2 v r :+ e
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> LineSegment 2 v r :+ e
edgeSegment Dart s
d' PlaneGraph s v e f r
ps (LineSegment 2 v r :+ e)
-> Getting (Line 2 r) (LineSegment 2 v r :+ e) (Line 2 r)
-> Line 2 r
forall s a. s -> Getting a s a -> a
^. (LineSegment 2 v r -> Const (Line 2 r) (LineSegment 2 v r))
-> (LineSegment 2 v r :+ e)
-> Const (Line 2 r) (LineSegment 2 v r :+ e)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core((LineSegment 2 v r -> Const (Line 2 r) (LineSegment 2 v r))
 -> (LineSegment 2 v r :+ e)
 -> Const (Line 2 r) (LineSegment 2 v r :+ e))
-> ((Line 2 r -> Const (Line 2 r) (Line 2 r))
    -> LineSegment 2 v r -> Const (Line 2 r) (LineSegment 2 v r))
-> Getting (Line 2 r) (LineSegment 2 v r :+ e) (Line 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(LineSegment 2 v r -> Line 2 r)
-> (Line 2 r -> Const (Line 2 r) (Line 2 r))
-> LineSegment 2 v r
-> Const (Line 2 r) (LineSegment 2 v r)
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to LineSegment 2 v r -> Line 2 r
forall t.
HasSupportingLine t =>
t -> Line (Dimension t) (NumType t)
supportingLine)
           (Vector (Dart s) -> Dart s :+ Line 2 r)
-> Vector (Dart s) -> Dart s :+ Line 2 r
forall a b. (a -> b) -> a -> b
$ VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s)
forall k (s :: k) v e f r.
VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s)
incidentEdges VertexId' s
v PlaneGraph s v e f r
ps
    -- based on the approach sketched at https://cstheory.stackexchange.com/questions/27586/finding-outer-face-in-plane-graph-embedded-planar-graph
    -- basically: find the leftmost vertex, find the incident edge with the largest slope
    -- and take the face left of that edge. This is the outerface.
    -- note that this requires that the edges are straight line segments


--------------------------------------------------------------------------------
-- * Reporting Geometries

-- | Reports all edges as line segments
--
-- >>> mapM_ print $ edgeSegments smallG
-- (Dart (Arc 0) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 2 0 :+ 2) :+ "0->2")
-- (Dart (Arc 1) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 2 2 :+ 1) :+ "0->1")
-- (Dart (Arc 2) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 (-1) 4 :+ 3) :+ "0->3")
-- (Dart (Arc 4) +1,ClosedLineSegment (Point2 2 2 :+ 1) (Point2 2 0 :+ 2) :+ "1->2")
-- (Dart (Arc 3) +1,ClosedLineSegment (Point2 2 2 :+ 1) (Point2 (-1) 4 :+ 3) :+ "1->3")
edgeSegments    :: PlaneGraph s v e f r -> V.Vector (Dart s, LineSegment 2 v r :+ e)
edgeSegments :: PlaneGraph s v e f r -> Vector (Dart s, LineSegment 2 v r :+ e)
edgeSegments PlaneGraph s v e f r
ps = ((Dart s, e) -> (Dart s, LineSegment 2 v r :+ e))
-> Vector (Dart s, e) -> Vector (Dart s, LineSegment 2 v r :+ e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Dart s, e) -> (Dart s, LineSegment 2 v r :+ e)
withSegment (Vector (Dart s, e) -> Vector (Dart s, LineSegment 2 v r :+ e))
-> (PlaneGraph s v e f r -> Vector (Dart s, e))
-> PlaneGraph s v e f r
-> Vector (Dart s, LineSegment 2 v r :+ e)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> Vector (Dart s, e)
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> Vector (Dart s, e)
edges (PlaneGraph s v e f r -> Vector (Dart s, LineSegment 2 v r :+ e))
-> PlaneGraph s v e f r -> Vector (Dart s, LineSegment 2 v r :+ e)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r
ps
  where
    withSegment :: (Dart s, e) -> (Dart s, LineSegment 2 v r :+ e)
withSegment (Dart s
d,e
e) = 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
vtxDataToExt VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
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
$ PlaneGraph s v e f r
psPlaneGraph s v e f r
-> Getting
     (VertexData r v, VertexData r v)
     (PlaneGraph 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 (PlaneGraph s v e f r) (VertexData r v, VertexData r v)
forall k (s :: k) v e f r.
Dart s
-> Getter (PlaneGraph s v e f r) (VertexData r v, VertexData r v)
endPointsOf Dart s
d
                            seg :: LineSegment 2 v r
seg   = (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
                        in (Dart s
d, LineSegment 2 v r
seg LineSegment 2 v r -> e -> LineSegment 2 v r :+ e
forall core extra. core -> extra -> core :+ extra
:+ e
e)

-- | Given a dart and the graph constructs the line segment representing the
-- dart. The segment \(\overline{uv})\) is has \(u\) as its tail and \(v\) as
-- its head.
--
-- \(O(1)\)
edgeSegment      :: Dart s -> PlaneGraph s v e f r -> LineSegment 2 v r :+ e
edgeSegment :: Dart s -> PlaneGraph s v e f r -> LineSegment 2 v r :+ e
edgeSegment Dart s
d PlaneGraph s v e f r
ps = LineSegment 2 v r
seg LineSegment 2 v r -> e -> LineSegment 2 v r :+ e
forall core extra. core -> extra -> core :+ extra
:+ PlaneGraph s v e f r
psPlaneGraph 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
  where
    seg :: LineSegment 2 v r
seg = 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
vtxDataToExt VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
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
$ PlaneGraph s v e f r
psPlaneGraph s v e f r
-> Getting
     (VertexData r v, VertexData r v)
     (PlaneGraph 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 (PlaneGraph s v e f r) (VertexData r v, VertexData r v)
forall k (s :: k) v e f r.
Dart s
-> Getter (PlaneGraph 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

-- | The polygon describing the face
--
-- runningtime: \(O(k)\), where \(k\) is the size of the face.
--
--
rawFaceBoundary      :: FaceId' s -> PlaneGraph s v e f r
                    -> SimplePolygon v r :+ f
rawFaceBoundary :: FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f
rawFaceBoundary FaceId' s
i PlaneGraph s v e f r
ps = SimplePolygon v r
pg SimplePolygon v r -> f -> SimplePolygon v r :+ f
forall core extra. core -> extra -> core :+ extra
:+ (PlaneGraph s v e f r
psPlaneGraph 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
i)
  where
    pg :: SimplePolygon v r
pg = [Point 2 r :+ v] -> SimplePolygon v r
forall r p. [Point 2 r :+ p] -> SimplePolygon p r
unsafeFromPoints ([Point 2 r :+ v] -> SimplePolygon v r)
-> (PlaneGraph s v e f r -> [Point 2 r :+ v])
-> PlaneGraph s v e f r
-> SimplePolygon v r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (Point 2 r :+ v) -> [Point 2 r :+ v]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Vector (Point 2 r :+ v) -> [Point 2 r :+ v])
-> (PlaneGraph s v e f r -> Vector (Point 2 r :+ v))
-> PlaneGraph s v e f r
-> [Point 2 r :+ v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (VertexId' s -> Point 2 r :+ v)
-> Vector (VertexId' s) -> Vector (Point 2 r :+ v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\VertexId' s
j -> PlaneGraph s v e f r
psPlaneGraph s v e f r
-> Getting (Point 2 r :+ v) (PlaneGraph s v e f r) (Point 2 r :+ v)
-> Point 2 r :+ v
forall s a. s -> Getting a s a -> a
^.(PlanarGraph s 'Primal (VertexData r v) e f
 -> Const
      (Point 2 r :+ v) (PlanarGraph s 'Primal (VertexData r v) e f))
-> PlaneGraph s v e f r
-> Const (Point 2 r :+ v) (PlaneGraph s v e f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r v) e f
  -> Const
       (Point 2 r :+ v) (PlanarGraph s 'Primal (VertexData r v) e f))
 -> PlaneGraph s v e f r
 -> Const (Point 2 r :+ v) (PlaneGraph s v e f r))
-> (((Point 2 r :+ v) -> Const (Point 2 r :+ v) (Point 2 r :+ v))
    -> PlanarGraph s 'Primal (VertexData r v) e f
    -> Const
         (Point 2 r :+ v) (PlanarGraph s 'Primal (VertexData r v) e f))
-> Getting (Point 2 r :+ v) (PlaneGraph s v e f r) (Point 2 r :+ v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.VertexId' s
-> Lens'
     (PlanarGraph s 'Primal (VertexData r v) e f)
     (DataOf (PlanarGraph s 'Primal (VertexData r v) e f) (VertexId' s))
forall g i. HasDataOf g i => i -> Lens' g (DataOf g i)
dataOf VertexId' s
j((VertexData r v -> Const (Point 2 r :+ v) (VertexData r v))
 -> PlanarGraph s 'Primal (VertexData r v) e f
 -> Const
      (Point 2 r :+ v) (PlanarGraph s 'Primal (VertexData r v) e f))
-> (((Point 2 r :+ v) -> Const (Point 2 r :+ v) (Point 2 r :+ v))
    -> VertexData r v -> Const (Point 2 r :+ v) (VertexData r v))
-> ((Point 2 r :+ v) -> Const (Point 2 r :+ v) (Point 2 r :+ v))
-> PlanarGraph s 'Primal (VertexData r v) e f
-> Const
     (Point 2 r :+ v) (PlanarGraph s 'Primal (VertexData r v) e f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(VertexData r v -> Point 2 r :+ v)
-> ((Point 2 r :+ v) -> Const (Point 2 r :+ v) (Point 2 r :+ v))
-> VertexData r v
-> Const (Point 2 r :+ v) (VertexData r v)
forall (p :: * -> * -> *) (f :: * -> *) s a.
(Profunctor p, Contravariant f) =>
(s -> a) -> Optic' p f s a
to VertexData r v -> Point 2 r :+ v
forall r v. VertexData r v -> Point 2 r :+ v
vtxDataToExt)
       (Vector (VertexId' s) -> Vector (Point 2 r :+ v))
-> (PlaneGraph s v e f r -> Vector (VertexId' s))
-> PlaneGraph s v e f r
-> Vector (Point 2 r :+ v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FaceId' s -> PlaneGraph s v e f r -> Vector (VertexId' s)
forall k (s :: k) v e f r.
FaceId' s -> PlaneGraph s v e f r -> Vector (VertexId' s)
boundaryVertices FaceId' s
i (PlaneGraph s v e f r -> SimplePolygon v r)
-> PlaneGraph s v e f r -> SimplePolygon v r
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r
ps

-- | Alias for rawFace Boundary
--
-- runningtime: \(O(k)\), where \(k\) is the size of the face.
rawFacePolygon :: FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f
rawFacePolygon :: FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f
rawFacePolygon = FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f
forall k (s :: k) v e f r.
FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f
rawFaceBoundary

-- | Lists all faces of the plane graph.
rawFacePolygons    :: PlaneGraph s v e f r
                   -> V.Vector (FaceId' s, SimplePolygon v r :+ f)
rawFacePolygons :: PlaneGraph s v e f r -> Vector (FaceId' s, SimplePolygon v r :+ f)
rawFacePolygons PlaneGraph s v e f r
ps = (FaceId' s -> (FaceId' s, SimplePolygon v r :+ f))
-> Vector (FaceId' s) -> Vector (FaceId' s, SimplePolygon v r :+ f)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\FaceId' s
i -> (FaceId' s
i,FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f
forall k (s :: k) v e f r.
FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f
rawFacePolygon FaceId' s
i PlaneGraph s v e f r
ps)) (Vector (FaceId' s) -> Vector (FaceId' s, SimplePolygon v r :+ f))
-> (PlaneGraph s v e f r -> Vector (FaceId' s))
-> PlaneGraph s v e f r
-> Vector (FaceId' s, SimplePolygon v r :+ f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlaneGraph s v e f r -> Vector (FaceId' s)
forall k (s :: k) v e f r.
PlaneGraph s v e f r -> Vector (FaceId' s)
faces' (PlaneGraph s v e f r
 -> Vector (FaceId' s, SimplePolygon v r :+ f))
-> PlaneGraph s v e f r
-> Vector (FaceId' s, SimplePolygon v r :+ f)
forall a b. (a -> b) -> a -> b
$ PlaneGraph s v e f r
ps

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

-- | Labels the edges of a plane graph with their distances, as specified by
-- the distance function.
withEdgeDistances     :: (Point 2 r ->  Point 2 r -> a)
                      -> PlaneGraph s p e f r -> PlaneGraph s p (a :+ e) f r
withEdgeDistances :: (Point 2 r -> Point 2 r -> a)
-> PlaneGraph s p e f r -> PlaneGraph s p (a :+ e) f r
withEdgeDistances Point 2 r -> Point 2 r -> a
f PlaneGraph s p e f r
g = PlaneGraph s p e f r
gPlaneGraph s p e f r
-> (PlaneGraph s p e f r -> PlaneGraph s p (a :+ e) f r)
-> PlaneGraph s p (a :+ e) f r
forall a b. a -> (a -> b) -> b
&(PlanarGraph s 'Primal (VertexData r p) e f
 -> Identity (PlanarGraph s 'Primal (VertexData r p) (a :+ e) f))
-> PlaneGraph s p e f r -> Identity (PlaneGraph s p (a :+ e) f r)
forall k (s :: k) v e f r k (s :: k) v e f r.
Iso
  (PlaneGraph s v e f r)
  (PlaneGraph s v e f r)
  (PlanarGraph s 'Primal (VertexData r v) e f)
  (PlanarGraph s 'Primal (VertexData r v) e f)
graph((PlanarGraph s 'Primal (VertexData r p) e f
  -> Identity (PlanarGraph s 'Primal (VertexData r p) (a :+ e) f))
 -> PlaneGraph s p e f r -> Identity (PlaneGraph s p (a :+ e) f r))
-> ((Vector (Dart s, e) -> Identity (Vector (Dart s, a :+ e)))
    -> PlanarGraph s 'Primal (VertexData r p) e f
    -> Identity (PlanarGraph s 'Primal (VertexData r p) (a :+ e) f))
-> (Vector (Dart s, e) -> Identity (Vector (Dart s, a :+ e)))
-> PlaneGraph s p e f r
-> Identity (PlaneGraph s p (a :+ e) f r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Vector (Dart s, e) -> Identity (Vector (Dart s, a :+ e)))
-> PlanarGraph s 'Primal (VertexData r p) e f
-> Identity (PlanarGraph s 'Primal (VertexData r p) (a :+ e) f)
forall k (s :: k) (w :: World) v e f e'.
Lens
  (PlanarGraph s w v e f)
  (PlanarGraph s w v e' f)
  (Vector (Dart s, e))
  (Vector (Dart s, e'))
PG.dartData ((Vector (Dart s, e) -> Identity (Vector (Dart s, a :+ e)))
 -> PlaneGraph s p e f r -> Identity (PlaneGraph s p (a :+ e) f r))
-> (Vector (Dart s, e) -> Vector (Dart s, a :+ e))
-> PlaneGraph s p e f r
-> PlaneGraph s p (a :+ e) f r
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
%~ ((Dart s, e) -> (Dart s, a :+ e))
-> Vector (Dart s, e) -> Vector (Dart s, a :+ e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(Dart s
d,e
x) -> (Dart s
d,Dart s -> a
len Dart s
d a -> e -> a :+ e
forall core extra. core -> extra -> core :+ extra
:+ e
x))
  where
    len :: Dart s -> a
len Dart s
d = (Point 2 r -> Point 2 r -> a) -> (Point 2 r, Point 2 r) -> a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Point 2 r -> Point 2 r -> a
f ((Point 2 r, Point 2 r) -> a)
-> ((VertexData r p, VertexData r p) -> (Point 2 r, Point 2 r))
-> (VertexData r p, VertexData r p)
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ASetter
  (VertexData r p, VertexData r p)
  (Point 2 r, Point 2 r)
  (VertexData r p)
  (Point 2 r)
-> (VertexData r p -> Point 2 r)
-> (VertexData r p, VertexData r p)
-> (Point 2 r, Point 2 r)
forall s t a b. ASetter s t a b -> (a -> b) -> s -> t
over ASetter
  (VertexData r p, VertexData r p)
  (Point 2 r, Point 2 r)
  (VertexData r p)
  (Point 2 r)
forall (r :: * -> * -> *) a b.
Bitraversable r =>
Traversal (r a a) (r b b) a b
both (VertexData r p
-> Getting (Point 2 r) (VertexData r p) (Point 2 r) -> Point 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Point 2 r) (VertexData r p) (Point 2 r)
forall r v r.
Lens (VertexData r v) (VertexData r v) (Point 2 r) (Point 2 r)
location) ((VertexData r p, VertexData r p) -> a)
-> (VertexData r p, VertexData r p) -> a
forall a b. (a -> b) -> a -> b
$ Dart s -> PlaneGraph s p e f r -> (VertexData r p, VertexData r p)
forall k (s :: k) v e f r.
Dart s -> PlaneGraph s v e f r -> (VertexData r v, VertexData r v)
endPointData Dart s
d PlaneGraph s p e f r
g