# 2d triangle collision

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

## Recommended Posts

How may I know if a point is inside the lines of a triangle? I find the slope of each line and find a perpendicular slope. Next if the perpindicular slope is positive then the dot is soposed to be on the left side of the intersection of the perpindicular slope and the slope of line on the triangle. I do the same for the next line and then next. If the last vertex is above the 2 vertecies that make the final line(I.E. bottom line) then the slope is multiplyed by -1 to do an opposite check. This works but I get problems when lines on a triangle go up and down or left to right (I.E. slope of 1/0 or perpendicular slopes of -1/0). I did a search on this forum but nothing I could understand. The language Iam using has no vector class or in its help files. Thanx in advance!

##### Share on other sites
I use a vector class. My basic method is as follows:
A triangle has 3 points, a, b, c.
for point A, check that the vector pa lies between ba and ca.
for point B, check that the vector pb lies between ab and cb.
etc.

You said you aren't using a vector class - if you can't write one and your diagonal line checking is working fine, you could just add the 2 straight cases.
if triangle line is horizontal:
if point.y > line.y
internal
else
external

##### Share on other sites
-make sure you have the normals of the triangle

-get the position of the point youre checking relative to the vertices of the triangle.

-take the dotproduct of the normal and this relative position for each edge, if all three outcomes are negative, your point lies inside.

##### Share on other sites
Quote:
 if you can't write one and your diagonal line checking is working fine, you could just add the 2 straight cases.

Thanx,

I got the bugs fixed. I was playing around by moving the mouse, if mouse pointer is in triangle a box turns green else its black. I was playing around with the vertecies of the triangle and found that what I was doing did not work for all triangles.

Quote:
 -make sure you have the normals of the triangle

What is a normal? I don't think I got them.

##### Share on other sites
when i said normals of the triangle, i should have said the normals of the edges of the triangle.

a normal is defined to be the vector peripendicular to a surface in 3D or a line in 2D.

tel me give a pseudocode example of what i was talking about.

bool pointintri(vector position, vector vertex1, vector vertex2, vector vertex3){vector edge1 = vertex3 - vertex2vector edge2 = vertex1 - vertex3vector edge3 = vertex2 - vertex1vector normal1 = cross(edge1)vector normal2 = cross(edge2)vector normal3 = cross(edge3)if ( normal1 . (vertex1 - position) < 0 && normal2 . (vertex2 - position) < 0 && normal3 . (vertex3 - position) < 0) return true}vector cross(vector v){return new vector(v.y,-v.x)}

note that the normals in this code arnt actually normals, since they are not normalized, but the normalization can be taken out since it has zero effect on the outcome of the function and takes quite some time.

##### Share on other sites
At the if statment what does the " . " do?

dot product.

##### Share on other sites
excuse me, one slight correction:

bool pointintri(vector position, vector vertex1, vector vertex2, vector vertex3){vector edge1 = vertex3 - vertex2vector edge2 = vertex1 - vertex3vector edge3 = vertex2 - vertex1vector normal1 = cross(edge1)vector normal2 = cross(edge2)vector normal3 = cross(edge3)if ( normal1 . (vertex2 - position) < 0 && normal2 . (vertex3 - position) < 0 && normal3 . (vertex1 - position) < 0) return true}vector cross(vector v){return new vector(v.y,-v.x)}

and yeah, the . [dot] stands for dotproduct, google its definition and purposes since its a very usefull operator.

##### Share on other sites
sorry for bothering all of you with my problem.

Quote:
 for point A, check that the vector pa lies between ba and ca.for point B, check that the vector pb lies between ab and cb.etc.

I don't think I understand. Do you mean to check if the slope from A to a is between the slope of ba and ca. I can't get it to work properly.

##### Share on other sites
Atlast I got it working :).

I found a very nice tutorial, I don't remember where because I was also playing around with memory and my windows failed to respond.

Anyway the important part of what was stated in the tutorial is to choose a random direction (left or right since that way slope is 0 for fastest perfermance) then count how many interesctions with the triangle/polygon there is. If there is an odd number than the point lies within the triangle if theres an even number then the point goes through the triangle.

if ( intersections & 1){
// odd, point inside
}
else
{
// even point outside
}

the only problem if there is an intersection at a vertex, I forgot how that was resolved.