| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone
Description
Synopsis
- type MonotonePolygon p r = SimplePolygon p r
- triangulate :: (Ord r, Fractional r) => proxy s -> MonotonePolygon p r -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
- triangulate' :: (Ord r, Fractional r) => proxy s -> MonotonePolygon p r -> PlaneGraph s p PolygonEdgeType PolygonFaceData r
- computeDiagonals :: (Ord r, Num r) => MonotonePolygon p r -> [LineSegment 2 p r]
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)\)