Suppose that you want to send someone a sequence of points that determines a terrain. You'd like to send the most important points first. How do we order points from most to least important? I'm looking for ideas. Here are some to get started:

Quadtree refinement

Start with a box around all points. Find the minimum and maximum heights, and if their difference is below a threshold, output a data point near the center of the box as the representative point.
Otherwise, split the box into smaller boxes, and continue recursively.

As you dial down the threshold value, you will refine this quadtree and output more points in what can be considered an importance order based on height. For more applications of quadtrees as terrain representations, see: * Renato Pajarola, Overview of Quadtree-based Terrain Triangulation and Visualization, UCI-ICS Technical Report No. 02-01, January 2002 http://www.ics.uci.edu/~pajarola/pub/UCI-ICS-02-01.pdf

VIP insertion

VeryImportantPoint insertion heuristics add the point with largest error to an evolving terrain model, often TINs. They produce an importance order, but tend to be very slow, because they constantly re-evalute the importance of all points as they build a more and more accurate terrain model.

Breakline insertion

Ridges of hills determine visibility and are breaklines for drainage. If those applications are important to us, then we should begin with points on ridges and maybe valleys. How do we refine this order?

When people talk about breaklines in GIS they are usually talking about a line across which no interpolation should be performed. For example, curbs, cliffs, and river bottoms often need to have breaklines placed on them. Using breaklines can greatly reduce the number of points necessary to get a good approximation, but currently they are placed manually by surveyors. Perhaps they can be inferred when a linear feature is found. Instead of storing breaklines explicitly, a simplex spline can achieve the same effect by increasing the density of the knot set along the line. So, in choosing knot sets, we need to consider not only the importance of those points, but also the effect that knot-set-density has on the interpolation. (Leo is working on this...)

Importance orders from surveyors/forresters

I have queried the professors in a forrestry department about which features they find the most interesting and which points they are most willing to throw away. I should get some answers from them soon. The first response I got was:

From my perspective, it depends partly on how the points got there. For example, surveyors will take far spread points in areas where the slope is uniform and may have clusters of points where it would be necessary to define a stream or other irregularity. But, if the points were LIDAR or something sort of random...the answer would be different... surveyors definitely DON'T take the convenient points. They carefully select the points they need...

Densely sampling steep slopes is well-known and mathematically justifiable. The insteresting part is that we can consider point sets chosen by surveys as reasonable examples of important point choices. By comparing the points sampled by surveyors to more dense LIDAR data, we can develop heuristics for emulating the point-importance orders surveyors use. While their ordering may not be perfect for a given application, it's a good start on complementing more mathematical definitions of importance.

-- JackSnoeyink - 18 Feb 2005 -- CraigFalls - 03 Mar 2005
to top