Jump to content
  • Advertisement
Sign in to follow this  
LordG

Math formula to determine if a point lies inside/outside a 2D triangle

This topic is 5411 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Nevermind, I think I got it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
If A, B and C are your vertices then you can represent the point P as A+(B-A)u+(C-A)v. If u>=0, v>=0 and u+v<=1 then P is in the triangle formed by A, B and C. You can form a 3X3 matrix with columns B-A, C-A and P-A then reduce it to find u and v. If the last row isn't all zeros then P doesn't lie in the plane of A, B and C.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

This topic is 5411 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!