#### Archived

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

# Point in triangle test.

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

## 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 on other sites

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 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 on other sites
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 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 polygonbool 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

Thanks

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 23
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631768
• Total Posts
3002242
×