Data.Geometry.PlanarSubdivision.Basic

Documentation

type VertexId' s = VertexId s Primal

type FaceId' s = FaceId s Primal

data VertexData r v

Note that the functor instance is in v

Constructors

VertexData !(Point 2 r) !v

Instances

Bifunctor VertexData

Defined in Data.PlaneGraph

Methods

bimap :: (a -> b) -> (c -> d) -> VertexData a c -> VertexData b d

first :: (a -> b) -> VertexData a c -> VertexData b c

second :: (b -> c) -> VertexData a b -> VertexData a c

Functor (VertexData r)

Defined in Data.PlaneGraph

Methods

fmap :: (a -> b) -> VertexData r a -> VertexData r b

(<$) :: a -> VertexData r b -> VertexData r a

Foldable (VertexData r)

Defined in Data.PlaneGraph

Methods

fold :: Monoid m => VertexData r m -> m

foldMap :: Monoid m => (a -> m) -> VertexData r a -> m

foldr :: (a -> b -> b) -> b -> VertexData r a -> b

foldr' :: (a -> b -> b) -> b -> VertexData r a -> b

foldl :: (b -> a -> b) -> b -> VertexData r a -> b

foldl' :: (b -> a -> b) -> b -> VertexData r a -> b

foldr1 :: (a -> a -> a) -> VertexData r a -> a

foldl1 :: (a -> a -> a) -> VertexData r a -> a

toList :: VertexData r a -> [a]

null :: VertexData r a -> Bool

length :: VertexData r a -> Int

elem :: Eq a => a -> VertexData r a -> Bool

maximum :: Ord a => VertexData r a -> a

minimum :: Ord a => VertexData r a -> a

sum :: Num a => VertexData r a -> a

product :: Num a => VertexData r a -> a

Traversable (VertexData r)

Defined in Data.PlaneGraph

Methods

traverse :: Applicative f => (a -> f b) -> VertexData r a -> f (VertexData r b)

sequenceA :: Applicative f => VertexData r (f a) -> f (VertexData r a)

mapM :: Monad m => (a -> m b) -> VertexData r a -> m (VertexData r b)

sequence :: Monad m => VertexData r (m a) -> m (VertexData r a)

(Eq r, Eq v) => Eq (VertexData r v)

Defined in Data.PlaneGraph

Methods

(==) :: VertexData r v -> VertexData r v -> Bool

(/=) :: VertexData r v -> VertexData r v -> Bool

(Ord r, Ord v) => Ord (VertexData r v)

Defined in Data.PlaneGraph

Methods

compare :: 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

max :: VertexData r v -> VertexData r v -> VertexData r v

min :: VertexData r v -> VertexData r v -> VertexData r v

(Show r, Show v) => Show (VertexData r v)

Defined in Data.PlaneGraph

Methods

showsPrec :: Int -> VertexData r v -> ShowS

show :: VertexData r v -> String

showList :: [VertexData r v] -> ShowS

(ToJSON r, ToJSON v) => ToJSON (VertexData r v)

Defined in Data.PlaneGraph

Methods

toJSON :: VertexData r v -> Value

toEncoding :: VertexData r v -> Encoding

toJSONList :: [VertexData r v] -> Value

toEncodingList :: [VertexData r v] -> Encoding

(FromJSON r, FromJSON v) => FromJSON (VertexData r v)

Defined in Data.PlaneGraph

Methods

parseJSON :: Value -> Parser (VertexData r v)

parseJSONList :: Value -> Parser [VertexData r v]

vData :: forall r v v. Lens (VertexData r v) (VertexData r v) v v

location :: forall r v r. Lens (VertexData r v) (VertexData r v) (Point 2 r) (Point 2 r)

data FaceData h f

The Face data consists of the data itself and a list of holes

Constructors

FaceData (Seq h) !f

Instances

Bifunctor FaceData

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

bimap :: (a -> b) -> (c -> d) -> FaceData a c -> FaceData b d

first :: (a -> b) -> FaceData a c -> FaceData b c

second :: (b -> c) -> FaceData a b -> FaceData a c

Functor (FaceData h)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

fmap :: (a -> b) -> FaceData h a -> FaceData h b

(<$) :: a -> FaceData h b -> FaceData h a

Foldable (FaceData h)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

fold :: Monoid m => FaceData h m -> m

foldMap :: Monoid m => (a -> m) -> FaceData h a -> m

foldr :: (a -> b -> b) -> b -> FaceData h a -> b

foldr' :: (a -> b -> b) -> b -> FaceData h a -> b

foldl :: (b -> a -> b) -> b -> FaceData h a -> b

foldl' :: (b -> a -> b) -> b -> FaceData h a -> b

foldr1 :: (a -> a -> a) -> FaceData h a -> a

foldl1 :: (a -> a -> a) -> FaceData h a -> a

toList :: FaceData h a -> [a]

null :: FaceData h a -> Bool

length :: FaceData h a -> Int

elem :: Eq a => a -> FaceData h a -> Bool

maximum :: Ord a => FaceData h a -> a

