The Quad-Arc Data Structure

摘要

In Gold et al. (1996) a simple polygon digitizing technique was described where 'fringe' points were digitized around the interior of each map polygon, the Voronoi diagram constructed and the relevant polygon boundary segments extracted fro mthe Voronoi cells. Gold (1997a) extended this to work with scanned map input, where the fringe points were generated automatically, and complete polygon boundary arcs were output. This work has now been extended by replacing the original triangulation data structure with the Quad-Edge structure of Guibas and Stolfi (1985). this has been modified for polygon mapping, and permits the preservation of complete map topology within a simply-generated structure. Its properties permit work on any manifold for any connected graph, and it may be simply coded using an object-oriented language.