17

I'm looking to do a linear interpolation of a irregularly sampled function z(x,y) based on a Delaunay triangulation. Say I have a hill for which I have obtained a Delaunay triangulation:

Delaunay-triangulated hill

I know the altitude z at each of the triangle vertices (samples). I want the altitude z at an arbitrary point (x,y).

  • How do I tell which triangle contains point (x,y)? Once I know this, I guess it's fairly straightforward to interpolate between the triangle's three vertices.

  • Do you know of a ready-made implementation of this? Perhaps with the interpolation bit included as well? I'm sure there must be an open source implementation of this somewhere out there. I'm especially interested in Java (source or JAR), but any flavour of VB or some other language could be useful as well.

Jean-François Corbett
  • 37,420
  • 30
  • 139
  • 188

6 Answers6

9

You can find the target triangle by walking through the triangulation towards the searched point. This assumes that you can access neighboring triangles in constant time, which is the case if the triangulation is stored in doubly connected edge list or similar structures. The implementation is straightforward because you do not need any additional data structures.

Added details: Let P be the searched point. Take any triangle T0 and a point P0 in T0. If P is in T0 you are finished. Else find the edge E0 of T0 that is crossed by the line P0-P. Go to the neighbor triangle T1 of T over the edge E0 and take a point P1 in T1. Now repeat until the triangle Tn contains P.

Jiri Kriz
  • 9,192
  • 3
  • 29
  • 36
  • D(s,n) < D(s,c) where s is searched point, n is the new point, c is the current point and D is the distance function. – nulvinge Sep 12 '11 at 14:21
  • 3
    Worthy mention: _"This procedure is guaranteed to terminate only in Delaunay triangulations. For arbitrary triangulations it may go into an infinite loop"_ .... _"However, the infinite loop can be broken, for all practical purposes, by introducing randomness when selecting which neighboring simplex to visit next"_ – Steven Jeuris Sep 12 '11 at 14:57
  • @Steven: good comment. Fortunately the walk always terminates in Delanay triangulations and we do not need to bother about any randomness. – Jiri Kriz Sep 12 '11 at 15:09
3

This is not an easy question to answer, and it depends on what performance you require from your lookup, and how much memory you are prepared to trade to get that performance.

If this is a very rare operation, or your number of triangles is small, then you can always iterate through all the triangles. Testing for a triangle containing a point isn't very expensive. You should probably code this first and see if it gives acceptable performance.

If it isn't acceptable, your can try walking through the triangulation - essentially start with a triangle and then find the next one nearest the point you are looking for. This does assume that you have some extra information over a simple list of triangles - specifically that you can find the triangles that use a given vertex (or find a triangle from its neighbouring triangle, which is roughly equivalent in complexity). If you don't have this computed then it is nearly as expensive as finding a point.

If that isn't fast enough, you need to set up some kind of R-Tree. This allows you to find triangles from their locations very quickly, but does need a lot of pre-processing and a substantial amount of memory for the tree.

You may find that the time to compute the pre-processing for each of the second and third methods is more than the time to find the triangles by exhaustive search, if you don't do it often.

DJClayworth
  • 26,349
  • 9
  • 53
  • 79
  • No information about vertices is needed for the walk. The only information needed are the neighbor triangles at the opposite side of each edge. And this is usually available. e.g. if the triangulation is stored in DCEL. – Jiri Kriz Sep 12 '11 at 15:03
  • Yes, technically you;re right. But the information about the neighbour triangles is as large and as complicated as the vertex->triangle map, so the argument is precisely the same. – DJClayworth Sep 12 '11 at 15:08
2

You might use a Delaunay Hierarchy http://hal.inria.fr/inria-00166711 The idea is to take a subset of the points, triangulate it, and have links between vertices between the two layers. The "walk" is then performed in the small triangulation, then one jumps from one layer to the next one, then one continues the walk. This is implemented in the triangulations of CGAL: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_37.10

Andreas Fabri
  • 1,144
  • 6
  • 9
2

My algorithms knowledge is a bit rusty. Instead of my prior answer, you are probably better of using a Voronoi Diagram.

A point location data structure can be built on top of the Voronoi diagram in order to answer nearest neighbor queries, where one wants to find the object that is closest to a given query point. Nearest neighbor queries have numerous applications. For example, one might want to find the nearest hospital, or the most similar object in a database.

I can't help you with the specifics of this, but hopefully this can point you in the right direction.

I'm guessing you could also use an R-tree in which you link to your triangles.

A quick search on google with 'java r-tree' should help you out to find existing libraries.

Steven Jeuris
  • 18,274
  • 9
  • 70
  • 161
1

I found a working implementation here: http://www.cs.bgu.ac.il/~benmoshe/DT/

The find method finds the triangle that contains a given point, and the z method does the planar interpolation.

Unfortunately it's a compiled JAR, so I don't know what the algorithm is, but I sense that it "walks through the triangulation" as suggested by @Jiri and @DJClayworth.

Also unfortunate is the rather unconventional nomenclature used in this JAR. I may end up writing a wrapper class with nicer nomenclature.

Jean-François Corbett
  • 37,420
  • 30
  • 139
  • 188
0

I am new to this but if you were able to reference each 2d triangle, using a hash map where the key is a unique number could you encode that key as say a color in an image. Then draw the triangles with that solid color.

To find the triangle you retrieve the key by decoding the color at the requested position.

There would be a cost when drawing the triangle but the lookup should be fast.

I think the idea could be abstracted to meshes in 3d.

Dave
  • 163
  • 1
  • 9