Polygon Traversal

Hide text Hide pseudo-code

The need to traverse a polygon is typical in many applications. Berg et al. present a way to traverse a polygon set stored using DCEL without using extra storage space for the algorithm. Polygons are ordered into a list to determine the traversing order. List is build by choosing an entry edge for every polygon. Each time an entry polygon is encountered a new polygon is entered. This way all polygons can be visited exatly once.
The entry edge is chosen by selecting a poing in first polygon and calculationg distances of each half-edge to this point. The interior edge that is closest to the point is an entry.

The task is to find the entry half edges and traverse the network in correct order. Entries can be found when find entry button is selected. Traversal can proceed when Traverse button is selected.

  Created Fri Oct 30 13:52:47 EET 2009 - Powered by SVG-hut