Computational Geometry and GIS

Theme

• Experimental Computational Cartography
• Interface between the theoreticians and the computer
• Design then implement algorithms and data structures
  • efficiently
  • on the largest (not toy sized!) datasets
• then
  • observe results and
  • suggest new research problems

Past

Triangulated Irregular Networks

• I designed possibly the first TIN program in GIS, in 1973.
• Now, can easily completely TIN a complete 1201x1201 DEM.

• How does error correlate to number of triangles?
• Is a Delauney triangulation the best?
• Is a constrained triangulation, forcing features to be included, necessary?
• Should we alternate inserting and deleting points?

Terrain Visibility

• viewshed: What points can an observer see?
• Visibility indices: How much area can each possible observer see?

• Compute confidence intervals.

1. Unshaded (): almost certainly visible.
2. Lightly shaded (): probably visible.
3. Darkly shaded (): probably hidden.
4. Black (): almost certainly hidden.

Following are two images:

1. some sample terrain from South Korea, color-coded by elevation, and

2. the visibility indices of every point, colored similarly.

• siting observers: alternate the above 2 programs.
• feature determination
• small relation of height to visibility

Hypsography Compression

Proposal: image processing wavelet compression algorithms work well for elevation.

Yes!

Contour to Elevation Interpolation

• Classic problem
• Can we do better?
• Build on classic idea of using a physical foundation, e.g., heat-flow PDE. W/o mods, that causes artifacts.
• The original contours should be invisible in the result.

3D Connected Components

• Given a 500x500x500 volume of bits
• Scanning a concrete block being stressed to failure
• Find connected components
• Union-find algorithm is 1960-ish, but here
• N=10⁸

Proposed Future Work

Short Term

1. Multiple observers covering a region.

2. Fast graphics cards?

3. Test the largest DEM datasets available.

4. Study other serendipitous questions that will arise.

Medium Term

1. Leverage from array operations tools, like Matlab?

2. Output sensitivity to input?

3. If visibility indices and viewsheds are sensitive to small input perturbations, then

   1. Try to establish error bounds on the output.

   2. Faster and less accurate output when input is inaccurate?

4. Feature recognition: feed into constrained TIN.

Long Term

1. Investigate the general question of the proper representation of terrain elevation data.

2. If using TINs, use triangular splines, not just piecewise multilinear flat triangles.

3. Consider the idea of a conceptually deeper representation, based on the geomorphological forces that created the terrain. Devise a basis set of operators, such as uplift, downcut, etc. Deduce the operators that created the particular terrain under consideration, and store them.

4. Slightly differently, represent the terrain by the features that people would use to describe it. This idea is many decades old. Can we get it to work? The problem is that you can't just say that there is a hill over there, you have to specify the hill in considerable detail, which would seem to take more space than simply listing all the elevations with a grid or TIN.

5. Extend to geological data structures. Plan excavation strategy for open pit mine.

6. The major creative force for terrestrial terrain is water erosion. This does not apply to the moon, Venus, and, to the same extent, to Mars. Therefore those surfaces might be statistically different. What impact, if any, would this have on the speed and output distribution of our algorithms and data structures?

This flow chart shows how the various parts can fit together.