hgeometry-0.7.0.0: Geometric Algorithms, Data structures, and Data types.

Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone

Synopsis

# Documentation

data LR Source #

Constructors

 L R
Instances
 Source # Instance details Methods(==) :: LR -> LR -> Bool #(/=) :: LR -> LR -> Bool # Source # Instance details MethodsshowsPrec :: Int -> LR -> ShowS #show :: LR -> String #showList :: [LR] -> ShowS #

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

type P p r = Point 2 r :+ (LR :+ p) Source #

type Stack a = [a] Source #

chainOf :: P p r -> LR Source #

toVtx :: P p r -> Point 2 r :+ p Source #

seg :: P p r -> P p r -> LineSegment 2 p r Source #

process :: (Ord r, Num r) => P p r -> Stack (P p r) -> SP (Stack (P p r)) [LineSegment 2 p r] Source #

isInside :: (Ord r, Num r) => P p r -> (P p r, P p r) -> Bool Source #

test if m does not block the line segment from v to u

mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] Source #

given a comparison function, merge the two ordered lists

splitPolygon :: Ord r => MonotonePolygon p r -> ([Point 2 r :+ (LR :+ p)], [Point 2 r :+ (LR :+ p)]) Source #

When the polygon is in counter clockwise order we return (leftChain,rightChain) ordered from the top-down.

if there are multiple points with the maximum yCoord we pick the rightmost one, if there are multiple point with the minimum yCoord we pick the leftmost one.

running time: $$O(n)$$