TerraStream: from elevation data to watershed hierarchies

ABSTRACT

We consider the problem of extracting a river network and a watershed hierarchy from a terrain given as a set of irregularly spaced points. We describe TERRASTREAM, a "pipelined" solution that consists of four main stages: construction of a digital elevation model (DEM), hydrological conditioning, extraction of river networks, and construction of a watershed hierarchy. Our approach has several advantages over existing methods. First, we design and implement the pipeline so that each stage is scalable to massive data sets; a single non-scalable stage would create a bottleneck and limit overall scalability. Second, we develop the algorithms in a general framework so that they work for both TIN and grid DEMs. Furthermore, TERRASTREAM is flexible and allows users to choose from various models and parameters, yet our pipeline is designed to reduce (or eliminate) the need for manual intervention between stages.

We have implemented TERRASTREAM and we present experimental results on real elevation point sets, which show that our approach handles massive multi-gigabyte terrain data sets. For example, we can process a data set containing over 300 million points---over 20GB of raw data---in under 26 hours, where most of the time (76%) is spent in the initial CPU-intensive DEM construction stage.

REFERENCES

• 1: P. K. Agarwal, L. Arge, and A. Danner. From point cloud to grid DEM: A scalable approach. In Proc. 12th International Symposium on Spatial Data Handling, pages 771--788. Springer-Verlag, 2006.
• 2: P. K. Agarwal, L. Arge, and K. Yi. I/O-efficient construction of constrained Delaunay triangulations. In Proc. 13th European Symposium on Algorithms, pages 355--366, 2005.
• 3: Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137884]
• 4: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 5: Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 6: L. Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1--24, 2003.
• 7: L. Arge, R. Barve, D. Hutchinson, O. Procopiuc, L. Toma, D. E. Vengroff, and R. Wickremesinghe. TPIE User Manual and Reference (edition 082902). Duke University, 2002.
• 8: Lars Arge , Jeffrey S. Chase , Patrick Halpin , Laura Toma , Jeffrey S. Vitter , Dean Urban , Rajiv Wickremesinghe, Efficient Flow Computation on Massive Grid Terrain Datasets, Geoinformatica, v.7 n.4, p.283-313, December 2003 [doi>10.1023/A:1025526421410]
• 9: L. Arge, A. Danner, H. Haverkort, and N. Zeh. I/O-efficient hierarchical watershed decomposition of grid terrain models. In Proc. 12th International Symposium on Spatial Data Handling, pages 825--844. Springer-Verlag, 2006.
• 10: Lars Arge , Laura Toma , Jeffrey Scott Vitter, I/O-Efficient Algorithms for Problems on Grid-Based Terrains, Journal of Experimental Algorithmics (JEA), 6, p.1-es, 2001 [doi>10.1145/945394.945395]
• 11: L. P. Chew. Constrained Delaunay triangulations. Algorithmica, 4:97--108, 1989.
• 12: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 13: Andrew Danner , Lars Arge , Pankaj K. Agarwal, I/o efficient algorithms and applications in geographic information systems, Duke University, Durham, NC, 2006
• 14: Herbert Edelsbrunner , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Geometry and Topology for Mesh Generation (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
• 15: Herbert Edelsbrunner , John Harer , Afra Zomorodian, Hierarchical morse complexes for piecewise linear 2-manifolds, Proceedings of the seventeenth annual symposium on Computational geometry, p.70-79, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378626]
• 16: H. Edelsbrunner , D. Letscher , A. Zomorodian, Topological persistence and simplification, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.454, November 12-14, 2000
• 17: J. Garbrecht and L. Martz. The assignment of drainage directions over flat surfaces in raster digital elevation models. Journal of Hydrology, 193:204--213, 1997.
• 18: Martin Isenburg , Yuanxin Liu , Jonathan Shewchuk , Jack Snoeyink, Streaming computation of Delaunay triangulations, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 19: M. Isenburg, Y. Liu, J. Shewchuk, J. Snoeyink, and T. Thirion. Generating raster DEM from mass points via TIN streaming. In Proc. 4th International Conference on Geographic Information Science, 2006.
• 20: S. Jenson and J. Domingue. Extracting topographic structure from digital elevation data for geographic information system analysis. Photogrammetric Engineering and Remote Sensing, 54(11):1593--1600, 1988.
• 21: N. L. Lea. An aspect driven kinematic routing algorithm. In Overland Flow: Hydraulics and Erosion Mechanics. Chapman & Hall, New York, 1992.
• 22: L. Mitas and H. Mitasova. Spatial interpolation. In Geographic Information Systems - Principles, Techniques, Management, and Applications. Wiley, New York, 1999. P. A. Longley, M. F. Goodchild, D. J. Maguire, D. W. Rhind (editors).
• 23: H. Mitasova, L. Mitas, and R. S. Harmon. Simultaneous spline interpolation and topographic analysis for lidar elevation data: methods for open source GIS. IEEE Geoscience and Remote Sensing Letters, 2(4):375--379, 2005.
• 24: Markus Neteler , Helena Mitasova, Open Source GIS: A GRASS GIS Approach, Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• 25: North Carolina Flood Mapping Program. http://www.ncfloodmaps.com.
• 26: J. F. O'Callaghan and D. M. Mark. The extraction of drainage networks from digital elevation data. Computer Vision, Graphics and Image Processing, 28:323--344, 1984.
• 27: P. Soille, J. Vogt, and R. Colombo. Carving and adaptive drainage enforcement of grid digital elevation models. Water Resources Research, 39(12):1366--1375, 2003.
• 28: D. Tarboton. A new method for the determination of flow directions and contributing areas in grid digital elevation models. Water Resources Research, 33:309--319, 1997.
• 29: A. Tribe. Automated recognition of valley lines and drainage networks from grid digital elevation models: a review and a new method. Journal of Hydrology, 139:263--293, 1992.
• 30: K. L. Verdin and J. P. Verdin. A topological system for delineation and codification of the Earth's river basins. Journal of Hydrology, 218:1--12, 1999.
• 31: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 32: J. P. Wilson and J. C. Gallant. Terrain Analysis: Principles and Applications. Wiley, New York, NY, 2000.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Experimentation

Keywords:
terrain modeling