Algorithms.Geometry.PolygonTriangulation.MakeMonotone

Documentation

data VertexType

Constructors

Start

Merge

Split

End

Regular

Instances

Eq VertexType

Defined in Algorithms.Geometry.PolygonTriangulation.MakeMonotone

Methods

(==) :: VertexType -> VertexType -> Bool

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

Read VertexType

Defined in Algorithms.Geometry.PolygonTriangulation.MakeMonotone

Methods

readsPrec :: Int -> ReadS VertexType

readList :: ReadS [VertexType]

readPrec :: ReadPrec VertexType

readListPrec :: ReadPrec [VertexType]

Show VertexType

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

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

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

p = p.y < q.y || p.y == q.y && p.x q.y

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

data StatusStruct r

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)

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

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]

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

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

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

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

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

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)

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

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

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

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