Locate triangle containing arbitrary point in Delaunay-triangulated surface

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.