What most efficient method to find a that triangle which contains the given point?

Question

Given the triangle with vertices (a,b,c):

        c

      /   \

    /       \

  /           \

 a  -  -  -  -  b

Which is then subdivided into four triangles by halving each of the edges:

              c

            /    \

          /        \

     ca /            \ bc
           _   _   _
      /\              /\

    /    \          /    \

  /        \      /        \

a  -  -  -  - ab  -  -   -   -b

Which results in four triangles (a, ab, ca), (b, bc, ab), (c, ca, bc), (ab, bc, ca).

Now given a point p. How do I determine in which triangle p lies, given that p is within the outer triangle (a, b, c)?

Currently I intend to use ab as the origin. Check whether it is to the left of right of the line "ca - ab" using the perp of "ca - ab" and checking the sign against the dot product of "ab - a" and the perp vector and the vector "p - ab". If it is the same or the dot product is zero then it must be in (a, ab, ca)... Continue with this procedure with the other outer triangles (b, ba, ab) & (c, ca, ba). In the end if it didn't match with these it must be contained within the inner triangle (ab, bc, ca).

Is there a better way to do it?

EDIT

Here is a little more info of the intended application of the algorithm:

I'm using this as a subdivision mask to generate a fine mesh over which I intend to interpolate. Each of the triangles will be subdivided similarly up to a specified depth. I want to determine the triangle (at the maximum depth) within which the point p lies. With this I can evaluate a function at the point p using interpolation over the triangle. There is a class of triangles which is right-angled and they do comprise a significant portion, but they're much easier to work with and this algorithm isn't intended for them.

Answer 1

This is a straightforward "point-in-polygon" test. Some good C implementations are here.

You could test the center triangle (ca-cb-ab) and if the point is not inside that triangle, you can easily deduce which of the other triangles the point must lie in.

Answer 2

• If the point is above ca/bc (i.e. in the top grey triangle) it's easy.

• If the point is left of ca (i.e. in the left grey triangle) it's easy.

• If the point is right of bc (i.e. in the right grey triangle) it's easy.

• If the point is in the middle, all you have to do is determine if the point is above or below the black V.

  You can do that by calulcating the y value of the line for the x value of the point and compare the result to the y value of the point.

  if (y' > (y * x') / x)
  {
      // center triangle
  }
  else
  {
      // right triangle
  }
  

Is this the most efficient method? I don't know.

Answer 3

Seems like triangle abc is fixed and point p varies?

Then you can consider ab to be the x axis and ac to be the y axis and work in those co-ordinates. We can also assume that ab = unit vector along x = e_x and ac = unit vector along y = e_y.

Then point p = (x,y) = x*e_x + y*e_y in that system.

Based on how x, y and x+y compare to 1/2 you can determine where the point lies. Something like:

if (y > 1/2) then c-ca-bc

if (x > 1/2) then b-ab-bc

if (x+y >= 1/2) then ab-bc-ca

else a-ab-ca

In the case abc is not fixed, transforming p into the required co-ordinates should still be a quick operation and the total number of operations with this algorithm will probably be lower than what you have currently. Of course, we can't tell which is better unless you actually try measuring the performance in your scenarios.

Answer 4

Is this an equilateral triangle? If so, then:

Let's say the height of your triangle is H. Use the distance formula to compute the distance from c to p. If d(c,p) < H/2, p is in the top triangle. If d(a,p) < H/2, p is in the left triangle. If d(b,p) < H/2, p is in the right triangle.

If none of the above are true, p is in the center triangle.

If your triangle isn't equilateral, then disregard my answer.