i have the following equation for collision detection distance=(d+p*n)(n*n); if(distance<32) collides now the problem i am thinking about is how to detect if a point in inside a triangle triangle ABC i thought about calculating the angle between ac-ap,ap-ab,.... and that for each angle and then check if the sum of all of them is -1==180° the sum of the inner angles of a triangle but i figured that this would be very time consuming in high polygon environments so is there a better and faster way to do a point-in-triangle test?

your triangle is defined by 3 lines : you just have to compute on which side of each line your point is.

lets for example take the line (a b) : p is in the "good" side of this line if (xb - xa)*(yp - ya) - (yb - ya)*(xp*xa) > 0

if the point p is also in the good side of line (b c)
and line (c a) , then p is in the triangle

hope this help,

Tang

Read the forum FAQ.



Wow, I had given up hope of ever saying this in this forum

Cédric

em can t it be you posted in the wrong thread
the faq doesn t seem to content anything concerning my question

quote:

---

Original post by Basiror
now the problem i am thinking about is how to detect if a point in inside a triangle

---

quote:

---

Forum FAQ:
10. How can I determine if a point lies within the interior of a 2D polygon?

Refer to the following web page, which has a comprehensive discussion of the subject:

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

This topic has been discussed since the math & physics forum began on gamedev.net, but I am not including links to any of the threads since I believe the linked website provides a nice summary of a variety of appropriate algorithms.

---

oh you were talking about this faq

lets say you have a polygon ABCDEFG

and a point P

PA=A-P
d=-PA
now you check if the line
x=P+s*d intersects one edge of the polygon

Hmmm... Yes, that should work. You don''t have to check if it intersects the two edges adjacent to A. In a triangle, this reduces to one line-edge intersection.

Cédric

i don t do it with triangles then the edge method is faster

I believe using cross products would be better than making line intersections.

Construct 3 vectors from the points of the triangle that all point in either clockwise or counter clockwise direction. I''ll just call the points p,q,r and the vectors u,v,w.

Triangle = { p,q,r }
u = q-p;
v = r-q;
w = p-r;

Now, we have a point that we wish to know if it is inside of the triangle. Lets call it x (gotta love that variable, its used EVERYWHERE). So now we will construct 3 more vectors using this point and a corner of the triangle. These new vectors will be px, qx, rx;

px = x-p;
qx = x-q;
rx = x-r;

Now according to whether you are using the right-hand or the lefthand rule the vector produced when you cross product the two vectors coming from each point they should either point behind the triangle perpendicularly, or in front. These vectors will be called y0,y1,y2.

y0 = u cross px;
y1 = v cross qx;
y2 = w cross rx;

Now, the point is inside of the rectangle if all y0, y1, y2 have positive z coordinates or all are negative z coordinates (in the case of 2D triangles). In the case of 3D triangles use the dot product on the y0, y1, y2 vectors. If all three dot products are positive, or all are negative, then the point is in the triangle.

Hope this helps.

For convex polygons, there''s also the angle method (that''s not the formal name, I just made it up ).

Basically, if a point X is inside a convex polygon, the sum of all the angles between any two adjacent points on the polygon and point X will add up to 360. So what you do is create a vector between each point on the polygon and point X. Take the dot product between all adjacent vectors, use it to find the angle, and add it to a total. If when you finish the total is 360 (or at least really close since we''re working with floats), then it''s inside the polygon.