The Terrain Processing Research Group

Scalable algorithms for realistic terrain processing in Geographic Information Systems (GIS)

Faculty: Laura Toma

Laura Toma Geographic information systems (GIS)---software systems used to handle geodata---are increasingly used in geo-sciences and beyond. As massive amounts of data become available from remote sensing technologies, GIS need algorithms that are designed and optimized for massive data, and are able to run efficiently on any users's desktop. Our goal is to develop such algorithms for fundamental problems on terrains and implement them into open-source modules that can be used by the GIS community. Problems studied include terrain simplification and representation, visibility, and flow.

Infrastructure: We have a grid of HP blades, running Linux and administered by Dj Merrill.

This work is supported by NSF through NSF award no. 0728780.

GIS Fellows Summer 2009 - Bowdoin College
Fellows in Terrain Processing - Summer 2009


Jeremy Fishman '09: Improved Visibility Computation on Massive Grid Terrains
We have developed new algorithms for computing viewsheds (visibility maps) on massive grid terrains.. more...

Mark McGranaghan '10: IO-efficient edge quadtrees
The quadtree is one of the most widely used data structures for spatial data. In this project we have developed a new algorithm for constructing a segment quadtree that works efficiently when the data is very large.. more...

Chris O'Donnell '10: Computing flow on triangulated terrains
We are working on modeling flow and efficiently computing river networks on terrain elevation data. While terrain elevation data is becoming more and more available from remote sensing.. more...

Bob Wei '10: Assessing the accuracy of visibility models
Given a digital elevation model (DEM) of a terrain and a location, one question often asked is: "If I were to be at this location, what would I be able to see?".. more...

Chris O'Donnell '10 Carl Morrissey '09: A library for TINs
The two most commonly used models for terrains are the grid and the TIN (triangulated irregular network): A grid terrain is represented as a matrix of elevation values sampled with a uniform grid from the terrain.. more...

William Richard '10: A fast viewshed module for GRASS open-source GIS
We have developed a new module for the open-source GIS GRASS. The new module, called r.viewshed..more...

Yi Zhuang '10: A simple, practical and scalable approach to map overlay
In this project we have developed an experimental evaluation of the IO-efficient quadtree structures proposed by De Berg, Haverkort, Thite and Toma.. more...

Yi Zhuang '10: Computing visibility on terrains in external memory
In this project we consider the problem of computing visibility on very large grid terrains in external memory.. more...

Older projects

Thomas Hazel '05: Terracost: Computing least-cost-path surfaces on massive grid terrains.

Jonathan Todd '05: I/O-efficient refinement of triangulated terrains


Improved visibility computation on massive grid terrains. Jeremy Fishman, Herman Haverkort and Laura Toma. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2009). To appear. [pdf]

Computing visibility on terrains in external memory. Herman Haverkort, Laura Toma and Yi Zhuang. ACM Journal of Experimental Algorithmics,Volume 13, Article 5, February 2009.

TerraCost: Computing Least-Cost-Path Surfaces for Massive Grid Terrains. Thomas Hazel, Laura Toma, Jan Vahrenhold and Rajiv Wickremesinghe. ACM Journal of Experimental Algorithmics, Volume 12, Article 1.9, June 2008.

I/O-Efficient map overlay and point location in low-density subdivisions. Mark de Berg, Herman Haverkort, Shripad Thite and Laura Toma. In Tokuyama, editors, Proceedings of the 18th Annual International Symposium on Algorithms and Computation (ISAAC 2007), LNCS vol. 4835, pp. 500-511. © Springer-Verlag. [pdf].

I/O-Efficient flow modeling on fat terrains. Mark de Berg, Otfried Cheong, Herman Haverkort, Jung-Gun Lim and Laura Toma. In Frank Dehne, Jˆrg-R¸diger Sack, Norbert Zeh, editors, Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007), LNCS vol. 4619, pp. 239-250. © Springer-Verlag. [pdf]

Computing visibility on terrains in external memory. Herman Haverkort, Laura Toma and Yi Zhuang. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments / Workshop on Analytic Algorithms and Combinatorics (ALENEX/ANALCO 2007).

Terracost: A versatile and scalable approach to computing least-cost-path surfaces for massive grid-based terrains. Thomas Hazel, Laura Toma, Jan Vahrenhold and Rajiv Wickremesinghe. In Proceedings of the 21st ACM Symposium on Applied Computing (SAC 2006), 2006. ACM 2006. © ACM.

Supporting Classes

[csci 350] A computing perspective of GIS:

[csci 340] Spatial data structures:


Summer Research at Bowdoin: Researcher Defines New Terrain in Computing Power
Academic Spotlight: New GIS Lab: Computer Science for the Common Good