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.TriangulateMonotone

Description

 
Synopsis

Documentation

type MonotonePolygon p r = SimplePolygon p r Source #

Y-monotone polygon. All straight horizontal lines intersects the polygon no more than twice.

triangulate :: (Ord r, Fractional r) => proxy s -> MonotonePolygon 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 -> MonotonePolygon p r -> PlaneGraph s p PolygonEdgeType PolygonFaceData r Source #

Triangulates a polygon of \(n\) vertices

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

computeDiagonals :: (Ord r, Num r) => MonotonePolygon p r -> [LineSegment 2 p r] Source #

Given a y-monotone polygon in counter clockwise order computes the diagonals to add to triangulate the polygon

pre: the input polygon is y-monotone and has \(n \geq 3\) vertices

running time: \(O(n)\)