Locate triangle containing arbitrary point in Delaunay-triangulated surface

Question

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:

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.

Answer 1

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.

Answer 2

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.