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

Safe HaskellNone
LanguageHaskell2010

Algorithms.Geometry.PolygonTriangulation.MakeMonotone

Synopsis

Documentation

classifyVertices :: (Num r, Ord r) => Polygon t p r -> Polygon t (p :+ VertexType) r Source #

assigns a vertex type to each vertex

pre: the polygon is given in CCW order

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

classifyVertices' :: (Num r, Ord r) => SimplePolygon p r -> SimplePolygon (p :+ VertexType) r Source #

assigns a vertex type to each vertex

pre: the polygon is given in CCW order

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

type Event r = Point 2 r :+ Two (LineSegment 2 Int r) Source #

data StatusStruct r Source #

Constructors

SS 

Fields

ix' :: Int -> Lens' (Vector a) a Source #

computeDiagonals :: forall t r p. (Fractional r, Ord r) => Polygon t p r -> [LineSegment 2 p r] Source #

Given a polygon, find a set of non-intersecting diagonals that partition the polygon into y-monotone pieces.

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

makeMonotone :: (Fractional r, Ord r) => proxy s -> Polygon t p r -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r Source #

Computes a set of diagionals that decompose the polygon into y-monotone pieces.

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

type VertexInfo p r = STR (Point 2 r) p VertexType Source #

tell' :: LineSegment 2 Int r -> Sweep p r () Source #

handle :: (Fractional r, Ord r) => Event r -> Sweep p r () Source #

insertAt :: (Ord r, Fractional r) => Point 2 r -> LineSegment 2 q r -> OrdSeq (LineSegment 2 q r) -> OrdSeq (LineSegment 2 q r) Source #

deleteAt :: (Fractional r, Ord r) => Point 2 r -> LineSegment 2 p r -> OrdSeq (LineSegment 2 p r) -> OrdSeq (LineSegment 2 p r) Source #

handleStart :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r () Source #

handleEnd :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r () Source #

tellIfMerge :: Int -> Point 2 r -> Int -> Sweep p r () Source #

Adds edge (i,j) if e_j's helper is a merge vertex

getHelper :: Int -> Sweep p r (SP (Point 2 r :+ Int) VertexType) Source #

Get the helper of edge i, and its vertex type

handleSplit :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r () Source #

handleMerge :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r () Source #

connectToLeft :: (Fractional r, Ord r) => Int -> Point 2 r -> Sweep p r () Source #

finds the edge j to the left of v_i, and connect v_i to it if the helper of j is a merge vertex

isLeftVertex :: Ord r => Int -> Event r -> Bool Source #

returns True if v the interior of the polygon is to the right of v

handleRegularL :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r () Source #

handleRegularR :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r () Source #