Safe Haskell	None
Language	Haskell2010

Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone

Synopsis

type MonotonePolygon p r = SimplePolygon p r
data LR
- = L
- | 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]
type P p r = Point 2 r :+ (LR :+ p)
type Stack a = [a]
chainOf :: P p r -> LR
toVtx :: P p r -> Point 2 r :+ p
seg :: P p r -> P p r -> LineSegment 2 p r
process :: (Ord r, Num r) => P p r -> Stack (P p r) -> SP (Stack (P p r)) [LineSegment 2 p r]
isInside :: (Ord r, Num r) => P p r -> (P p r, P p r) -> Bool
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
splitPolygon :: Ord r => MonotonePolygon p r -> ([Point 2 r :+ (LR :+ p)], [Point 2 r :+ (LR :+ p)])
testPoly5 :: SimplePolygon () Rational

Documentation

type MonotonePolygon p r = SimplePolygon p r Source #

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

testPoly5 :: SimplePolygon () Rational Source #