#### Archived

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

# How to determin whether a point is in triangle or not

## Recommended Posts

lythm    203
Hello: How can I determin if a point is within a triangle.

##### Share on other sites
Karg    133
(only if in 3D) You need to find if the point is on the plane spaned by the triangle. Distance of the point to the plane == 0

(both 2D and 3D)Then see if it is on the "correct" side of each of the edges of the triangle. Distance of the point from each line has the same sign.
The sign you are looking for (+ or -) depends on which way you use the endpoints to create the lines.

karg

[edited by - Karg on May 24, 2004 12:26:13 AM]

##### Share on other sites
Yann L    1802
Code:
//----------------------------------------------------------------------------// CHECKS IF 2D POINT P IS IN TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT//   Given a triangle ABC and a point P, determines if P is inside//   of ABC (regardless of vertex ordering - CCW or CW). 2D version only, but//   this handles the 3D case if appropriately projected to the XY, YZ, or XZ//   planes (by dropping corresponding component; i.e. drop Z in XY projection).//----------------------------------------------------------------------------int Pt2dInTri(Vect2d A, Vect2d B, Vect2d C, Vect2d P){	// FIRST CHECK THE SIGN OF THE Z-COMPONENT OF THE NORMAL BY CALCULATING	// THE CROSS-PRODUCT (ABxBC). THIS WILL DETERMINE THE ORDERING OF THE	// VERTICES. IF NEGATIVE, VERTICES ARE CLOCKWISE ORDER; OTHERWISE CCW.	// THEN EVALUATE SIGN OF Z-COMPONENTS FOR ABxAP, BCxBP, and CAxCP TO	// DETERMINE IF P IS IN "INSIDE" HALF-SPACE FOR EACH EDGE IN TURN ("INSIDE"	// IS DETERMINED BY SIGN OF Z OF NORMAL (VERTEX ORDERING).	// NOTE: FULL CROSS-PRODS ARE NOT REQUIRED; ONLY THE Z-COMPONENTS	Vect2d dAB=B-A, dBC=C-B;  // "REPEATS"	if ((dAB.x*dBC.y-dAB.y*dBC.x) < 0) // CW	{		if (dAB.x*(P.y-A.y) >= dAB.y*(P.x-A.x)) return(0);           // ABxAP		if (dBC.x*(P.y-B.y) >= dBC.y*(P.x-B.x)) return(0);           // BCxBP		if ((A.x-C.x)*(P.y-C.y) >= (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP	}	else // CCW	{		if (dAB.x*(P.y-A.y) < dAB.y*(P.x-A.x)) return(0);           // ABxAP		if (dBC.x*(P.y-B.y) < dBC.y*(P.x-B.x)) return(0);           // BCxBP		if ((A.x-C.x)*(P.y-C.y) < (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP	}	return(1); // "INSIDE" EACH EDGE''S IN-HALF-SPACE (PT P IS INSIDE TRIANGLE)	};//----------------------------------------------------------------------------// CHECKS IF 3D POINT P IS IN 3D TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT.// USES 2D VERSION AFTER PROJECTED SINCE THE 3D TRIANGLE IS PROJECTED ON ONE OF // THE PLANES FORMED BY THE PRINCIPAL AXES (XY, YZ, and XZ). N=Normal//---------------------------------------------------------------------------- int Pt3dInTri(Vect3d A, Vect3d B, Vect3d C, Vect3d P, Vect3d N){  // DETERMINE LARGEST COMPONENT OF NORMAL (magnitude, since we want the largest projection)  N.x=ABS(N.x); N.y=ABS(N.y); N.z=ABS(N.z);    // PROJECT ONTO PLANE WHERE LARGEST COMPONENT IS SET TO ZERO  if (N.x>=N.y && N.x>N.z)     // X IS LARGEST SO PROJECT ONTO YZ-PLANE    return( Pt2dInTri(Vect2d(A.y,A.z),Vect2d(B.y,B.z),Vect2d(C.y,C.z),Vect2d(P.y,P.z)) );	else if (N.y>N.x && N.y>N.z) // Y IS LARGEST SO PROJECT ONTO XZ-PLANE    return( Pt2dInTri(Vect2d(A.x,A.z),Vect2d(B.x,B.z),Vect2d(C.x,C.z),Vect2d(P.x,P.z)) );  else                         // Z IS LARGEST SO PROJECT ONTO XY-PLANE    return( Pt2dInTri(Vect2d(A.x,A.y),Vect2d(B.x,B.y),Vect2d(C.x,C.y),Vect2d(P.x,P.y)) );};

