visibility-0.1.0.2: Simple computation of visibility polygons.

Safe HaskellSafe
LanguageHaskell2010

Data.Geometry.Visibility

Description

The algorithm is relatively simple. The points are sorted by their polar angle relative to the reference point, keeping track of which line segment they belong to. In this ordering, they are assigned tags representing whether they are a start of a segment, or it's end. A comparison is defined on those oriented segments that determines which segment covers the other if viewed from the reference point. Then the list of points is folded over by putting segments in a set, and removing them from it when a starting point or an end point is encountered, respectively. Every time the closest segment to the reference point changes, we output two points of a visibility polygon by computing relevant ray-segment intersections.

Synopsis

Documentation

data Polygon Source

Constructors

Polygon SimplePolygon [SimplePolygon]

Construct a polygon from an simple polygon and a list of holes.

newtype SimplePolygon Source

Constructors

Simple [Point]

Construct a simple polygon from points in a CCW order

visibilityPolygon :: Point -> Polygon -> SimplePolygon Source

Given a Point and a Polygon (possibly with holes), returns a SimplePolygon describing the area visible from the Point inside of the Polygon. O(n log n) where n is the number of points.