Archived

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

lythm

How to determin whether a point is in triangle or not

Recommended Posts

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


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


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


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


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


Link to post
Share on other sites
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
http://opengladiator.fateback.com/tri.jpg



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


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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;
}

Share this post


Link to post
Share on other sites