minimum :: Ord a => FaceData h a -> a

sum :: Num a => FaceData h a -> a

product :: Num a => FaceData h a -> a

Traversable (FaceData h)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

traverse :: Applicative f => (a -> f b) -> FaceData h a -> f (FaceData h b)

sequenceA :: Applicative f => FaceData h (f a) -> f (FaceData h a)

mapM :: Monad m => (a -> m b) -> FaceData h a -> m (FaceData h b)

sequence :: Monad m => FaceData h (m a) -> m (FaceData h a)

(Eq h, Eq f) => Eq (FaceData h f)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

(==) :: FaceData h f -> FaceData h f -> Bool

(/=) :: FaceData h f -> FaceData h f -> Bool

(Ord h, Ord f) => Ord (FaceData h f)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

compare :: FaceData h f -> FaceData h f -> Ordering

(<) :: FaceData h f -> FaceData h f -> Bool

(<=) :: FaceData h f -> FaceData h f -> Bool

(>) :: FaceData h f -> FaceData h f -> Bool

(>=) :: FaceData h f -> FaceData h f -> Bool

max :: FaceData h f -> FaceData h f -> FaceData h f

min :: FaceData h f -> FaceData h f -> FaceData h f

(Show h, Show f) => Show (FaceData h f)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

showsPrec :: Int -> FaceData h f -> ShowS

show :: FaceData h f -> String

showList :: [FaceData h f] -> ShowS

Generic (FaceData h f)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type Rep (FaceData h f) :: * -> *

Methods

from :: FaceData h f -> Rep (FaceData h f) x

to :: Rep (FaceData h f) x -> FaceData h f

(ToJSON h, ToJSON f) => ToJSON (FaceData h f)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

toJSON :: FaceData h f -> Value

toEncoding :: FaceData h f -> Encoding

toJSONList :: [FaceData h f] -> Value

toEncodingList :: [FaceData h f] -> Encoding

(FromJSON h, FromJSON f) => FromJSON (FaceData h f)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

parseJSON :: Value -> Parser (FaceData h f)

parseJSONList :: Value -> Parser [FaceData h f]

type Rep (FaceData h f)

Defined in Data.Geometry.PlanarSubdivision.Basic

type Rep (FaceData h f) = D1 (MetaData "FaceData" "Data.Geometry.PlanarSubdivision.Basic" "hgeometry-0.7.0.0-3y7zA7ljCTE9s6EHvXHItM" False) (C1 (MetaCons "FaceData" PrefixI True) (S1 (MetaSel (Just "_holes") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Seq h)) :*: S1 (MetaSel (Just "_fData") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 f)))

holes :: forall h f h. Lens (FaceData h f) (FaceData h f) (Seq h) (Seq h)

fData :: forall h f f. Lens (FaceData h f) (FaceData h f) f f

data PlanarSubdivision s v e f r

A planarsubdivision is essentially a bunch of plane-graphs; one for every connected component. These graphs store the global ID's (darts, vertexId's, faceId's) in their data values. This essentially gives us a mapping between the two.

note that a face may actually occur in multiple graphs, hence when we store the edges to the the holes, we store the global edgeId's rather than the local edgeId (dart)'s.

invariant: the outerface has faceId 0

Constructors

PlanarSubdivision (Vector (Component s r)) (Vector (Raw s (VertexId' (Wrap s)) v)) (Vector (Raw s (Dart (Wrap s)) e)) (Vector (Raw s (FaceId' (Wrap s)) f))

Instances

Functor (PlanarSubdivision s v e f)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

fmap :: (a -> b) -> PlanarSubdivision s v e f a -> PlanarSubdivision s v e f b

(<$) :: a -> PlanarSubdivision s v e f b -> PlanarSubdivision s v e f a

(Eq r, Eq v, Eq e, Eq f) => Eq (PlanarSubdivision s v e f r)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

(==) :: PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool

(/=) :: PlanarSubdivision s v e f r -> PlanarSubdivision s v e f r -> Bool

(Show r, Show v, Show e, Show f) => Show (PlanarSubdivision s v e f r)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

showsPrec :: Int -> PlanarSubdivision s v e f r -> ShowS

show :: PlanarSubdivision s v e f r -> String

showList :: [PlanarSubdivision s v e f r] -> ShowS

IsBoxable (PlanarSubdivision s v e f r)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

boundingBox :: PlanarSubdivision s v e f r -> Box (Dimension (PlanarSubdivision s v e f r)) () (NumType (PlanarSubdivision s v e f r))

