6
$\begingroup$

Planet elevation maps can be quite big, zooming in/out can be quite costly.

I wonder if there is a most efficient data-structure used to store elevation maps such as quad-trees or any tree-based structure that will make appear details of the planet surface only when a certain level of details is required (and not before) with a fast access to the data.

$\endgroup$
  • 1
    $\begingroup$ We could do with a little more information here, I've leaned more towards file storage. If you're looking for an in memory data structure some sort of tree has got to be the way to go... $\endgroup$ – Liath Sep 22 '14 at 12:58
  • 3
    $\begingroup$ While the question itself may be valid, I don't see how it relates to worldbuilding and have voted to close it as off topic for that reason. While software recommendation questions may be on topic, this question is not one I would expect a worldbuilding expert to be able to answer. I imagine it might be on topic on Software Engineering however, since it is about the "white board" design stage of software development. $\endgroup$ – a CVn Sep 23 '14 at 11:28
  • 1
    $\begingroup$ Discussion about specific algorithms or data-structures for programming a World building software seems to be valid to me. Getting rid of this kind of questions will reduce drastically the scope of this site. $\endgroup$ – perror Sep 23 '14 at 11:51
  • 2
    $\begingroup$ I say that since software recommendations are on-topic, this question should be reopened, despite what @MichaelKjörling wrote above. If you agree, and have 500+ rep, vote to reopen! $\endgroup$ – Shokhet Nov 10 '14 at 2:22
  • 3
    $\begingroup$ @Shokhet I posted a Worldbuilding Meta question about this: Are questions about how to develop worldbuilding software on topic?. Please make your case there. (My personal opinion remains that this type of question is off topic on this site.) $\endgroup$ – a CVn Nov 10 '14 at 7:42
8
$\begingroup$

A hierarchical triangulated irregular network (HTIN) is probably what you are after.

A TIN consists of a delauny triangulation over a set of point samples which are distributed based on the frequency of the surface being modelled. Where the surface varies rapidly, the points are dense, and where the surface does not vary, the points are sparse.

In a hierarchical TIN, the points and their triangulation incorporate an order of precedence and a spatial index so that sections of the triangulation can be extracted at specific levels of detail.

$\endgroup$
  • $\begingroup$ I'm afraid my familiarity with the specific details of HTIN algorithms is lacking so you'll have to do some digging through academic papers for details. I've worked with some related algorithms for stipple generation but not HTINs themselves. $\endgroup$ – smithkm Sep 23 '14 at 3:02
5
$\begingroup$

There are two common ways to store elevation data, the first is by point the second is by contour.

Storing a selection of points suffers because you're limited by the granularity of your data, if you only hold an elevation each metre of surface area you have to interpolate the distance in between. You also end up with a lot of redundant data (after all large portions of land are effectively flat).

If you look at almost any good mountaineering map you'll notice that height is not indicated by a sequence of dots in a grid. It's represented by contours, these lines (of varying size and shape circles encircle peaks and mountains. As you can imagine it's a lot more efficient to store a line of coordinates which are at the same height than every point on the globe.

In terms of actual data structures I would suggest the following:

<contours>
  <contour height="123">
    <point lng="53.2852" lat="-3.5788" />
    <point lng="53.2952" lat="-3.5288" />
  </contour>
</contours>

When your application is passed a point it should determine which is the innermost contour it lies within (perhaps add a ParentContourID to help?). That will be the height of your point (or you can interpolate from the nearest two).

$\endgroup$
  • $\begingroup$ Now I'm grumpy, I was aiming for the Lake District with those coordinates, hit North Wales instead. Not bad from memory though! $\endgroup$ – Liath Sep 22 '14 at 12:57
  • $\begingroup$ Contours are used on maps because they are easy for humans to interpret, but they are quite hard to interpolate effectively. That's why DEMs are based on points, either regular sets as raster DEMS, or irregular points in a TIN. In any any modern map with contours, those contours are going to be derived from point data of some sort. $\endgroup$ – smithkm Sep 23 '14 at 2:59
  • $\begingroup$ @smithkm I was thinking more from a data storage perspective. Thanks for the additional information about HTINs - really interesting stuff! $\endgroup$ – Liath Sep 23 '14 at 7:13

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