Given a point and a set of triangles, what's would be a fast way to find which triangle the point belongs to?

I'm trying to do a piece-wise affine transform in Python.

I have one image with a set of points hand marked and another set of points where I wish to "move" my current points and the texture between.

This is my understanding of the transformation:

1. Find the delaunay triangulation of the moved points
2. For each pixel in the image, find the corresponding triangle
3. Find the barycentric coordinates of the pixel for the triangle found in 2.

4. Multiply the barycentric coordinates for the pixel in 3 and you have the coordinates of the pixel in the new image.

I ran some tests and I believe my understanding is correct. I have two bottlenecks in my code currently. First, finding out if a point is inside a triangle. For that I am using the algorithm from the wikipedia page.

The second bottleneck, and this is the real problem, is finding out the triangle a point belongs to (hence the title :)) I tried finding the distance from the points to the centers, then ordering the triangles in each iteration by the distance from its center to the point, but that doesn't always work. I believe the problem lies in the fact that I have to use the triangulation of the image I want and not from the image I have.

I figure the displacement of the points/triangles comes into play then, but I'm not sure how.

• I realize this is a 4 year old question, and the original asker's account no longer even exists but... FYI for future googlers: if you are using Python like the original poster, scipy's Delaunay class has a find_simplex method for accomplishing exactly this task. – Chester Jun 8 '15 at 17:47