hgeometry-0.12.0.0: Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Algorithms.Geometry.PolygonTriangulation.MakeMonotone

Description

 
Synopsis

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)\)

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)\).