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

Algorithms.Geometry.PolygonTriangulation.MakeMonotone

Synopsis

# Documentation

Constructors

 Start Merge Split End Regular
Instances
 Source # Instance details Methods Source # Instance details Methods Source # Instance details MethodsshowList :: [VertexType] -> ShowS #

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

cmpSweep :: Ord r => (Point 2 r :+ e) -> (Point 2 r :+ e) -> Ordering Source #

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

data StatusStruct r Source #

Constructors

 SS Fields_statusStruct :: !(OrdSeq (LineSegment 2 Int r)) _helper :: !(IntMap Int)for every e_i, the id of the helper vertex
Instances
 Show r => Show (StatusStruct r) Source # Instance details MethodsshowsPrec :: Int -> StatusStruct r -> ShowS #show :: StatusStruct r -> String #showList :: [StatusStruct r] -> ShowS #

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 #