I saw an algoirthm somewhere that said to take a vertical ray and draw it straight down from the point. (Any direction, actually)

If that ray intersects exactly one of the segments that makes up the triangle, the point is inside.

If the ray exactly intersects a point of the triangle, if the point lies ON a segment, or the ray coincides exactly with a segment, then these are special cases, but most cases are covered by the above.

I'm not sure how well this works in 3D space. The ray you draw would have to lie on the same plane as the triangle.

Just an idea.

I suppose if you wanted to evolve the algorithm for 3D, you could take any arbitrary plane that passes through the point, and if exactly two of the segments intersect the plane, the point is inside. Blah, no, that wouldn't work. Arrgh!


[edited by - Waverider on October 7, 2002 10:23:05 AM]

quote:

---

Original post by Fantasio
Do you know how to use the very useful DotProduct in geometry?

---

No, I do not even know what dot product does.

How I put an image with my message ??

How can I put an image with my message ??

quote:

---

Original post by Fantasio
How I put an image with my message ??

---

I''m not sure what the HTML code is for an image, and actually that may be disabled now due to some destructive individuals who seem to want to attack the site in various ways.

But in theory I think you could just put standard HTML code to link in an image. Now, you do have to host the images on your own public website----gamedev doesn''t provide a way for you to upload and store images on our servers.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

I''ll give my standard link #317 in reply to the original question:

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

bwahhaha
double CWndMain::TriangleArea(double x1, double y1, double x2, double y2, double x3, double y3)
{
return 0.5*abs(x1 * y2 - y1 * x2 + x2 * y3 - x3 * y2 + x3 * y1 - x1 * y3);
}
BOOL CWndMain::InTriangle(double px, double py, double x1, double y1, double x2, double y2, double x3, double y3)
{

double s, s1_2, s1_3, s2_3;

s1_2 = TriangleArea(px, py, x1, y1, x2, y2);
s1_3 = TriangleArea(px, py, x1, y1, x3, y3);
s2_3 = TriangleArea(px, py, x2, y2, x3, y3);

s = TriangleArea(x1, y1, x2, y2, x3, y3);

if(s == s1_2 + s1_3 + s2_3)
{
return true;
}
else
{
return false;
}
}

Killer Eagle Software

[edited by - DevLiquidKnight on October 9, 2002 9:52:58 PM]

Boo Ya Grandma! Just put the vectrs in clockwise order.
for vector, use

typedef struct _VECTOR
{
float x, y, z;
} vector;

int PointInTriangle( vector A, vector B, vector C, vector Point )
{
vector AB;// = B-A;
vector BC;// = C-B;

AB.x = B.x - A.x;
AB.y = B.y - A.y;
BC.x = C.x - B.x;
BC.y = C.y - B.y;

if( AB.x * BC.y - AB.y * BC.x < 0 )
{
if( AB.x * ( Point.y - A.y ) >= AB.y * ( Point.x - A.x ) ) return( 0 );
if( BC.x * ( Point.y - B.y ) >= BC.y * ( Point.x - B.x ) ) return( 0 );
if( ( A.x - C.x ) * ( Point.y - C.y ) >= ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 );
}
else
{
if( AB.x * ( Point.y - A.y ) < AB.y * ( Point.x - A.x ) ) return( 0 );
if( BC.x * ( Point.y - B.y ) < BC.y * ( Point.x - B.x ) ) return( 0 );
if( ( A.x - C.x ) * ( Point.y - C.y ) < ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 );
}
return( 1 );
}

Does that work for you?

[edited by - Mulligan on October 9, 2002 10:05:08 PM]

*bump*

It occured to me that I could create three planes based on the triangle''s edge and test the point against those planes, but that''s a waste. It would be faster to make three lines and test those against the point, although this means mapping the lines and the point to the plane, in other words converting them from 3D to 2D coordinates. The lines can be mapped ahead of time since in nearly all cases, the triangle''s shape/size remains unchanged, so you just map the point to the plane based on some arbitrary origin and X/Y axes (which change if the triangle gets rotated).

So, how do you map a point from 3D to 2D based on arbitrary X and Y axes (expressed as 3D vectors)?

Also:

quote:

---

double d = Magnitude(b-a);
D3DVECTOR V = Normalize(b - a);

---

Unoptimized. Should be:

double d = Magnitude(b-a);
D3DVECTOR V = (b - a) / d;

...assuming b != a, which means d != 0.

~CGameProgrammer( );