Title
Kinetic Voronoi/Delaunay Drawing Tools
Abstract
We 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 batchoriented 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 (MP, or the "pen") as it moves through the topological network (visualized as either the Voronoi diagram or Delaunay triangulation). The trailing line accumulates the adjacency relationships of MP. There are thus three parts to our method: the maintenance of MP in the DT/VD; the use of MP to draw the constrained edges in the Delaunay triangulation; and the use of MP to draw the line segment Voronoi diagram. In all cases deletion is the inverse of the original drawing: move MP so as to "roll up" the desired segment. 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.
Year
DOI
Venue
2006
10.1109/ISVD.2006.24
ISVD
Keywords
Field
DocType
computational geometry,cartography,network topology,network visualization,voronoi diagram,mesh generation,geographic information systems,testing,point location,gold,delaunay triangulation,kinetic theory,visualization,robustness,kinetics
Adjacency list,Line segment,Bowyer–Watson algorithm,Computer science,Computational geometry,Theoretical computer science,Voronoi diagram,Constrained Delaunay triangulation,Pitteway triangulation,Delaunay triangulation
Conference
ISBN
Citations 
PageRank 
0-7695-2630-6
6
0.72
References 
Authors
15
2
Name
Order
Citations
PageRank
Christopher M. Gold128935.07
Maciej Dakowicz281.43