HasDataOf (PlanarSubdivision s v e f r) (FaceId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (FaceId' s) :: *

Methods

dataOf :: FaceId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (FaceId' s))

HasDataOf (PlanarSubdivision s v e f r) (Dart s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (Dart s))

HasDataOf (PlanarSubdivision s v e f r) (VertexId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (VertexId' s) :: *

Methods

dataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (VertexId' s))

type NumType (PlanarSubdivision s v e f r)

Defined in Data.Geometry.PlanarSubdivision.Basic

type NumType (PlanarSubdivision s v e f r) = r

type Dimension (PlanarSubdivision s v e f r)

Defined in Data.Geometry.PlanarSubdivision.Basic

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

type DataOf (PlanarSubdivision s v e f r) (FaceId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

type DataOf (PlanarSubdivision s v e f r) (FaceId' s) = f

type DataOf (PlanarSubdivision s v e f r) (Dart s)

Defined in Data.Geometry.PlanarSubdivision.Basic

type DataOf (PlanarSubdivision s v e f r) (Dart s) = e

type DataOf (PlanarSubdivision s v e f r) (VertexId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

type DataOf (PlanarSubdivision s v e f r) (VertexId' s) = v

type family Wrap (s :: k) :: k where ...

Equations

Wrap s = Wrap' s

type Component s r = PlaneGraph (Wrap s) (VertexId' s) (Dart s) (FaceData (Dart s) (FaceId' s)) r

A connected component.

For every face f, and every hole in this face, the facedata points to a dart d on the hole s.t. this dart has the face f on its left. i.e. leftFace d = f

data ComponentId s

Instances

Bounded (ComponentId s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

minBound :: ComponentId s

maxBound :: ComponentId s

Enum (ComponentId s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

succ :: ComponentId s -> ComponentId s

pred :: ComponentId s -> ComponentId s

toEnum :: Int -> ComponentId s

fromEnum :: ComponentId s -> Int

enumFrom :: ComponentId s -> [ComponentId s]

enumFromThen :: ComponentId s -> ComponentId s -> [ComponentId s]

enumFromTo :: ComponentId s -> ComponentId s -> [ComponentId s]

enumFromThenTo :: ComponentId s -> ComponentId s -> ComponentId s -> [ComponentId s]

Eq (ComponentId s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

(==) :: ComponentId s -> ComponentId s -> Bool

(/=) :: ComponentId s -> ComponentId s -> Bool

Ord (ComponentId s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

compare :: ComponentId s -> ComponentId s -> Ordering

(<) :: ComponentId s -> ComponentId s -> Bool

(<=) :: ComponentId s -> ComponentId s -> Bool

(>) :: ComponentId s -> ComponentId s -> Bool

(>=) :: ComponentId s -> ComponentId s -> Bool

max :: ComponentId s -> ComponentId s -> ComponentId s

min :: ComponentId s -> ComponentId s -> ComponentId s

Show (ComponentId s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

showsPrec :: Int -> ComponentId s -> ShowS

show :: ComponentId s -> String

showList :: [ComponentId s] -> ShowS

Generic (ComponentId s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type Rep (ComponentId s) :: * -> *

Methods

from :: ComponentId s -> Rep (ComponentId s) x

to :: Rep (ComponentId s) x -> ComponentId s

type Rep (ComponentId s)

Defined in Data.Geometry.PlanarSubdivision.Basic

type Rep (ComponentId s) = D1 (MetaData "ComponentId" "Data.Geometry.PlanarSubdivision.Basic" "hgeometry-0.7.0.0-3y7zA7ljCTE9s6EHvXHItM" True) (C1 (MetaCons "ComponentId" PrefixI True) (S1 (MetaSel (Just "unCI") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Int)))

data PolygonFaceData

Data type that expresses whether or not we are inside or outside the polygon.

Constructors

Inside

Outside

Instances

Eq PolygonFaceData

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

(==) :: PolygonFaceData -> PolygonFaceData -> Bool

(/=) :: PolygonFaceData -> PolygonFaceData -> Bool

Read PolygonFaceData

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

readsPrec :: Int -> ReadS PolygonFaceData

readList :: ReadS [PolygonFaceData]

readPrec :: ReadPrec PolygonFaceData

readListPrec :: ReadPrec [PolygonFaceData]

Show PolygonFaceData

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

showsPrec :: Int -> PolygonFaceData -> ShowS

show :: PolygonFaceData -> String

showList :: [PolygonFaceData] -> ShowS

data PlanarGraph s (w :: World) v e f

A *connected* Planar graph with bidirected edges. I.e. the edges (darts) are directed, however, for every directed edge, the edge in the oposite direction is also in the graph.

The types v, e, and f are the are the types of the data associated with the vertices, edges, and faces, respectively.

The orbits in the embedding are assumed to be in counterclockwise order. Therefore, every dart directly bounds the face to its right.

Instances

(Eq v, Eq e, Eq f) => Eq (PlanarGraph s w v e f)

Defined in Data.PlanarGraph

Methods

(==) :: PlanarGraph s w v e f -> PlanarGraph s w v e f -> Bool

(/=) :: PlanarGraph s w v e f -> PlanarGraph s w v e f -> Bool

(Show v, Show e, Show f) => Show (PlanarGraph s w v e f)

Defined in Data.PlanarGraph

Methods

showsPrec :: Int -> PlanarGraph s w v e f -> ShowS

show :: PlanarGraph s w v e f -> String

showList :: [PlanarGraph s w v e f] -> ShowS

(ToJSON v, ToJSON e, ToJSON f) => ToJSON (PlanarGraph s w v e f)

Defined in Data.PlanarGraph

Methods

toJSON :: PlanarGraph s w v e f -> Value

toEncoding :: PlanarGraph s w v e f -> Encoding

toJSONList :: [PlanarGraph s w v e f] -> Value

toEncodingList :: [PlanarGraph s w v e f] -> Encoding

(FromJSON v, FromJSON e, FromJSON f) => FromJSON (PlanarGraph s Primal v e f)

Defined in Data.PlanarGraph

Methods

parseJSON :: Value -> Parser (PlanarGraph s Primal v e f)

parseJSONList :: Value -> Parser [PlanarGraph s Primal v e f]

HasDataOf (PlanarGraph s w v e f) (Dart s)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s))

HasDataOf (PlanarGraph s w v e f) (VertexId s w)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (VertexId s w) :: *

Methods

dataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w))

HasDataOf (PlanarGraph s w v e f) (FaceId s w)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (FaceId s w) :: *

Methods

dataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w))

type DataOf (PlanarGraph s w v e f) (Dart s)

Defined in Data.PlanarGraph

type DataOf (PlanarGraph s w v e f) (Dart s) = e

type DataOf (PlanarGraph s w v e f) (VertexId s w)

Defined in Data.PlanarGraph

type DataOf (PlanarGraph s w v e f) (VertexId s w) = v

type DataOf (PlanarGraph s w v e f) (FaceId s w)

Defined in Data.PlanarGraph

type DataOf (PlanarGraph s w v e f) (FaceId s w) = f

data PlaneGraph s v e f r

Embedded, *connected*, planar graph

Instances

Functor (PlaneGraph s v e f)

Defined in Data.PlaneGraph

Methods

fmap :: (a -> b) -> PlaneGraph s v e f a -> PlaneGraph s v e f b

(<$) :: a -> PlaneGraph s v e f b -> PlaneGraph s v e f a

(Eq r, Eq v, Eq e, Eq f) => Eq (PlaneGraph s v e f r)

Defined in Data.PlaneGraph

Methods

(==) :: 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

(Show r, Show v, Show e, Show f) => Show (PlaneGraph s v e f r)

Defined in Data.PlaneGraph

Methods

showsPrec :: Int -> PlaneGraph s v e f r -> ShowS

show :: PlaneGraph s v e f r -> String

showList :: [PlaneGraph s v e f r] -> ShowS

(ToJSON r, ToJSON v, ToJSON e, ToJSON f) => ToJSON (PlaneGraph s v e f r)

Defined in Data.PlaneGraph

Methods

toJSON :: PlaneGraph s v e f r -> Value

toEncoding :: PlaneGraph s v e f r -> Encoding

toJSONList :: [PlaneGraph s v e f r] -> Value

toEncodingList :: [PlaneGraph s v e f r] -> Encoding

(FromJSON r, FromJSON v, FromJSON e, FromJSON f) => FromJSON (PlaneGraph s v e f r)

Defined in Data.PlaneGraph

Methods

parseJSON :: Value -> Parser (PlaneGraph s v e f r)

parseJSONList :: Value -> Parser [PlaneGraph s v e f r]

IsBoxable (PlaneGraph s v e f r)

Defined in Data.PlaneGraph

Methods

boundingBox :: PlaneGraph s v e f r -> Box (Dimension (PlaneGraph s v e f r)) () (NumType (PlaneGraph s v e f r))

HasDataOf (PlaneGraph s v e f r) (FaceId' s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (FaceId' s) :: *

Methods

dataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s))

HasDataOf (PlaneGraph s v e f r) (Dart s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s))

HasDataOf (PlaneGraph s v e f r) (VertexId' s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (VertexId' s) :: *

Methods

dataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s))

type NumType (PlaneGraph s v e f r)

Defined in Data.PlaneGraph

type NumType (PlaneGraph s v e f r) = r

type Dimension (PlaneGraph s v e f r)

Defined in Data.PlaneGraph

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

type DataOf (PlaneGraph s v e f r) (FaceId' s)

Defined in Data.PlaneGraph

type DataOf (PlaneGraph s v e f r) (FaceId' s) = f

type DataOf (PlaneGraph s v e f r) (Dart s)

Defined in Data.PlaneGraph

type DataOf (PlaneGraph s v e f r) (Dart s) = e

type DataOf (PlaneGraph s v e f r) (VertexId' s)

Defined in Data.PlaneGraph

type DataOf (PlaneGraph s v e f r) (VertexId' s) = v

fromSimplePolygon

Arguments

:: (Ord r, Fractional r)

=> proxy s

-> SimplePolygon p r

-> f

data inside

-> f

data outside the polygon

-> PlanarSubdivision s p () f r

Construct a planar subdivision from a simple polygon

running time: \(O(n)\).

fromConnectedSegments :: (Foldable f, Ord r, Fractional r) => proxy s -> f (LineSegment 2 p r :+ e) -> PlanarSubdivision s (NonEmpty p) e () r

Constructs a connected planar subdivision.

pre: the segments form a single connected component running time: \(O(n\log n)\)

fromPlaneGraph :: forall s v e f r. (Ord r, Fractional r) => PlaneGraph s v e f r -> PlanarSubdivision s v e f r

Constructs a planarsubdivision from a PlaneGraph

runningTime: \(O(n)\)

fromPlaneGraph' :: forall s v e f r. PlaneGraph s v e f r -> Dart s -> PlanarSubdivision s v e f r

Given a (connected) PlaneGraph and a dart that has the outerface on its left | Constructs a planarsubdivision

runningTime: \(O(n)\)

numVertices :: PlanarSubdivision s v e f r -> Int

Get the number of vertices

>>> numVertices myGraph
4

numEdges :: PlanarSubdivision s v e f r -> Int

Get the number of Edges

>>> numEdges myGraph
6

numFaces :: PlanarSubdivision s v e f r -> Int

Get the number of faces

>>> numFaces myGraph
4

numDarts :: PlanarSubdivision s v e f r -> Int

Get the number of Darts

>>> numDarts myGraph
12

dual :: Getter (PlanarGraph s w v e f) (PlanarGraph s (DualOf w) f e v)

components :: forall s v e f r r. Lens (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f r) (Vector (Component s r)) (Vector (Component s r))

component :: ComponentId s -> Lens' (PlanarSubdivision s v e f r) (Component s r)

vertices' :: PlanarSubdivision s v e f r -> Vector (VertexId' s)

Enumerate all vertices

>>> vertices' myGraph
[VertexId 0,VertexId 1,VertexId 2,VertexId 3]

vertices :: PlanarSubdivision s v e f r -> Vector (VertexId' s, VertexData r v)

Enumerate all vertices, together with their vertex data

edges' :: PlanarSubdivision s v e f r -> Vector (Dart s)

Enumerate all edges. We report only the Positive darts

edges :: PlanarSubdivision s v e f r -> Vector (Dart s, e)

Enumerate all edges with their edge data. We report only the Positive darts.

>>> mapM_ print $ edges myGraph
(Dart (Arc 2) +1,"c+")
(Dart (Arc 1) +1,"b+")
(Dart (Arc 0) +1,"a+")
(Dart (Arc 5) +1,"g+")
(Dart (Arc 4) +1,"e+")
(Dart (Arc 3) +1,"d+")

faces' :: PlanarSubdivision s v e f r -> Vector (FaceId' s)

faces :: PlanarSubdivision s v e f r -> Vector (FaceId' s, FaceData (Dart s) f)

internalFaces :: (Ord r, Fractional r) => PlanarSubdivision s v e f r -> Vector (FaceId' s, FaceData (Dart s) f)

Enumerates all faces with their face data exlcluding the outer face

darts' :: PlanarSubdivision s v e f r -> Vector (Dart s)

Enumerate all darts

headOf :: Dart s -> PlanarSubdivision s v e f r -> VertexId' s

The vertex this dart is heading in to

running time: \(O(1)\)

tailOf :: Dart s -> PlanarSubdivision s v e f r -> VertexId' s

The tail of a dart, i.e. the vertex this dart is leaving from

running time: \(O(1)\)

twin :: Dart s -> Dart s

Get the twin of this dart (edge)

>>> twin (dart 0 "+1")
Dart (Arc 0) -1
>>> twin (dart 0 "-1")
Dart (Arc 0) +1

endPoints :: Dart s -> PlanarSubdivision s v e f r -> (VertexId' s, VertexId' s)

endPoints d g = (tailOf d g, headOf d g)

running time: \(O(1)\)

incidentEdges :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)

All edges incident to vertex v, in counterclockwise order around v.

running time: \(O(k)\), where \(k\) is the number of edges reported.

incomingEdges :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)

All incoming edges incident to vertex v, in counterclockwise order around v.

outgoingEdges :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)

All outgoing edges incident to vertex v, in counterclockwise order around v.

nextIncidentEdge :: Dart s -> PlanarSubdivision s v e f r -> Dart s

Given a dart d that points into some vertex v, report the next dart e in the cyclic order around v.

running time: \(O(1)\)

neighboursOf :: VertexId' s -> PlanarSubdivision s v e f r -> Vector (VertexId' s)

Gets the neighbours of a particular vertex, in counterclockwise order around the vertex.

running time: \(O(k)\), where \(k\) is the output size

leftFace :: Dart s -> PlanarSubdivision s v e f r -> FaceId' s

The face to the left of the dart

running time: \(O(1)\).

rightFace :: Dart s -> PlanarSubdivision s v e f r -> FaceId' s

The face to the right of the dart

running time: \(O(1)\).

outerBoundaryDarts :: FaceId' s -> PlanarSubdivision s v e f r -> Vector (Dart s)

The darts on the outer boundary of the face, for internal faces in clockwise order, for the outer face in counter clockwise order.

running time: \(O(k)\), where \(k\) is the output size.

boundaryVertices :: FaceId' s -> PlanarSubdivision s v e f r -> Vector (VertexId' s)

The vertices of the outer boundary of the face, for internal faces in clockwise order, for the outer face in counter clockwise order.

running time: \(O(k)\), where \(k\) is the output size.

holesOf :: FaceId' s -> PlanarSubdivision s v e f r -> Seq (Dart s)

Lists the holes in this face, given as a list of darts to arbitrary darts on those faces.

running time: \(O(k)\), where \(k\) is the number of darts returned.

outerFaceId :: PlanarSubdivision s v e f r -> FaceId' s

gets the id of the outer face

running time: \(O(1)\)

boundary' :: Dart s -> PlanarSubdivision s v e f r -> Vector (Dart s)

Generates the darts incident to a face, starting with the given dart.

\(O(k)\), where \(k\) is the number of darts reported

locationOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (Point 2 r)

class HasDataOf g i where

Minimal complete definition

dataOf

Associated Types

type DataOf g i

Methods

dataOf :: i -> Lens' g (DataOf g i)

get the data associated with the value i.

running time: \(O(1)\) to read the data, \(O(n)\) to write it.

Instances

HasDataOf (PlanarGraph s w v e f) (Dart s)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s))

HasDataOf (PlaneGraph s v e f r) (FaceId' s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (FaceId' s) :: *

Methods

dataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s))

