| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.VisibilityPolygon.Lee
Description
\(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.
Synopsis
- visibilityPolygon :: forall p t r. (Ord r, Fractional r) => Point 2 r -> Polygon t p r -> StarShapedPolygon (Definer p () r) r
- visibilitySweep :: forall p r e. (Ord r, Fractional r) => Vector 2 r -> Maybe (Point 2 r) -> Point 2 r -> [LineSegment 2 p r :+ e] -> [Point 2 r :+ Definer p e r]
- 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)
- 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
Documentation
visibilityPolygon :: forall p t r. (Ord r, Fractional r) => Point 2 r -> Polygon t p r -> StarShapedPolygon (Definer p () r) r Source #
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)\)
Arguments
| :: forall p r e. (Ord r, Fractional r) | |
| => Vector 2 r | starting direction of the sweep |
| -> Maybe (Point 2 r) |
|
| -> 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 Source #
type Definer p e r = Either p (Point 2 r :+ p, LineSegment 2 p r :+ e) Source #
Vertices of the visibility polgyon are either original vertices or defined by some vertex and an edge
type StarShapedPolygon p r = SimplePolygon p r Source #
compareAroundEndPoint :: forall p r e. (Ord r, Fractional r) => Point 2 r -> (LineSegment 2 p r :+ e) -> (LineSegment 2 p r :+ e) -> Ordering Source #
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).