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

Christopher M. Gold, Darka Mioc, François Anton, Ojaswa Sharma, Maciej Dakowicz

    Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review


    This chapter presents a methodology for automated cartographic data in- put, 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 ob ject 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 ob jectives 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.
    Original languageEnglish
    Title of host publicationGeneralized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence
    PublisherSpringer Verlag
    Publication date2008
    ISBN (Print)978-3-540-85125-7
    Publication statusPublished - 2008

    Fingerprint Dive into the research topics of 'A methodology for automated cartographic data input, drawing and editing using kinetic Delaunay/Voronoi diagrams'. Together they form a unique fingerprint.

    Cite this