Archived

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

Point in triangle test.

This topic is 5775 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 point and a triangle, how do i test the point to see if it lies within the triangle? Thanks. P.S. I tried searching, but the forum search doesn''t work.

Share this post


Link to post
Share on other sites
What exactly are you asking?

A triangle in 2D space as a bounding area with a point in it?

A triangle in 3D space describing a bounding area on a plane?

A triangle in 3D space projected to a 2D space (viewport) as a bounding area?

George D. Filiotis
Are you in support of the ban of Dihydrogen Monoxide? You should be!

Share this post


Link to post
Share on other sites
I am doing a triangle/triangle collision routine in 3D. I am at the point where I have the points where the triangle crosses the plane of the other triangle. I need to check these points to see if they lie within the other triangle, and thus confirm the collision. Thanks for the help.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
i thought about this before, and it seems to me you can test whether a 2d point is in a 2d triangle, by

1) drawing lines from all trianglevertices to the point
2) check if these lines cross the triangle-sides,
if they don''t -> the point is inside, else outside

Ofcourse in your algo you need to find someway of projecting the plane in question to 2d. That''s the hard part I guess...

hope this helps,

Pieter (earx)

Share this post


Link to post
Share on other sites
Here is my algorithm for testing for a 3D point to see if it’s inside the polygon. Note that this assumes the point is coplanar with the polygon. This works with convex as well as concave polygons.

It works by picking the two dominant axis and ignoring the other one. Thus it projects it to 2D. Note you need the normal to the polygon, which you might have lying around…

To the ANSI/ISO/C++ conformation police… Yes, it probably isn’t, but I don’t care.

  
//Returns true if the point is inside the polygon.

//Assumes the point is coplanar with the polygon

bool PointInPoly(point3* pVerts, int nNumVerts, point3& pt3Norm, point3& pt3CoPlanar)
{
int nOffsetA;
int nOffsetB;
point2 pt2Point;
bool bInside = false;

//Do one of three orientations

if(fabs(pt3Norm.x) > 0.5773f) //Use y and z

{
nOffsetA = 1;
nOffsetB = 2;
pt2Point = point2(pt3CoPlanar.y, pt3CoPlanar.z);
}
else if(fabs(pt3Norm.y) > 0.5773f) //Use x and z

{
nOffsetA = 0;
nOffsetB = 2;
pt2Point = point2(pt3CoPlanar.x, pt3CoPlanar.z);
}
else //Use x and y

{
nOffsetA = 0;
nOffsetB = 1;
pt2Point = point2(pt3CoPlanar.x, pt3CoPlanar.y);
}

// Extend a straight line away from the point,

// and count the lines that cut through that extended line

for(int i = 0, j = nNumVerts - 1; i < nNumVerts; j = i++)
{
// Skip lines that begin and end either above or below the point

bool bAZeroY;
bool bBZeroY;

point2 pt2VertA(((float*)&pVerts[i])[nOffsetA], ((float*)&pVerts[i])[nOffsetB]);
point2 pt2VertB(((float*)&pVerts[j])[nOffsetA], ((float*)&pVerts[j])[nOffsetB]);

// Move the vertices so that it''s relative to the origin, not the test point

pt2VertA -= pt2Point;
pt2VertB -= pt2Point;

// Test if the line is either completely above or below the point

if((pt2VertA.y > EPSILON && pt2VertB.y > EPSILON) ||
(pt2VertA.y < -EPSILON && pt2VertB.y < -EPSILON))
continue;

// Test if the line is completely to the left of the origin

if(pt2VertA.x < -EPSILON && pt2VertB.x < -EPSILON)
continue;

bAZeroY = fabs(pt2VertA.y) < EPSILON;
bBZeroY = fabs(pt2VertB.y) < EPSILON;

if(bAZeroY)
{
if(pt2VertA.x > -EPSILON)
bInside ^= 1; // Going through the origin of the line

else if(bBZeroY && pt2VertB.x > -EPSILON)
bInside ^= 1;

continue;
}
else if(bBZeroY)
continue;

// Calculate the point going through y == 0.0f

float fRel = pt2VertA.y / (pt2VertA.y - pt2VertB.y);
float fHitX = pt2VertA.x + (pt2VertB.x - pt2VertA.x) * fRel;

if(fHitX > -EPSILON)
bInside ^= 1;
}

return bInside;
}

SS

Share this post


Link to post
Share on other sites