hgeometry- Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone



\(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.



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

visibilitySweep Source #


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

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