Hello guys, I'm trying to come up with a mathematical formula to determine if a point is inside a triangle, outside a triangle or on the edge of a triangle. This is a 2D Triangle. Now let's say the triangle is represented with 3 vectors a, b and c in clockwise order. And we'll let the point be p. Does anyone have any clue on how to do this? I was thinking about clipping, but not sure how to represent this mathematically.

Nevermind, I think I got it.

Let me know if the following works for you. It should be practical and will determine if a point P is within a triangle defined by three points that are ordered counter-clockwise, as you required.

Suppose you have the three points A(a1, a2), B(b1, b2) and C(c1,c2), which are ordered counter-clockwise.

Suppose you wish to test whether or not the point P(p1, p2) is within or on the perimeter of the triangle defined by ABC.

Let R = (2(a1^2 + a2^2 + a1*p1 + a2*p2 - b1*p1 - b2*p2) + 4(b1^2 + b2^2) - 6(a1*b1 + a2*b2))*(b1 - a1) / (2(a1^2 + a2^2 + b1^2 + b2^2 - 2a1*b1 - 2a2*b2) + a1.

Let Q = -(p1 - R) / (b2 - a2).

To know whether a point is within the triangle will take a minimum of one test for Q, or a maximum of three tests. If Q is positive for any of the tests, then the point is outside the triangle. If Q is less-than or equal-to zero for all three tests, then the point is within the triangle or on its perimeter.

For the first test, you would use the two points A and B of the triangle. If Q was positive, you would not need to perform any more tests to know that the point P was outside the triangle. If Q was negative for the test with A, B, you would need to make a second test with the points B and C. To do that, you would replace A with B, and B with C in the above equations and then solve for Q. Apply a similar procedure a third time if needed.

First test: A and B.
Second test: B and C.
Third test: C and A.

I hope this helps. If there is a slight error in a sign or something, let me know.

Take care, and good luck.

The plane of ABC is the entire XY-plane. He wants to determine if the point is in a 2D triangle. Taken from your last statement.

Quote:Original post by LilBudyWizer
My mistake, but it still applies. Rather than reducing a matrix you can just use u=(v2.x*v3.y-v2.y*v3.x)/(v1.y*v2.x-v1.x*v2.y) and v=(v1.y*v3.x-v1.x*v3.y)/(v1.y*v2.x-v1.x*v2.y) where v1=B-A, v2=C-A and v3=P-A. Which looking at that you are just finding the intersection of A+V1*u and P-V2*v.

i concur, thats the best way to do it. take note of the common terms you can take out.

Using the original method I wrote above isn't bad since if you calculate a1^2 and b1^2 in the first test and then need to do a second test, you don't need to calculate b1^2 again since it will replace a1^2, etc.

If he has the proper functions, he could do what you guys suggest. That is, basically a change of basis and then a check of the components.

If he has a solver, he would just need to perform a change of basis to the vector AB and AC frame. Then transform the point into that frame and if the components are both greater than 1, than the point is outside the triangle.

I must admit, I am more used to working mathematical problems on paper than solving with a computer.

I still like the method previously. hehe.

The first test would take:
21 multiplications
2 divides
10 additions
9 subtractions

The other tests would have less since some results from the previous could be applied to the next.

lol.

Since this is the math board, here's a more "mathy" description of a way to solve this using Barycentric Coordinates:

http://graphics.cs.ucdavis.edu/GraphicsNotes/Barycentric-Coordinates/Barycentric-Coordinates.html

From http://www.dracat.net/~wyvern/papers/barycentric.doc you can use a simple formula for 2D:
For a triangle <<x1,y1> <x2,y2> <x3,y3>> and some point <x0,y0>:
b0 = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
u = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0
v = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
w = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0

The point <x0,y0> lies inside the triangle iff u,v,w >= 0 (if speed is an issue you can do early rejection and/or multiply by 1/b0 rather than doing those divides)

This is the same as LilBudy's method, just on a silver platter :)

-nohbdy