Generating realistic terrains with higher-order Delaunay triangulations. (English) Zbl 1110.65022
Summary: For hydrologic applications, terrain models should have few local minima, and drainage lines should coincide with edges. We show that triangulating a set of points with elevations such that the number of local minima of the resulting terrain is minimized is NP-hard for degenerate point sets. The same result applies when there are no degeneracies for higher-order Delaunay triangulations. Two heuristics are presented to reduce the number of local minima for higher-order Delaunay triangulations, which start out with the Delaunay triangulation. We give efficient algorithms for their implementation, and test on real-world data how well they perform. We also study another desirable drainage characteristic, few valley components, and how to obtain it for higher-order Delaunay triangulations. This gives rise to a third heuristic. Tables and visualizations show how the heuristics perform for the drainage characteristics on real-world data.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Keywords:
terrain modeling; higher order Delaunay triangulations; numerical examples; algorithms; drainage characteristicsReferences:
| [1] | M. Abellanas, P. Bose, J. Garcìa, F. Hurtado, M. Nicolàs, P.A. Ramos, On properties of higher-order Delaunay graphs with applications, in: Abstracts of the 21st Europ. Workshop on Comput. Geom., 2005, pp. 119-122; M. Abellanas, P. Bose, J. Garcìa, F. Hurtado, M. Nicolàs, P.A. Ramos, On properties of higher-order Delaunay graphs with applications, in: Abstracts of the 21st Europ. Workshop on Comput. Geom., 2005, pp. 119-122 |
| [2] | Agarwal, P. K.; Mustafa, N. H., Independent set of intersection graphs of convex objects in 2D, (Proc. SWAT 2004. Proc. SWAT 2004, Lecture Notes in Computer Science, vol. 3111 (2004), Springer: Springer Berlin), 127-137 · Zbl 1095.68712 |
| [3] | Bern, M.; Edelsbrunner, H.; Eppstein, D.; Mitchell, S.; Tan, T. S., Edge insertion for optimal triangulations, Discrete & Computational Geometry, 10, 1, 47-65 (1993) · Zbl 0780.68108 |
| [4] | Bern, M.; Eppstein, D., Mesh generation and optimal triangulation, (Du, D.-Z.; Hwang, F. K., Computing in Euclidean Geometry. Computing in Euclidean Geometry, Lecture Notes Series on Computing, vol. 4 (1995), World Scientific: World Scientific Singapore), 47-123 |
| [5] | Chew, L. P., Constrained Delaunay triangulations, Algorithmica, 4, 97-108 (1989) · Zbl 0664.68042 |
| [6] | M. de Berg, P. Bose, K. Dobrint, M. van Kreveld, M. Overmars, M. de Groot, T. Roos, J. Snoeyink, S. Yu, The complexity of rivers in triangulated terrains, in: Proc. 8th Canad. Conf. Comput. Geom., 1996, pp. 325-330; M. de Berg, P. Bose, K. Dobrint, M. van Kreveld, M. Overmars, M. de Groot, T. Roos, J. Snoeyink, S. Yu, The complexity of rivers in triangulated terrains, in: Proc. 8th Canad. Conf. Comput. Geom., 1996, pp. 325-330 |
| [7] | A.U. Frank, B. Palmer, V.B. Robinson, Formal methods for the accurate definition of some fundamental terms in physical geography, in: Proc. 2nd Int. Symp. on Spatial Data Handling, 1986, pp. 583-599; A.U. Frank, B. Palmer, V.B. Robinson, Formal methods for the accurate definition of some fundamental terms in physical geography, in: Proc. 2nd Int. Symp. on Spatial Data Handling, 1986, pp. 583-599 |
| [8] | Gudmundsson, J.; Hammar, M.; van Kreveld, M., Higher order Delaunay triangulations, Computational Geometry: Theory and Applications, 23, 85-98 (2002) · Zbl 1005.65020 |
| [9] | Gudmundsson, J.; Haverkort, H.; van Kreveld, M., Constrained higher order Delaunay triangulations, Computational Geometry: Theory and Applications, 30, 271-277 (2005) · Zbl 1071.65020 |
| [10] | M.F. Hutchinson, Calculation of hydrologically sound digital elevation models, in: Proc. 3th Int. Symp. on Spatial Data Handling, 1988, pp. 117-133; M.F. Hutchinson, Calculation of hydrologically sound digital elevation models, in: Proc. 3th Int. Symp. on Spatial Data Handling, 1988, pp. 117-133 |
| [11] | S.K. Jenson, C.M. Trautwein, Methods and applications in surface depression analysis, in: Proc. Auto-Carto 8, 1987, pp. 137-144; S.K. Jenson, C.M. Trautwein, Methods and applications in surface depression analysis, in: Proc. Auto-Carto 8, 1987, pp. 137-144 |
| [12] | Liu, Y.; Snoeyink, J., Flooding triangulated terrain, (Fisher, P. F., Developments in Spatial Data Handling, Proc. 11th Int. Symp. (2004), Springer: Springer Berlin), 137-148 |
| [13] | M. McAllister, J. Snoeyink, Extracting consistent watersheds from digital river and elevation data, in: Proc. ASPRS/ACSM Annu. Conf., 1999; M. McAllister, J. Snoeyink, Extracting consistent watersheds from digital river and elevation data, in: Proc. ASPRS/ACSM Annu. Conf., 1999 |
| [14] | Mitchell, C., Terrain Evaluation (1991), Longman: Longman Harlow |
| [15] | E.A. Ramos, On range reporting, ray shooting and \(k\); E.A. Ramos, On range reporting, ray shooting and \(k\) |
| [16] | B. Schneider, Geomorphologically sound reconstruction of digital terrain surfaces from contours, in: T.K. Poiker, N. Chrisman (Eds.), Proc. 8th Int. Symp. on Spatial Data Handling, 1998, pp. 657-667; B. Schneider, Geomorphologically sound reconstruction of digital terrain surfaces from contours, in: T.K. Poiker, N. Chrisman (Eds.), Proc. 8th Int. Symp. on Spatial Data Handling, 1998, pp. 657-667 |
| [17] | D.M. Theobald, M.F. Goodchild, Artifacts of TIN-based surface flow modelling, in: Proc. GIS/LIS, 1990, pp. 955-964; D.M. Theobald, M.F. Goodchild, Artifacts of TIN-based surface flow modelling, in: Proc. GIS/LIS, 1990, pp. 955-964 |
| [18] | Tucker, G. E.; Lancaster, S. T.; Gasparini, N. M.; Bras, R. L.; Rybarczyk, S. M., An object-oriented framework for distributed hydrologic and geomorphic modeling using triangulated irregular networks, Computers and Geosciences, 27, 959-973 (2001) |
| [19] | S. Yu, M. van Kreveld, J. Snoeyink, Drainage queries in TINs: from local to global and back again, in: M.J. Kraak, M. Molenaar (Eds.), Advances in GIS research II: Proc. of the 7th Int. Symp. on Spatial Data Handling, 1997, pp. 829-842; S. Yu, M. van Kreveld, J. Snoeyink, Drainage queries in TINs: from local to global and back again, in: M.J. Kraak, M. Molenaar (Eds.), Advances in GIS research II: Proc. of the 7th Int. Symp. on Spatial Data Handling, 1997, pp. 829-842 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
