| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Algorithms.Geometry.PolygonTriangulation.MakeMonotone
Synopsis
- data VertexType
- classifyVertices :: (Num r, Ord r) => Polygon t p r -> Polygon t (p :+ VertexType) r
- classifyVertices' :: (Num r, Ord r) => SimplePolygon p r -> SimplePolygon (p :+ VertexType) r
- cmpSweep :: Ord r => (Point 2 r :+ e) -> (Point 2 r :+ e) -> Ordering
- type Event r = Point 2 r :+ Two (LineSegment 2 Int r)
- data StatusStruct r = SS {
- _statusStruct :: !(OrdSeq (LineSegment 2 Int r))
- _helper :: !(IntMap Int)
- statusStruct :: forall r r. Lens (StatusStruct r) (StatusStruct r) (OrdSeq (LineSegment 2 Int r)) (OrdSeq (LineSegment 2 Int r))
- helper :: forall r. Lens' (StatusStruct r) (IntMap Int)
- ix' :: Int -> Lens' (Vector a) a
- computeDiagonals :: forall t r p. (Fractional r, Ord r) => Polygon t p r -> [LineSegment 2 p r]
- makeMonotone :: (Fractional r, Ord r) => proxy s -> Polygon t p r -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
- type Sweep p r = WriterT (DList (LineSegment 2 Int r)) (StateT (StatusStruct r) (Reader (Vector (VertexInfo p r))))
- type VertexInfo p r = STR (Point 2 r) p VertexType
- tell' :: LineSegment 2 Int r -> Sweep p r ()
- getIdx :: Event r -> Int
- getVertexType :: Int -> Sweep p r VertexType
- getEventType :: Event r -> Sweep p r VertexType
- handle :: (Fractional r, Ord r) => Event r -> Sweep p r ()
- insertAt :: (Ord r, Fractional r) => Point 2 r -> LineSegment 2 q r -> OrdSeq (LineSegment 2 q r) -> OrdSeq (LineSegment 2 q r)
- deleteAt :: (Fractional r, Ord r) => Point 2 r -> LineSegment 2 p r -> OrdSeq (LineSegment 2 p r) -> OrdSeq (LineSegment 2 p r)
- handleStart :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r ()
- handleEnd :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r ()
- tellIfMerge :: Int -> Point 2 r -> Int -> Sweep p r ()
- getHelper :: Int -> Sweep p r (SP (Point 2 r :+ Int) VertexType)
- lookupLE :: (Ord r, Fractional r) => Point 2 r -> OrdSeq (LineSegment 2 Int r) -> Maybe (LineSegment 2 Int r)
- handleSplit :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r ()
- handleMerge :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r ()
- connectToLeft :: (Fractional r, Ord r) => Int -> Point 2 r -> Sweep p r ()
- isLeftVertex :: Ord r => Int -> Event r -> Bool
- handleRegularL :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r ()
- handleRegularR :: (Fractional r, Ord r) => Int -> Event r -> Sweep p r ()
Documentation
data VertexType Source #
Instances
| Eq VertexType Source # | |
| Read VertexType Source # | |
Defined in Algorithms.Geometry.PolygonTriangulation.MakeMonotone Methods readsPrec :: Int -> ReadS VertexType # readList :: ReadS [VertexType] # readPrec :: ReadPrec VertexType # readListPrec :: ReadPrec [VertexType] # | |
| Show VertexType Source # | |
Defined in Algorithms.Geometry.PolygonTriangulation.MakeMonotone Methods showsPrec :: Int -> VertexType -> ShowS # show :: VertexType -> String # showList :: [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)\).
data StatusStruct r Source #
Constructors
| SS | |
Fields
| |
Instances
| Show r => Show (StatusStruct r) Source # | |
Defined in Algorithms.Geometry.PolygonTriangulation.MakeMonotone Methods showsPrec :: Int -> StatusStruct r -> ShowS # show :: StatusStruct r -> String # showList :: [StatusStruct r] -> ShowS # | |
statusStruct :: forall r r. Lens (StatusStruct r) (StatusStruct r) (OrdSeq (LineSegment 2 Int r)) (OrdSeq (LineSegment 2 Int r)) 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 Sweep p r = WriterT (DList (LineSegment 2 Int r)) (StateT (StatusStruct r) (Reader (Vector (VertexInfo p r)))) Source #
type VertexInfo p r = STR (Point 2 r) p VertexType Source #
getVertexType :: Int -> Sweep p r VertexType Source #
getEventType :: Event r -> Sweep p r VertexType 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 #
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
lookupLE :: (Ord r, Fractional r) => Point 2 r -> OrdSeq (LineSegment 2 Int r) -> Maybe (LineSegment 2 Int r) Source #
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 #