[Math] Given a point and a set of triangles, what’s would be a fast way to find which triangle the point belongs to

geometryimage processingtrigonometry

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.

Best Answer

Two things:

1) For finding out what triangle a point belongs to, I'd recommend a gridding system - overlay a small (something in the range of 20x20 to 50x50, depending on how many points are in your triangulation) grid on top of your destination triangulation and bin all the triangles into each grid cell they overlap (this should be fairly quick; with the right resolution, many of your triangles will fall into a single cell and most of the rest will only straddle a couple). Then to determine which triangle a point belongs to, figure out which bin the point is in and test only the triangles that overlap that bin. There are other, similar schemes available but this is probably the simplest and it should be more than good enough for what you're doing.

2) Since you don't make it clear which way you're iterating in your description, I want to emphasize that you should be looping over the points in your destination image, not the points in your source image; if you loop over the points in the source image and forward-transform then you may wind up with holes in your destination image; by looping over your destination image and back-transforming to find the corresponding point in the source image, you eliminate this problem. Also, you almost certainly want to do some measure of antialiasing; the easiest thing to do is probably to subsample your destination image and do 4 or 9 samples for each destination pixel.

Related Question