Locate triangle containing arbitrary point in Delaunay-triangulated surface

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:

开发者_如何学Go

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.

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.

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.

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.

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

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.