# Extracting coordinates of a triangulation from DEM data

I'm working on the succinct representation of planar graphs and now I'm trying to obtain some datasets to test my results. I saw that Delaunay triangulations of elevation data can be a good source of datasets.

I downloaded DEM data from USGS elevation data, but now I don't know how to extract the Delaunay triangulation and (most important for me) its underlying planar graph. Is that even possible?

• I'm voting to close this question as off-topic because it is better suited to mathematics stack exchange. – If you do not know- just GIS Jan 20 '16 at 13:44
• Hi, I was expecting some hints about QGis or any other GIS software to obtain the triangulation – José Fuentes Jan 20 '16 at 13:56
• DEM data is usually a rectangular grid of height values. Any triangulation from sampled spot heights is probably long gone. You can always sample the DEM yourself at some set of points and construct a triangulation. – Spacedman Jan 20 '16 at 14:05
• @Spacedman is correct, I am not even sure though you can reverse engineer in this manner. – If you do not know- just GIS Jan 20 '16 at 14:57
• Are you wanting a TIN with a subset of points from the DEM? This outline mentions 3 alternative algorithms: Fowler and Little, VIP and Drop Heuristic. – Kirk Kuykendall Jan 20 '16 at 18:14

The solution proposed by Spacedman is easy to do with GRASS GIS and Python scripting or or OpenJump's "planar graph" command.

1) Generate random points (or specific points) from the DEM and sample elevation at each of these points. (v.random, v.drape)

2) Compute a TIN with the Delaunay algorithm (v.delaunay, 3D)

3) Compute the Planar Graph (with Python here): nodes, arcs and faces

Nodes and Arcs:

Faces

• Seems like it would be better to pick significant points, such as peaks/valleys, at step 1 instead of random points. That way the triangular surface would more closely reflect the DEM. – Kirk Kuykendall Jan 20 '16 at 17:28
• If you want, it is the principle here: extract points from the DEM – gene Jan 20 '16 at 17:42