Triangle question

[cyborg]

Hi!

How do I determine if a point is inside a triangle.

Thanks for any help!

[jemidiah]

You could check each line's equation, checking whether the point is in the correct relation of each of the three lines. I'd bet there's a more efficient way, though.

[cyborg]

You mean check the angle?

[jemidiah]

Actually, I meant check the inequality of each line against the point. Something like this:

(viewed with picture)
For x = y, the point must be below the line. Therefore, the inequality x >= y must hold true. For x = 1, it must be to the right of the line. Therefore, the inequality of x <= 1 must hold true. With the line y = 0, the point must be above the line. Therefore, the inequality y >= 0 must hold true.

Plugging it all in, 0.5 >= 0.25; 0.5 <= 1; 0.25 >= 0. They are all true and the point is then on the line.

Like I said, it's inefficient and difficult to implement. I'd bet there is another way involving angles or the length of line segments.

[sunburnt]

a point X is outside of a triangle ABC if

B X
/_\
C A

ABX is a clockwise turn OR
BCX is a clockwise turn OR
CAX is a clockwise turn

a point X is inside of a triangle ABC if

B
/X\
C A

ABX is a counter clockwise turn AND
BCX is a counter clockwise turn AND
CAX is a counter clockwise turn
You can determine clockwise/counterclockwise by taking the determinant:



SomeType Determinant(x1, y1, x2, y2, x3, y3)
{
float determ = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);

if (determ >= 0.0)
return CounterClockwise;
else
return Clockwise;
}


so:


if ( (Determinant(A.x, A.y, B.x, B.y, X.x, X.y) == CW) ||
(Determinant(B.x, B.y, C.x, C.y, X.x, X.y) == CW) ||
(Determinant(C.x, C.y, A.x, A.y, X.x, X.y) == CW))
{
Point X is outside
}
else
{
Point X is inside
}

[cyborg]

Thanks alot! My program works really smooth now!

[sunburnt]

I should mention that you need to have the verteces of the triangle in Counter Clockwise order for this to work!

[cyborg]

I just do like this:


If CheckTriangle(.Point(2), .Point(1), .Point(0), X, Y) Or CheckTriangle(.Point(0), .Point(1), .Point(2), X, Y) Then


It works really fine :)

[cyborg]

I've got one problem though...
When porting it to c code, the functions seem to always return true. You seem to know some c, so i ask you here. What's wrong with this code?



bool Determinant(double X1,double Y1,double X2,double Y2,double X3,double Y3)
{
double determ = (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);

if (determ >= 0)
return true;
else
return false;
}

bool _stdcall CheckTriangle(sPoint* A, sPoint* B, sPoint* C, double X, double Y)
{
if (Determinant(A->X, A->Y, B->X, B->Y, X, Y) ||
Determinant(B->X, B->Y, C->X, C->Y, X, Y) ||
Determinant(C->X, C->Y, A->X, A->Y, X, Y))
return true;
else
return false;
}