Regresar

A methodology for automated cartographic data input, drawing and editing using kinetic Delaunay/Voronoi diagrams

Abstract:

This chapter presents a methodology for automated cartographic data input, drawing and editing. This methodology is based on kinematic algorithms for point and line Delaunay triangulation and the Voronoi diagram. It allows one to automate some parts of the manual digitization process and the topological editing of maps that preserve map updates. The manual digitization process is replaced by computer assisted skeletonization using scanned paper maps. We are using the Delaunay triangulation and the Voronoi diagram in order to extract the skeletons that are guaranteed to be topologically correct. The features thus extracted as object centrelines can be stored as vector maps in a Geographic Information System after labelling and editing. This research work can also be used for updates from sources that are either paper copy maps or digital raster images. A prototype application that was developed as part of the research has been presented. We also describe two reversible line-drawing methods for cartographic applications based on the kinetic (moving-point) Voronoi diagram. Our objectives were to optimize the user's ability to draw and edit the map, rather than to produce the most efficient batch-oriented algorithm for large data sets, and all our algorithms are based on local operations (except for basic point location). Because the deletion of individual points or line segments is a necessary part of the manual editing process, incremental insertion and deletion is used. The original concept used here is that, as a curve (line) is the locus of a moving point, then segments are drawn by maintaining the topology of a single moving point (abbreviated as MP hereafter, or the "pen") as it moves through the topological network (visualized as either the Voronoi diagram or Delaunay triangulation). This approach also has the interesting property that a "log file" of all operations may be preserved, allowing reversion to previous map states, or "dates", as required. © 2009 Springer-Verlag Berlin Heidelberg.