hgeometry-0.10.0.0: Geometric Algorithms, Data structures, and Data types.

Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Data.Geometry.PlanarSubdivision

Description

Data type to represent a PlanarSubdivision

Synopsis

Documentation

fromPolygons Source #

Arguments

:: (Foldable1 c, Ord r, Fractional r) 
=> proxy s 
-> f

outer face data

-> c (Polygon t p r :+ f)

the disjoint polygons

-> PlanarSubdivision s p () f r 

Constructs a planar subdivision from a collection of \(k\) disjoint polygons of total complexity \(O(n)\).

pre: The boundary of the polygons is given in counterclockwise orientation

runningtime: \(O(n\log n\log k)\) in case of polygons with holes, and \(O(n\log k)\) in case of simple polygons.

fromPolygons' Source #

Arguments

:: (Foldable1 c, Ord r, Fractional r) 
=> proxy s 
-> f

outer face data

-> c (SomePolygon p r :+ f)

the disjoint polygons

-> PlanarSubdivision s p () f r 

Version of fromPolygons that accepts SomePolygons as input.

fromPolygon Source #

Arguments

:: (Ord r, Fractional r) 
=> proxy s 
-> Polygon t p r 
-> f

data inside

-> f

data outside the polygon

-> PlanarSubdivision s p () f r 

Construct a planar subdivision from a polygon. Since our PlanarSubdivision models only connected planar subdivisions, this may add dummy/invisible edges.

pre: The outer boundary of the polygons is given in counterclockwise orientation

running time: \(O(n)\) for a simple polygon, \(O(n\log n)\) for a polygon with holes.