View Full Version : Point in Triangle?

TheBlob

12-06-2001, 11:13 AM

Hi!

Well, my problem is the following:

I have a point p(x|y) and three points a,b,c forming a triangle. How can I check, if the point p is in the triangle??

Maybe someone has a good, working function?

Please help!

TheBlob!

Leyder Dylan

12-06-2001, 02:17 PM

Here's a link.

http://www.gametutorials.com/Tutorials/Advanced/OpenGL_Pg2.htm

"Polygon Detection"

It's works !

Yeah !!!!!!!!!!!!!!!

Iceman

12-06-2001, 04:40 PM

I have exactly what u need ...

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~

// Determine if a two dimensional point lies within the confines of a given

// two dimensional triangle.

//

// From Dr. Dobbs Journal, October, 2000

bool IsPointInsideFace(

double pX,

double pY,

double v0x,

double v0y,

double v1x,

double v1y,

double v2x,

double v2y

)

{

double x0, x1, x2, y1, u, v, denom;

x1 = v1x - v0x;

if ( x1 == 0.0 )

{

// Triangle points 0 and 1 have the same X value

// Zero area test - can be removed if triangle is known to be valid

x2 = v2x - v0x;

if ( ( x2 == 0.0 ) &#0124; &#0124;

// Compute u and check bounds

( ( u = (pX - v0x) / x2 ) < 0.0 ) &#0124; &#0124;

( u > 1.0 ) &#0124; &#0124;

// Zero area test - remove if known to be valid

( ( y1 = v1y - v0y ) == 0.0 ) &#0124; &#0124;

// Compute v and check bounds

( ( v = ( (pY - v0y) - u *

( v2y - v0y ) ) / y1 ) < 0.0 ) )

{

// Missed for some reason

return false;

}

}

else

{

// Triangle points 0 and 1 have a different X value

// Compute denom and check for zero area triangle - check

// is not needed if triangle known to be valid.

x2 = v2x - v0x;

y1 = v1y - v0y;

denom = ( v2y - v0y ) * x1 - x2 * y1;

if ( ( denom == 0.0 ) &#0124; &#0124;

// Compute u and check bounds

( ( u = ( (pY - v0y) * x1 - (x0 = pX - v0x) * y1 ) / denom ) < 0.0 ) &#0124; &#0124;

( u > 1.0 ) &#0124; &#0124;

// Compute v & check bounds

( ( v = ( x0 - u * x2 ) / x1 ) < 0.0 ) )

{

// Missed for some reason

return false;

}

}

// Check gamma

if ( u + v > 1.0 )

{

// Outside third edge

return false;

}

return true;

}

I have a simple method :

TEST the point P is in triangle ABC or not

add the area of PAB,PBC,PCA ,if the total is equal to the area of ABC ,then we know the point P is in the triangle ,otherwise is out.

right?

Iceman

12-07-2001, 09:06 AM

Sure, but benchmark it against the above algorithm and I am willing to bet that it looses in terms of raw performance. If you get a chance to do so please post the results here ... thx

Powered by vBulletin® Version 4.2.2 Copyright © 2014 vBulletin Solutions, Inc. All rights reserved.