| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.PolygonTriangulation.MakeMonotone
Description
Synopsis
- makeMonotone :: (Fractional r, Ord r) => proxy s -> Polygon t p r -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
- computeDiagonals :: forall t r p. (Fractional r, Ord r) => Polygon t p r -> [LineSegment 2 p r]
- data VertexType
- classifyVertices :: (Num r, Ord r) => Polygon t p r -> Polygon t (p :+ VertexType) r
Documentation
makeMonotone :: (Fractional r, Ord r) => proxy s -> Polygon t p r -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r Source #
Computes a set of diagionals that decompose the polygon into y-monotone pieces.
pre: the polygon boundary is given in counterClockwise order.
running time: \(O(n\log n)\)
computeDiagonals :: forall t r p. (Fractional r, Ord r) => Polygon t p r -> [LineSegment 2 p r] Source #
Given a polygon, find a set of non-intersecting diagonals that partition the polygon into y-monotone pieces.
running time: \(O(n\log n)\)
data VertexType Source #
Instances
| Eq VertexType Source # | |
| Read VertexType Source # | |
Defined in Algorithms.Geometry.PolygonTriangulation.MakeMonotone Methods readsPrec :: Int -> ReadS VertexType # readList :: ReadS [VertexType] # readPrec :: ReadPrec VertexType # readListPrec :: ReadPrec [VertexType] # | |
| Show VertexType Source # | |
Defined in Algorithms.Geometry.PolygonTriangulation.MakeMonotone Methods showsPrec :: Int -> VertexType -> ShowS # show :: VertexType -> String # showList :: [VertexType] -> ShowS # | |
classifyVertices :: (Num r, Ord r) => Polygon t p r -> Polygon t (p :+ VertexType) r Source #
assigns a vertex type to each vertex
pre: Both the outer boundary and the inner boundary of the polygon are given in CCW order.
running time: \(O(n)\).