HasDataOf (PlaneGraph s v e f r) (Dart s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s))

HasDataOf (PlaneGraph s v e f r) (VertexId' s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (VertexId' s) :: *

Methods

dataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s))

HasDataOf (PlanarSubdivision s v e f r) (FaceId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (FaceId' s) :: *

Methods

dataOf :: FaceId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (FaceId' s))

HasDataOf (PlanarSubdivision s v e f r) (Dart s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (Dart s))

HasDataOf (PlanarSubdivision s v e f r) (VertexId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (VertexId' s) :: *

Methods

dataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (VertexId' s))

HasDataOf (PlanarGraph s w v e f) (VertexId s w)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (VertexId s w) :: *

Methods

dataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w))

HasDataOf (PlanarGraph s w v e f) (FaceId s w)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (FaceId s w) :: *

Methods

dataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w))

endPointsOf :: Dart s -> Getter (PlanarSubdivision s v e f r) (VertexData r v, VertexData r v)

Getter for the data at the endpoints of a dart

running time: \(O(1)\)

endPointData :: Dart s -> PlanarSubdivision s v e f r -> (VertexData r v, VertexData r v)

data corresponding to the endpoints of the dart

running time: \(O(1)\)

edgeSegment :: Dart s -> PlanarSubdivision s v e f r -> LineSegment 2 v r :+ e

Given a dart and the subdivision constructs the line segment representing it

\(O(1)\)

edgeSegments :: PlanarSubdivision s v e f r -> Vector (Dart s, LineSegment 2 v r :+ e)

Reports all edges as line segments

rawFacePolygon :: FaceId' s -> PlanarSubdivision s v e f r -> SomePolygon v r :+ f

Constructs the boundary of the given face

\(O(k)\), where \(k\) is the complexity of the face

rawFaceBoundary :: FaceId' s -> PlanarSubdivision s v e f r -> SimplePolygon v r :+ f

Constructs the outer boundary of the face

\(O(k)\), where \(k\) is the complexity of the outer boundary of the face

rawFacePolygons :: PlanarSubdivision s v e f r -> Vector (FaceId' s, SomePolygon v r :+ f)

Lists all faces of the planar subdivision.

newtype VertexId s (w :: World)

A vertex in a planar graph. A vertex is tied to a particular planar graph by the phantom type s, and to a particular world w.

Constructors

VertexId

Fields

• _unVertexId :: Int

Instances

Enum (VertexId s w)

Defined in Data.PlanarGraph

Methods

succ :: VertexId s w -> VertexId s w

pred :: VertexId s w -> VertexId s w

toEnum :: Int -> VertexId s w

fromEnum :: VertexId s w -> Int

enumFrom :: VertexId s w -> [VertexId s w]

enumFromThen :: VertexId s w -> VertexId s w -> [VertexId s w]

enumFromTo :: VertexId s w -> VertexId s w -> [VertexId s w]

enumFromThenTo :: VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w]

Eq (VertexId s w)

Defined in Data.PlanarGraph

Methods

(==) :: VertexId s w -> VertexId s w -> Bool

(/=) :: VertexId s w -> VertexId s w -> Bool

Ord (VertexId s w)

Defined in Data.PlanarGraph

Methods

compare :: VertexId s w -> VertexId s w -> Ordering

(<) :: VertexId s w -> VertexId s w -> Bool

(<=) :: VertexId s w -> VertexId s w -> Bool

(>) :: VertexId s w -> VertexId s w -> Bool

(>=) :: VertexId s w -> VertexId s w -> Bool

max :: VertexId s w -> VertexId s w -> VertexId s w

min :: VertexId s w -> VertexId s w -> VertexId s w

Show (VertexId s w)

Defined in Data.PlanarGraph

Methods

showsPrec :: Int -> VertexId s w -> ShowS

show :: VertexId s w -> String

showList :: [VertexId s w] -> ShowS

ToJSON (VertexId s w)

Defined in Data.PlanarGraph

Methods

toJSON :: VertexId s w -> Value

toEncoding :: VertexId s w -> Encoding

toJSONList :: [VertexId s w] -> Value

toEncodingList :: [VertexId s w] -> Encoding

FromJSON (VertexId s w)

Defined in Data.PlanarGraph

Methods

parseJSON :: Value -> Parser (VertexId s w)

parseJSONList :: Value -> Parser [VertexId s w]

HasDataOf (PlaneGraph s v e f r) (VertexId' s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (VertexId' s) :: *

Methods

dataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s))

