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

Algorithms.Geometry.PolygonTriangulation.Triangulate

Description

 
Synopsis

Documentation

triangulate :: (Ord r, Fractional r) => proxy s -> Polygon t p r -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r Source #

Triangulates a polygon of \(n\) vertices

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

triangulate' :: (Ord r, Fractional r) => proxy s -> Polygon t p r -> PlaneGraph s p PolygonEdgeType PolygonFaceData r Source #

Triangulates a polygon of \(n\) vertices

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

computeDiagonals :: (Ord r, Fractional r) => Polygon t p r -> [LineSegment 2 p r] Source #

Computes a set of diagaonals that together triangulate the input polygon of \(n\) vertices.

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

computeDiagonals' :: (Ord r, Fractional r) => Polygon t p r -> (Polygon t p r, [LineSegment 2 p r]) Source #

Computes a set of diagaonals that together triangulate the input polygon of \(n\) vertices. Returns a copy of the input polygon, whose boundaries are oriented in counter clockwise order, as well.

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