Found that somewhere on the net a long time ago, I don''t remember where. I fixed two little bugs in the original code, the modified one above works very well.

##### Share on other sites
jaba    122
Very interesting code!!!
In Pt3dInTri is not necessary to calculate the distance from point to the plane?

##### Share on other sites
lythm    203
Karg:
Thanks.
Yann L:
Thanks for your code. I never thought it could be solved in that clean neat way.

##### Share on other sites
sckoobs    157
Check this out: http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

I use the 2d Even-Odd method for my collision detection algorithm in my asteroids clone, very straightforward and efficient - no cross products and it doesn''t matter in what order you feed the vertices in.

##### Share on other sites
Yann L    1802
quote:
Original post by jaba
In Pt3dInTri is not necessary to calculate the distance from point to the plane?

The distance is assumed to be 0, ie. the point is assumed to lie on the triangle''s surface (or very near to it, within some epsilon). If it doesn''t, you need to project it along the face normal, onto the surface.

##### Share on other sites
Just out of curiosity, ever heard of barycentric space? If you take the forulas down far enough it doesn''t involve planes and can be quick even without precomputation.
Look it up, its fun

--------------------------------------------------------
Life would be so much easier if we could just get the source code.

##### Share on other sites
jaba    122
quote:
Original post by Yann L
quote:
Original post by jaba
In Pt3dInTri is not necessary to calculate the distance from point to the plane?

The distance is assumed to be 0, ie. the point is assumed to lie on the triangle's surface (or very near to it, within some epsilon). If it doesn't, you need to project it along the face normal, onto the surface.

Sorry, I don't understand

The blue point(projected) is within the blue triangle(projected) but it isn't within the red triangle. First you must check if the point is on the plane of the triangle and then check if it is
within the projected triangle. Sorry I am very stupid, can you explain me please?

[edited by - jaba on May 25, 2004 4:27:54 PM]

##### Share on other sites
Karg    133
The posted code assumes that the point is on the same plane as the triangle. If that isn''t a safe assumption for you case, then you have to test if the absolute distance of the point from the plane is within some small value (almost 0).
Find a plane equation from 3 points (ax+by+cz+d form):
Given: Point3D p0, Point3D p1, Point3D p2,
a = p0.y *(p1.z - p2.z) + p1.y *(p2.z - p0.z) + p2.y *(p0.z - p1.z);
b = p0.z *(p1.x - p2.x) + p1.z *(p2.x - p0.x) + p2.z *(p0.x - p1.x);
c = p0.x *(p1.y - p2.y) + p1.x *(p2.y - p0.y) + p2.x *(p0.y - p1.y);
d = -(p0.x *(p1.y *p2.z - p2.y *p1.z) + p1.x *(p2.y *p0.z - p0.y *p2.z) + p2.x *(p0.y *p1.z - p1.y *p0.z));

Then plug in the test point''s coordinates for x, y, and z. If the absolute value of the result is within some small value, then it is on the plane. Then continue with the other test.

karg

jaba    122
Ok!!, thanks

##### Share on other sites
motote    122
Here is a method I develop some years ago... is more efficient since it''s only make 4 mults.

Hi hope it still works

This test if point (p) is inside triangle (abc).

bool pointInside(point2D a, point2D b, point2D c, point2D p){  float sign1, sign2;  if ((a.x <= p.x) && (p.x <= c.x))  {   sign2 = (p.x - a.x) * (c.y - a.y) - (p.y - a.y) * (c.x - a.x);   if ((p.x < b.x) || (b.x == c.x))    sign1 = (p.x - a.x) * (b.y - a.y) - (p.y - a.y) * (b.x - a.x);   else    sign1 = (p.y - c.y) * (b.x - c.x) - (p.x - c.x) * (b.y - c.y);      if (((sign1 >= 0) && (sign2 <= 0)) || ((sign1 <= 0) && (sign2 >= 0)))    return true;  }  return false;}