How do you tell if a point is within the boundaries of a triangle in 2D? I need this to make my character follow polygonal terrain in a 3D game. Please help!

Wait, you need to know how to tell if a point is within the boundaries of a triangle to make a charecter follow a polygonal terrain in a 3d game? That''s really confusing. Could you explain a bit more?

"Remember, I'm the monkey, and you're the cheese grater. So no fooling around."
-Grand Theft Auto, London

Hey I can finally answer one!

Ok this is going to take a bit of explaining. If you have points a, b, and c arranged as follows:
a

b c
then you can tell their orientation (clockwise v. counterclockwise). Now if point D were in the middle, you could check the orientation of a,b,d and b,c,d and c,a,d.

if the orientation of a,b,d = a,b,c and orientation b,c,d = b,c,a and orientation c,a,d = c,a,b then point d is inside the triangle.

Now the question is how to check orientation. Back when I worked in QB only, I used this algorithm to check culled polygons in 3d - if their orientation switched, they were turned away from me. Here it is, translated to C/C++...

bool Orientation(x1, y1, x2, y2, x3, y3)
{
int xtop; //xcoord of top point
int ytop; //ycoord of top point
int xmid;
int ymid;
int xbot;
int ybot;
int ptop; //which point is top
int pmid; //which point is middle
int pbot;
int pfirst;//horizontal order of points
int pnext;
int plast;
if (y1 <= y2 && y2 <= y3)
{
xtop = x1;
xmid = x2;
xbot = x3;
ytop = y1;
ymid = y2;
ybot = y3;
ptop = 1;
pmid = 2;
pbot = 3;
}
if (y1 <= y3 && y3 <= y2)
{
xtop = x1;
xmid = x3;
xbot = x2;
ytop = y1;
ymid = y3;
ybot = y2;
ptop = 1;
pmid = 3;
pbot = 2;
}
if (y2 <= y1 && y1 <= y3)
{
xtop = x2;
xmid = x1;
xbot = x3;
ytop = y2;
ymid = y1;
ybot = y3;
ptop = 2;
pmid = 1;
pbot = 3;
}
if (y2 <= y3 && y3 <= y1)
{
xtop = x2;
xmid = x3;
xbot = x1;
ytop = y2;
ymid = y3;
ybot = y1;
ptop = 2;
pmid = 3;
pbot = 1;
}
if (y3 <= y2 && y2 <= y1)
{
xtop = x3;
xmid = x2;
xbot = x1;
ytop = y3;
ymid = y2;
ybot = y1;
ptop = 3;
pmid = 2;
pbot = 1;
}
if (y3 <= y1 && y1 <= y2)
{
xtop = x3;
xmid = x1;
xbot = x2;
ytop = y3;
ymid = y1;
ybot = y2;
ptop = 3;
pmid = 1;
pbot = 2;
}
//Up till here has just been sorting them by y-position
//now we mix up the y''s if they''re equal - saves trouble
if (ymid == ybot && xmid > xbot)
ybot == ybot + 1;

if (ytop == ymid && xtop < xmid)//Find Final Verdict
{
pfirst = ptop;
pnext = pmid;
plast = pbot;
GOTO done;
}

if (ytop = ymid && xtop > xmid)
{
pfirst = pmid;
pnext = ptop;
plast = pbot;
GOTO done;
}

if (ytop == ymid && ymid == ybot)
return false;/*not really a false, this means triangle is a horizontal line - make a new return val for this.

xmidline = (xbot - xtop) / (ybot - ytop) * (ymid - ytop) + xtop; /* Y-coord where horizontal line thru middle point would hit line from top to bottom point*/

if (xmid < xmidline)
}
pfirst = ptop;
pnext = pbot;
plast = pmid;
GOTO done;
}
if (xmid > xmidline)
{
pfirst = ptop;
pnext = pmid;
plast = pbot;
GOTO done;
}


done:
if (pfirst = 1 && pnext = 3)
return true;
if (pnext = 1 && plast = 3)
return true;
if (plast = 1 && pfirst = 3)
return true;
return false;
}

Sorry for any syntatical errors and the overall sloppiness I converted from BASIC right here in this window. I don''t know the GOTO command, so change it to whatever in c++. You should get the basic idea. First I order the points vertically and horizontally, and change them a little if necessary to make them different. Then I find which side of the line between the top and bottom points the middle point is. This shows you the orientation. Also in there are some checks if we could find the orientation quicker. Sorry if the code seems sloppy and worthless, I wrote it when I was like 9 or 10.

Just check if Orientation(ax,ay,bx,by,dx,dy) == Orientation(ax,ay,bx,by,cx,cy), etc etc etc.

Hope this helps.

Just so you know, goto is still goto - it''s just considered poor programming practice, so most books don''t document it. You''d set it up just like basic, like this:
label:
if (something)
goto label;

Thanks, guys! By the way, the reason I need to tell if a point is within a triangle for terrain-following is that I need to know which triangle the player is standing so I can calculate the absolute height of the player from the XZ plane.

Hey, I figured out a remarkably simple way to do this! I''m not sure how much faster/slower than the other way is, but it works!

//////////////////////////////////////////////////////////////////////////
// Tri.cpp - Tests if a point is within a triangle
// (C) 2000 Scott Hilbert

//////////////////////////////////////////////////////////////////////////
// Includes

#include

//////////////////////////////////////////////////////////////////////////
// Point structure

typedef struct
{
float x;
float y;
} point;

//////////////////////////////////////////////////////////////////////////
// Prototypes

float Slope(point p1, point p2);
bool WithinTriangle(point a, point b, point c, point d);
bool IsBetween(float a, float b, float c);

//////////////////////////////////////////////////////////////////////////
// Function to get slope of a line

float Slope(point p1, point p2)
{
// normal line
if(p1.x != p2.x)
return (p1.y-p2.y)/(p1.x-p2.x);
// vertical line -
// return a really high number for slope
else return 9999999;
}

//////////////////////////////////////////////////////////////////////////
// Checks if B is between A and C

bool IsBetween(float a, float b, float c)
{
// check for between-ness
if( a <= b && b <= c ) return true;
if( a >= b && b >= c ) return true;

// nothing, bail
return false;
}

//////////////////////////////////////////////////////////////////////////
// Checks whether point D is within triangle ABC

bool WithinTriangle(point a, point b, point c, point d)
{
// slopes of involved segments
float ab = Slope(a,b),
ac = Slope(a,c),
ad = Slope(a,d),
bc = Slope(b,c),
bd = Slope(b,d);

// do first check on slopes
if( !IsBetween(ab, ad, ac) ) return false;

// second check
if( !IsBetween(ab, bd, bc) ) return false;

// all OK, return true
return true;
}

//////////////////////////////////////////////////////////////////////////
// Main

void main()
{
// test points checked by func.
point a = {0,0}, // These 3 points are the triangle
b = {5,5},
c = {1,4},
d = {1,2}; // This is the one tested.
// Change to see different results

// do the check!
if( WithinTriangle(a,b,c,d) ) cout << "Test Successful!" << endl;
else cout << "Test Unsuccessful!" << endl;

}

Wow, you guys really put too much effort in your code. I think SHilbert''s code is like mine. My code uses 3 SLOPE-INTERCEPT equations. Remember y=mx+b. The only difference is that it uses y>=mx+b or y<=mx+b.