HasDataOf (PlanarSubdivision s v e f r) (VertexId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (VertexId' s) :: *

Methods

dataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (VertexId' s))

HasDataOf (PlanarGraph s w v e f) (VertexId s w)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (VertexId s w) :: *

Methods

dataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w))

type DataOf (PlaneGraph s v e f r) (VertexId' s)

Defined in Data.PlaneGraph

type DataOf (PlaneGraph s v e f r) (VertexId' s) = v

type DataOf (PlanarSubdivision s v e f r) (VertexId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

type DataOf (PlanarSubdivision s v e f r) (VertexId' s) = v

type DataOf (PlanarGraph s w v e f) (VertexId s w)

Defined in Data.PlanarGraph

type DataOf (PlanarGraph s w v e f) (VertexId s w) = v

newtype FaceId s w

A face

Constructors

FaceId

Fields

• _unFaceId :: VertexId s (DualOf w)

Instances

Eq (FaceId s w)

Defined in Data.PlanarGraph

Methods

(==) :: FaceId s w -> FaceId s w -> Bool

(/=) :: FaceId s w -> FaceId s w -> Bool

Ord (FaceId s w)

Defined in Data.PlanarGraph

Methods

compare :: FaceId s w -> FaceId s w -> Ordering

(<) :: FaceId s w -> FaceId s w -> Bool

(<=) :: FaceId s w -> FaceId s w -> Bool

(>) :: FaceId s w -> FaceId s w -> Bool

(>=) :: FaceId s w -> FaceId s w -> Bool

max :: FaceId s w -> FaceId s w -> FaceId s w

min :: FaceId s w -> FaceId s w -> FaceId s w

Show (FaceId s w)

Defined in Data.PlanarGraph

Methods

showsPrec :: Int -> FaceId s w -> ShowS

show :: FaceId s w -> String

showList :: [FaceId s w] -> ShowS

ToJSON (FaceId s w)

Defined in Data.PlanarGraph

Methods

toJSON :: FaceId s w -> Value

toEncoding :: FaceId s w -> Encoding

toJSONList :: [FaceId s w] -> Value

toEncodingList :: [FaceId s w] -> Encoding

FromJSON (FaceId s w)

Defined in Data.PlanarGraph

Methods

parseJSON :: Value -> Parser (FaceId s w)

parseJSONList :: Value -> Parser [FaceId s w]

HasDataOf (PlaneGraph s v e f r) (FaceId' s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (FaceId' s) :: *

Methods

dataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s))

HasDataOf (PlanarSubdivision s v e f r) (FaceId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (FaceId' s) :: *

Methods

dataOf :: FaceId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (FaceId' s))

HasDataOf (PlanarGraph s w v e f) (FaceId s w)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (FaceId s w) :: *

Methods

dataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w))

type DataOf (PlaneGraph s v e f r) (FaceId' s)

Defined in Data.PlaneGraph

type DataOf (PlaneGraph s v e f r) (FaceId' s) = f

type DataOf (PlanarSubdivision s v e f r) (FaceId' s)

Defined in Data.Geometry.PlanarSubdivision.Basic

type DataOf (PlanarSubdivision s v e f r) (FaceId' s) = f

type DataOf (PlanarGraph s w v e f) (FaceId s w)

Defined in Data.PlanarGraph

type DataOf (PlanarGraph s w v e f) (FaceId s w) = f

data Dart s

A dart represents a bi-directed edge. I.e. a dart has a direction, however the dart of the oposite direction is always present in the planar graph as well.

Instances

Enum (Dart s)

Defined in Data.PlanarGraph

Methods

succ :: Dart s -> Dart s

pred :: Dart s -> Dart s

toEnum :: Int -> Dart s

fromEnum :: Dart s -> Int

enumFrom :: Dart s -> [Dart s]

enumFromThen :: Dart s -> Dart s -> [Dart s]

enumFromTo :: Dart s -> Dart s -> [Dart s]

enumFromThenTo :: Dart s -> Dart s -> Dart s -> [Dart s]

Eq (Dart s)

Defined in Data.PlanarGraph

Methods

(==) :: Dart s -> Dart s -> Bool

(/=) :: Dart s -> Dart s -> Bool

Ord (Dart s)

Defined in Data.PlanarGraph

Methods

compare :: Dart s -> Dart s -> Ordering

(<) :: Dart s -> Dart s -> Bool

(<=) :: Dart s -> Dart s -> Bool

(>) :: Dart s -> Dart s -> Bool

(>=) :: Dart s -> Dart s -> Bool

max :: Dart s -> Dart s -> Dart s

min :: Dart s -> Dart s -> Dart s

Show (Dart s)

Defined in Data.PlanarGraph

Methods

showsPrec :: Int -> Dart s -> ShowS

show :: Dart s -> String

showList :: [Dart s] -> ShowS

HasDataOf (PlanarGraph s w v e f) (Dart s)

Defined in Data.PlanarGraph

Associated Types

type DataOf (PlanarGraph s w v e f) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s))

HasDataOf (PlaneGraph s v e f r) (Dart s)

Defined in Data.PlaneGraph

Associated Types

type DataOf (PlaneGraph s v e f r) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s))

HasDataOf (PlanarSubdivision s v e f r) (Dart s)

Defined in Data.Geometry.PlanarSubdivision.Basic

Associated Types

type DataOf (PlanarSubdivision s v e f r) (Dart s) :: *

Methods

dataOf :: Dart s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (Dart s))

type DataOf (PlanarGraph s w v e f) (Dart s)

Defined in Data.PlanarGraph

type DataOf (PlanarGraph s w v e f) (Dart s) = e

type DataOf (PlaneGraph s v e f r) (Dart s)

Defined in Data.PlaneGraph

type DataOf (PlaneGraph s v e f r) (Dart s) = e

type DataOf (PlanarSubdivision s v e f r) (Dart s)

Defined in Data.Geometry.PlanarSubdivision.Basic

type DataOf (PlanarSubdivision s v e f r) (Dart s) = e

data World

The world in which the graph lives

Constructors

Primal

Dual

Instances

Eq World

Defined in Data.PlanarGraph

Methods

(==) :: World -> World -> Bool

(/=) :: World -> World -> Bool

Show World

Defined in Data.PlanarGraph

Methods

showsPrec :: Int -> World -> ShowS

show :: World -> String

showList :: [World] -> ShowS

rawVertexData :: forall s v e f r v. Lens (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f r) (Vector (Raw s (VertexId' (Wrap s)) v)) (Vector (Raw s (VertexId' (Wrap s)) v))

rawDartData :: forall s v e f r e. Lens (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f r) (Vector (Raw s (Dart (Wrap s)) e)) (Vector (Raw s (Dart (Wrap s)) e))

rawFaceData :: forall s v e f r f. Lens (PlanarSubdivision s v e f r) (PlanarSubdivision s v e f r) (Vector (Raw s (FaceId' (Wrap s)) f)) (Vector (Raw s (FaceId' (Wrap s)) f))

dataVal :: forall s ia a a. Lens (Raw s ia a) (Raw s ia a) a a

dartMapping :: PlanarSubdivision s v e f r -> Vector (Dart (Wrap s), Dart s)

data Raw s ia a

Constructors

Raw

Fields

• _compId :: !(ComponentId s)
• _idxVal :: !ia
• _dataVal :: !a

Instances

Functor (Raw s ia)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

fmap :: (a -> b) -> Raw s ia a -> Raw s ia b

(<$) :: a -> Raw s ia b -> Raw s ia a

Foldable (Raw s ia)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

fold :: Monoid m => Raw s ia m -> m

foldMap :: Monoid m => (a -> m) -> Raw s ia a -> m

foldr :: (a -> b -> b) -> b -> Raw s ia a -> b

foldr' :: (a -> b -> b) -> b -> Raw s ia a -> b

foldl :: (b -> a -> b) -> b -> Raw s ia a -> b

foldl' :: (b -> a -> b) -> b -> Raw s ia a -> b

foldr1 :: (a -> a -> a) -> Raw s ia a -> a

foldl1 :: (a -> a -> a) -> Raw s ia a -> a

toList :: Raw s ia a -> [a]

null :: Raw s ia a -> Bool

length :: Raw s ia a -> Int

elem :: Eq a => a -> Raw s ia a -> Bool

maximum :: Ord a => Raw s ia a -> a

minimum :: Ord a => Raw s ia a -> a

sum :: Num a => Raw s ia a -> a

product :: Num a => Raw s ia a -> a

Traversable (Raw s ia)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

traverse :: Applicative f => (a -> f b) -> Raw s ia a -> f (Raw s ia b)

sequenceA :: Applicative f => Raw s ia (f a) -> f (Raw s ia a)

mapM :: Monad m => (a -> m b) -> Raw s ia a -> m (Raw s ia b)

sequence :: Monad m => Raw s ia (m a) -> m (Raw s ia a)

(Eq ia, Eq a) => Eq (Raw s ia a)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

(==) :: Raw s ia a -> Raw s ia a -> Bool

(/=) :: Raw s ia a -> Raw s ia a -> Bool

(Show ia, Show a) => Show (Raw s ia a)

Defined in Data.Geometry.PlanarSubdivision.Basic

Methods

showsPrec :: Int -> Raw s ia a -> ShowS

show :: Raw s ia a -> String

showList :: [Raw s ia a] -> ShowS