Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone

Documentation

type MonotonePolygon p r = SimplePolygon p r

data LR

Constructors

L

R

Instances

Eq LR

Defined in Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone

Methods

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

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

Show LR

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

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

Triangulates a polygon of \(n\) vertices

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

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

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)

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

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

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

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

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