Generating realistic terrains with higher-order Delaunay triangulations |
| |
Institution: | Institute of Information and Computing Sciences, Utrecht University, the Netherlands;TU Eindhoven, the Netherlands;NICTA, Australia;Utrecht University, the Netherlands;TU Eindhoven, the Netherlands |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|