Abstract | ||
---|---|---|
We wish to extract the topology from scanned maps. In previous work [GNY] this was done by extracting a skeleton from the Voronoi diagram, but this required vertex labelling and was only useable for polygon maps. We wished to take the crust algorithm of Amenta et al. [ABE] and modify it to extract the skeleton from unlabelled vertices. We find that by reducing the algorithm to a local test on the original Voronoi diagram we may extract both a crust and a skeleton simultaneously, using a variant of the Quad-Edge structure of [GS]. We show that this crust has the properties of the original, and that the resulting skeleton has many practical uses. We illustrate the usefulness of the combined diagram with various applications. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1007/s00453-001-0014-x | Algorithmica |
Keywords | Field | DocType |
Key words. Curve reconstruction,Medial axis,Voronoi diagram,Planar subdivision,Scanned maps,Topology building in GIS. | Polygon,Combinatorics,Vertex (geometry),Crust,Computational geometry,Medial axis,Diagram,Voronoi diagram,Skeleton (computer programming),Mathematics | Journal |
Volume | Issue | ISSN |
30 | 2 | 0178-4617 |
Citations | PageRank | References |
36 | 1.95 | 18 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christopher M. Gold | 1 | 289 | 35.07 |
Jack Snoeyink | 2 | 2842 | 231.68 |