Dealing with nodata

Practical considerations give rise to one more type of flat area, the nodata cells. A nodata cell is a cell in the grid where the elevation was unavailable and which has a special elevation value called the nodata value. Nodata cells inside the terrain receive special treatment: they are considered as nonexistent; they do not have flow-directions and they do not influence the flow of their neighbors. Nodata is also used to fill in the boundary of the terrain (which is irregular) and is different from the edge of the grid (which is rectangular) as illustrated below. This ``ocean'' of nodata acts as a giant sink; all flow is ultimately routed there. This means that edge-nodata does influence the flow of its neighbors. Furthermore, the terrain may contain pockets of nodata values which are isolated from the border (essentially holes in the grid). These pockets do not act as sinks.

A cell is on the border of the grid if it is on the first or last row or column of the grid. For simplicity, we augment the grid with two rows of nodata cells, one just above the first row, and one just below the last row, and with two columns of nodata cells, one just to the left of the first column, and one just to the right of the last column. Thus the borders of the grid are only nodata cells. A nodata cell is on the border of the terrain if and only if (a) it is on the border of the grid, or (b) it is connected to a nodata cell on the border of the grid through a path containing only nodata cells.

[nodata]
Boundary of the terrain.
Data points are white, edge nodata points are black and nodata points in the interior are hatched.

Finding the edge of the terrain can then be expressed as finding connected components in a graph that naturally corresponds to the nodata cells, which has a node for each nodata cell, and an edge between any two nodata cells which are adjacent. This can be done using Scan(N) I/Os.


<laura@cs.duke.edu>
Last modified: Wed Apr 18 12:13:53 2001 by laura.