onezero

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.