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

Safe HaskellNone
LanguageHaskell2010

Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone

Synopsis

Documentation

data LR Source #

Constructors

L 
R 
Instances
Eq LR Source # 
Instance details

Defined in Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone

Methods

(==) :: LR -> LR -> Bool #

(/=) :: LR -> LR -> Bool #

Show LR Source # 
Instance details

Defined in Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone

Methods

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