Algorithms.Geometry.VisibilityPolygon.Lee

\(O(n\log n)\) time algorithm to compute the visibility polygon of a point inside a polygon (possibly containing holes) with \(n\) vertices, or among a set of \(n\) disjoint segments. The alogirhtm used is the the rotational sweepline algorithm by Lee, described in:

D. T. Lee. Proximity and reachability in the plane. Report R-831, Dept. Elect. Engrg., Univ. Illinois, Urbana, IL, 1978.

Documentation

visibilityPolygon :: forall p t r. (Ord r, Fractional r) => Point 2 r -> Polygon t p r -> StarShapedPolygon (Definer p () r) r

Computes the visibility polygon of a point q in a polygon with \(n\) vertices.

pre: q lies strictly inside the polygon

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

visibilitySweep

Arguments

:: forall p r e. (Ord r, Fractional r)

=> Vector 2 r

starting direction of the sweep

-> Maybe (Point 2 r)

• - point indicating the last point to sweep to

-> Point 2 r

the point form which we compute the visibility polgyon

-> [LineSegment 2 p r :+ e]

-> [Point 2 r :+ Definer p e r]

computes a (partial) visibility polygon of a set of \(n\) disjoint segments. The input segments are allowed to share endpoints, but no intersections or no endpoints in the interior of other segments. The input vector indicates the starting direction, the Maybe point indicates up to which point/dicrection (CCW) of the starting vector we should compute the visibility polygon.

pre : - all line segments are considered closed. - no singleton linesegments exactly pointing away from q. - for every orientattion the visibility is blocked somewhere, i.e. no rays starting in the query point q that are disjoint from all segments. - no vertices at staring direction sv

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

type VisibilityPolygon p e r = StarShapedPolygon (Definer p e r) r

type Definer p e r = Either p (Point 2 r :+ p, LineSegment 2 p r :+ e)

Vertices of the visibility polgyon are either original vertices or defined by some vertex and an edge

type StarShapedPolygon p r = SimplePolygon p r

compareAroundEndPoint :: forall p r e. (Ord r, Fractional r) => Point 2 r -> (LineSegment 2 p r :+ e) -> (LineSegment 2 p r :+ e) -> Ordering

Given two segments that share an endpoint, order them by their order around this common endpoint. I.e. if uv and uw share endpoint u we uv is considered smaller iff v is smaller than w in the counterclockwise order around u (treating the direction from q to the common endpoint as zero).