Quickly find and render terrain above a given elevation

Question

Given an elevation map consisting of lat/lon/elevation pairs, what is the fastest way to find all points above a given elevation level (or better yet, just the the 2D concave hull)?

I'm working on a GIS app where I need to render an overlay on top of a map to visually indicate regions that are of higher elevation; it's determining this polygon/region that has me stumped (for now). I have a simple array of lat/lon/elevation pairs (more specifically, the GTOPO30 DEM files), but I'm free to transform that into any data structure that you would suggest.

We've been pointed toward Triangulated Irregular Networks (TINs), but I'm not sure how to efficiently query that data once we've generated the TIN. I wouldn't be surprised if our problem could be solved similarly to how one would generate a contour map, but I don't have any experience with it. Any suggestions would be awesome.

Answer 1

It sounds like you're attempting to create a polygonal representation of the boundary of the high land.

If you're working with raster data (sampled on a rectangular grid), try this.

Think of your grid as an assembly of right triangles.

Let's say you have a 3x3 grid of points

• a b c
• d e f
• g h k

Your triangles are:

• abd part of the rectangle abed
• bde the other part of the rectangle abed
• bef part of the rectangle bcfe
• cef the other part of the rectangle bcfe
• dge ... and so on

Your algorithm has these steps.

1. Build a list of triangles that are above the elevation threshold.

2. Take the union of these triangles to make a polygonal area.

3. Determine the boundary of the polygon.

4. If necessary, smooth the polygon boundary to make your layer look ok when displayed.

If you're trying to generate good looking contour lines, step 4 is very hard to to right.

Step 1 is the key to this problem.

For each triangle, if all three vertices are above the threshold, include the whole triangle in your list. If all are below, forget about the triangle. If some vertices are above and others below, split your triangle into three by adding new vertices that lie precisely on the elevation line (by interpolating elevation). Include the one or two of those new triangles in your highland list.

For the rest of the steps you'll need a decent 2d geometry processing library.

If your points are not on a regular grid, start by using the Delaunay algorithm (which you can look up) to organize your pointss in into triangles. Then follow the same algorith I mentioned above. Warning. This is going to look kind of sketchy if you don't have many points.