Archived

This topic is now archived and is closed to further replies.

Point in a triangle

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

Hi, I have a triangle and a point and I need to know whether the point is inside or outside. I would STRONGLY prefer any solution not using trigoniomery, but I can accept it. I have and idea like this: take the three edges as plane dividers and by each of them divide the plane into two sides, then chceck on whaty side the point lies and if it lies on the right side for all three edges, then it''s in. But not only I have problem learning what side is right (oposite of wrong), I also have problems learning what on what side of the plane the point lies (here again I came up with a solution, where you compute the ratio between delta x and delat y of the edge (aka plane divider) and then between the upper end of the edge (or lower, doesn''t matter) and the point I want. Then by chceking which one is bigger, I''ll learn the side I guess) Thanks for any hints

Share this post


Link to post
Share on other sites
Here's the triginometry you didnt want

The first three parameters are the points in the triangle, and the last point is the extra point. Returns true if the extra point is inside the triangle. You may want to uncomment the comment a few lines into the function, because I forgot why i commented them in the first place.

vector is defined like

struct vector{
float x, y;
};

bool PointInTri( vector A, vector B, vector C, vector Point )
{
vector AB;// = B-A;
vector BC;// = C-B;

AB.x = B.x - A.x;
AB.y = B.y - A.y;
BC.x = C.x - B.x;
BC.y = C.y - B.y;

if( AB.x * BC.y - AB.y * BC.x < 0 )
{
if( AB.x * ( Point.y - A.y ) >= AB.y * ( Point.x - A.x ) ) return( 0 );
if( BC.x * ( Point.y - B.y ) >= BC.y * ( Point.x - B.x ) ) return( 0 );
if( ( A.x - C.x ) * ( Point.y - C.y ) >= ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 );
}
else
{
if( AB.x * ( Point.y - A.y ) < AB.y * ( Point.x - A.x ) ) return( 0 );
if( BC.x * ( Point.y - B.y ) < BC.y * ( Point.x - B.x ) ) return( 0 );
if( ( A.x - C.x ) * ( Point.y - C.y ) < ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 );
}
return( 1 );
}

[edited by - Mulligan on June 26, 2002 1:06:29 PM]

Share this post


Link to post
Share on other sites
Here''s the way most people do it:

You simply have to get the 3 angles made up from the vectors from the point to the 3 triangle vertices. It sounds confusing but it''s really not. Ok, let me explain it a little better:

1. Get the angle between these two vectors
- Point to 1st triangle vertex
- Point to 2nd triangle vertex
2. Get the angle between these two vectors
- Point to 2nd triangle vertex
- Point to 3rd triangle vertex
3. Get the angle between these two vectors
- Point to 3rd triangle vertex
- Point to 1st triangle vertex

4. Add up all the angles. If they equal 360 or greater, then your point falls withing the triangle. Otherwise, if it is less than 360, your point is outside of the triangle.

GameTutorials.com has a good tutorial on this subject in their OpenGL tutorials section. It is in the Line/Polygon intersect tutorial. Hope this helps.

Share this post


Link to post
Share on other sites
quote:
Original post by RegularKid
4. Add up all the angles. If they equal 360 or greater, then your point falls withing the triangle. Otherwise, if it is less than 360, your point is outside of the triangle.



It should equal exactly 360 degrees +- a really small error.

Share this post


Link to post
Share on other sites