Sign in to follow this  

2d triangle collision

This topic is 4836 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

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 this post


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


Link to post
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 this post


Link to post
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.

thanx in advance!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It sounds like your program is exclusively 2D. In 3D+, normals become _very_ important. if you count your points of your triangle A, B, C and they proceed in a counter-clockwise fashion, your normal is a line that extends from the center of your triangle toward you ( probably ). The actual rule is called Righthand rule - counter clockwise progression, then curl your fingers with A being your edge of palm, B being your first knuckle, C being the tip of your little finger. Now close your fist, extend your thumb, and the tip of your thumb points in the same direction as the normal. Normals are a direction only, they have no position, but they tell you in 3d which direction the triangle is facing.

Share this post


Link to post
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 - vertex2
vector edge2 = vertex1 - vertex3
vector edge3 = vertex2 - vertex1

vector 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 this post


Link to post
Share on other sites
excuse me, one slight correction:


bool pointintri(vector position, vector vertex1, vector vertex2, vector vertex3){

vector edge1 = vertex3 - vertex2
vector edge2 = vertex1 - vertex3
vector edge3 = vertex2 - vertex1

vector 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 this post


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

Thanks in advance!

Share this post


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

Share this post


Link to post
Share on other sites

This topic is 4836 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this