Safe Haskell	Safe
Language	Haskell2010

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 Point Source

Constructors

Point !Double !Double

Instances

Eq Point Source
Num Point Source
Ord Point Source
Read Point Source
Show Point Source

data Polygon Source

Constructors

Polygon SimplePolygon [SimplePolygon]

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

Instances

Eq Polygon Source
Ord Polygon Source
Read Polygon Source
Show Polygon Source

newtype SimplePolygon Source

Constructors

Simple [Point]

Construct a simple polygon from points in a CCW order

Instances

Eq SimplePolygon Source
Ord SimplePolygon Source
Read SimplePolygon Source
Show SimplePolygon Source

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.