Back to search

University of British Columbia

The computational geometry of hydrology data in geographic information systems

Abstract

dc:description

Computational geometry counts geographic information systems (GIS) among its application areas. GIS data sets are large and are related to the Earth's surface by geometric coordinates. These properties mesh with geometry algorithms and their asymptotic analyses. This dissertation investigates the geometry in a specialized set of GIS problems, namely finding river network centrelines and finding watershed boundaries. Our goal is to create robust and consistent algorithms that solve these problems efficiently. When finding river network centrelines, the main issue is the robustness of the algorithm. The medial axis is an excellent centreline for a river or lake, but few robust implementations exist. Moreover, the medial axis uses parabolic segments, which are harder to represent accurately than line segments. We approximate the medial axis with a piecewise-linear structure that we compute with a robust algorithm for point Voronoi diagrams. Our approximation provides estimates of river area and associates the points on the centreline with the nearest river bank points, much like the medial axis. In turn, we use this association to identify opposite points along river banks. When finding watershed boundaries on triangulated terrains, we focus on finding an algorithm that is consistent with the terrain. In previous work, Nelson et al. [66] locate regions that drain to a common location, but their solution can be disconnected in degenerate cases. We propose a vector algorithm whose watersheds are consistent with the assumption on how water flows on the terrain; the algorithm guarantees one polygon per watershed. Our algorithm finds the watershed boundaries for local minima in the terrain in O(n log n + k) worst-case time where n is the number of points that model the terrain and k is the complexity of the watershed boundaries. We apply our solutions for these GIS problems to data in the British Columbia TRIM (Terrain Resource Inventory Mapping) format. For river networks, we find centrelines for the Fraser River in British Columbia and for a subset of its tributaries. We link these centrelines into a single river network. We have used this network to model the migration of salmon. For watersheds, we identify the boundaries of watersheds in the mountains north of Vancouver, British Columbia and compare the boundaries with manually-digitized watersheds of the same region.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1999

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • McAllister, Michael

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/10824

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

McAllister, Michael. The computational geometry of hydrology data in geographic information systems. doctoral thesis, University of British Columbia, 1999. http://hdl.handle.net/2429/10824