## Visibility and Terrain Labeling (Excerpt)

By

Andrew Shapira

A Thesis Submitted To the Graduate

Faculty of Rensselaer Polytechnic Institute

in Partial Fulfillment of the

Requirements for the Degree of

MASTER OF SCIENCE

Approved: George Nagy, Thesis Advisor

Rensselaer Polytechnic Institute

Troy, New York

May, 1990

**Note – **this web page does not include the complete thesis contents.
This page includes only some front matter, the abstract, table of contents, and introduction. The original `troff`

document source of the complete thesis has been lost. Only printed copies are known.

### Contents

List of Tables

List of Figures

Acknowledgement

Abstract

1. Introduction

2 Literature Review

2.1 Visibility

2.2 Landform Terminology

2.3 Terrain Processing

2.4 Skeletons

2.5 Finite Binary Patterns

2.6 Rational Arithmetic

3 Terrain Visibility

3.1 Introduction

3.2 Theory

3.2.1 Terminology

3.2.2 Terrain Models

3.2.3 Discrete Visibility

3.2.4 Properties of Visibility

3.2.4.1 Constraints

3.2.4.2 Finite Binary Patterns

3.3 Algorithms

3.3.1 Constructing a 2-d Terrain to Match a Matrix

3.3.2 Eliminating Dependence on Viewpoint Position

3.3.3 Fast Line-Grid Intersection

3.4 Discussion

3.4.1 Digital Terrain Data

3.4.2 `Landscope` Implementation Details

3.4.2.1 Overview

3.4.2.2 Terrain-Related Issues

3.4.2.3 Integer Arithmetic

3.4.2.4 Matrix Mode

3.4.2.5 Count Mode

3.4.2.6 Last Horizon Mode

3.4.2.7 Last Horizon Geometry

3.4.2.8 Software Development

3.4.2.9 Theoretical Performance

3.4.2.10 Actual Performance

3.4.3 Dependence on Viewpoint Position

3.4.4 Terrain Sequences

4 Terrain Labeling

4.1 Introduction

4.2 Ridge Labeling Algorithm

4.2.1 Introduction

4.2.2 Defining Ridges and Ridge Structures

4.2.3 Terminology

4.2.4 Outline of Labeling Algorithm

4.2.5 Stage 1 (Binary Image)

4.2.6 Stage 2 (Expansion / Skeletonization)

4.2.7 Stage 3 (Ridge Finding)

4.2.8 Stage 4 (Ridge Ordering)

4.3 Discussion

4.3.1 Introduction

4.3.2 Predicted Ridge Properties

4.3.3 Experiment Description

4.3.4 Statistical Evaluation

4.3.5 Experiment Analysis

4.3.6 Conclusion

5 Path Problems

5.1 Introduction

5.2 Theory

5.2.1 Introduction

5.2.2 Path Definition

5.2.3 Physical Path Length

5.2.4 Formal Problem Statements

5.3 Algorithms

5.3.1 Path Algorithm

5.3.2 Scenic Path Problem Analysis

5.4 Discussion

5.4.1 Introduction

5.4.2 Examples

5.4.2.1 Scenic Boat Path on Lake Champlain

5.4.2.2 Scenic Path Near Mt. Marcy

5.4.2.3 Line of Sight Path Near Mt. Marcy

5.4.2.4 Hidden Path 1

5.4.2.5 Hidden Path 2

5.4.3 Conclusion

6 Open Problems

6.1 Visibility Sets

6.2 Visibility Matrices

6.3 Fractional Visibility

6.4 Sunlight Distribution

6.5 Terrain Sequences

6.6 Terrain Labeling

7 Conclusion

8 Literature Cited

### Abstract

The `Landscope` program computes surface visibility information
in the form of pairwise boolean visibility values for selected data
points.
The program uses integer arithmetic to efficiently and robustly
compute visibility functions within a gridded terrain model that
allows only integer coordinates.
A fast line-grid intersection algorithm forms the basis for this
computation.

One `Landscope` computation analyzes terrain edges that
block visibility.
This computation is used as the input to a ridge-finding algorithm
that is based on image processing operations such as expansion,
skeletonization, and the distance transform.
The ridge-finding process is illustrated by superimposing computed
ridges onto elevation and visibility data; the results are assessed
by comparing actual and predicted statistical properties.
Three areas are tested; each consists of 500 by 500 data points
taken from a 1201 by 1201 United States Geological Survey
digital elevation model of the Lake Champlain region of
New York and Vermont.

`Landscope` output is also used to determine shortest paths
that are least or most visible from a point or region.
The method applies Dijkstra’s shortest-path algorithm to
feasible regions determined from visibility criteria.
Superimposing the paths onto elevation data reveals that the
paths would be difficult or impossible to obtain by inspection.

A theoretical analysis of visibility along a line of sight yields some constraints on pairwise visibility relations for points on the line, an algorithm for constructing terrain models that meet visibility constraints, and a procedure for reducing the dependence of visible area upon a viewpoint’s position within a finite terrain. Also investigated is a phenomenon similar to the convergence of arithmetic sequences that results from applying a visibility operator to terrain models.

Several new visibility-related questions to which answers were not found are formulated.

### Chapter 1 – Introduction

People who use terrain maps, such as hikers, hunters, skier, other outdoor sportsmen, developers, and military personnel, are also interested in visibility. This common interest in terrain maps and visibility, when considered along with some intuitive ideas about landforms and visibility, suggests that visibility considerations may aid terrain labeling. The approach taken in this thesis is to use only visibility information to label terrain. This excludes factors typically used for terrain labeling such as elevation, vegetation, and climate information.

Although here the visibility information is derived from elevation data, the labeling in this thesis does not depend on having elevation data available. (However, elevation data is used to evaluate the success of the terrain labeling algorithm.)

In addition to terrain labeling, this thesis also contains visibility-related theoretical results, purely visibility-based experiments, and the solution of path problems. These path problems involve finding a path that satisfies some visibility constraint, such as, “each point along the path must be invisible to a specified set of points.”

Throughout the thesis, actual terrain data was used for the experiments. The data consists of a 1.4 million point data set obtained from the United States Geological Survey.

A sizable amount of software was developed.
All software development was done using the UNIX operating system.
Three programs account for most of the approximately 800 lines of
C code produced.
A program called `Landscope` performs visibility calculations
on a gridded terrain.
Another program, `Landmark`, filters `Landscope` output
to produce a hierarchical labeling of ridges.
Finally, the `Landway` program takes `Landscope` output
and solves path problems.

The thesis is organized as follows.
The literature review is a synopsis of some prior work in visibility
and terrain labeling.
Following the literature review are the three major chapters.
The first discusses visibility itself; it covers some terminology
used throughout the thesis as well as some visibility theorems and
a description of `Landscope`.
The following chapter consists of the development of a
ridge-labeling algorithm, and several experiments to test
the algorithm.
The section describing the experiments has by far the most figures
of any section in the thesis.
The next chapter parallels the previous chapter in that it develops
a path-finding algorithm and some experiments to test the algorithm.
After the three major chapters is a chapter that collects some
open problems in one place and suggests areas for future work,
and the conclusion.