How to find delaunay triangulation facets containing the given points

Question

I have plotted n random points (the black points) and used delaunay triangulation, now I want to interpolate m random evaluation points (the red points) so I need to calculate which triangle the evaluation point is inside.

What is the approach for calculating the vertices of the triangle for each point?

Answer 1

For a given triangle, ABC, a point is inside the triangle if it is on the same side of line AB as point C is, on the same side of line BC as point A is, and on the same side of line AC as point B is. You can pre-optimize this check for each triangle and check them all until you find the triangle(s) it is in. See this page for more details.

To save computation, you can compute the minimum and maximum X and Y coordinates of the points for each triangle. If the X and Y coordinates of a point are not within the minimum and maximum values, you can immediately skip checking that triangle. The point cannot be inside it if it isn't inside the rectangle that bounds the triangle.