What is a Structured Visibility Profile?
To the left is an example of the tree that defines a structured visibility profile (SVP) for a chain c. The modified chain, referred to as t(c), excludes the regions shown in green to the left. This ensures that all points contained "below" the chain are reachable, meaning that there exists a y monotone path from a point at y = -∞ to each point that does not intersect c. Each leaf of the tree corresponds to an down-pocket of the reachable region. The SVP of a chain can be computed in linear time, and can be applied to solve many problems that previously required triangulation. This structure and the algorithm for computing it was developed in 1989 by Paul Heffernan and Joseph Mitchell at Cornell University.
|
How do I compute the SVP?
The full algorithm involves a series of sweeps through the polygonal chain, and therefore the svp can be computed in linear time.
In Phase I, the chain is processed to remove any illegal turns.
In Phase II, the modified chain is processed to remove any intersecting sections that may have resulted from Phase I.
In Phase I, the chain is processed to remove any illegal turns.
In Phase II, the modified chain is processed to remove any intersecting sections that may have resulted from Phase I.
Applications to Simple Polygons
For an explanation of the applications of problems in simple polygons that can be solved more rapidly using an SVP, go here.