1

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?

  • 1
    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
  • 1
    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
1

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)

enter image description here

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

enter image description here

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

Nodes and Arcs:

enter image description here

Faces

enter image description here

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.