Relatively simple geometry...

A line to the left of direction (dx,dy) is (-dy,dx) and right is (dy,-dx). The direction need not be a unit vector. If the dot product of two vectors is positive then the angle between them is less than 90 degrees, if it is zero they are perpendicular and if it is negative it is more than 90 degrees. So if you wind your triangles consistantly, i.e. vertices always listed clockwise or counter-clockwise, you can find a direction pointing out or into the triangle. You can also find the direction from the point to one of the two vertices for a side. The dot product of those two vectors tells you which side of the line you are on. If you are behind all the lines then you are inside the triangle.

Actually I don''t think consistant winding matters. All that matters is that the dot product has the same sign for all sides.

Well, that was confusing and I am afraid I don''t know very much vector math to write my own function to do what you''re talking about, care to help me a great deal and write one? :D

Thanks, ~SPH

Yes. Test if the point is "behind" the three edges forming the triangle. Let the three points in the triangle be x0,x1,x2 and the point inside/outside the triangle be x3.

Now, the edges directions are x01, x12 and x20 (xij means xi-xj, for example x01 = x0-x1). When you know the edge direction xij, you can compute the normal of the edge by:

nij.x = -eij.y
nij.y = eij.x

(I suggest to normalize the normal vector)

Then to check wether x3 is behind an edge xij. The formula is:

d = nij DOT (x3-xi)

If d < 0, then the point is behind the edge, if d > 0, the point is in front of the edge. In code this would be:

// returns 1 if inside, 0 if outside
// checking if the point is in front of ANY edge
// is equal to checking if the point is behind ALL
// edges, and it''s also faster (because the inside/outside
// state is guaranteed immediately), so we perform it that way
//
// I of course assume you write your own Vector2D routines...

int Inside( Vector2D x0, Vector2D x1, Vector2D x3, Vector2D x4 )
{
Vector2D x01 = x0-x1;
Vector2D x12 = x1-x2;
Vector2D x20 = x2-x0;
Vector2D n01( -x01.y, x01.x );
Vector2D n12( -x12.y, x12.x );
Vector2D n20( -x20.y, x20.x );
n1.Normalize();
n2.Normalize();
n3.Normalize();
if( n01*(x3-x0) > 0 ||
n12*(x3-x1) > 0 ||
n20*(x3-20) > 0 )
return 0;
return 1;
}

If it doesn''t work (you get the opposite result), change the > -operator to <=.

- Mikko Kauppila

Thanks for that function, but one problem...

There is a rather large fault in that function, the fact the you use '>' on vectors. I get an error from this obviously, was I intended to implement it myself?

If I was meant to implement the '>' operator myself, then how would I go about finding if a vector is > an integer???

EDIT: You also subtract 20 from one of the vectors in you're 'if' statement, how is this to be implemented?

Thanks, ~SPH


[edited by - ShmeeBegek on February 15, 2003 4:26:25 PM]

quote:

---

Original post by ShmeeBegek
If I was meant to implement the ''>'' operator myself, then how would I go about finding if a vector is > an integer???

EDIT: You also subtract 20 from one of the vectors in you''re ''if'' statement, how is this to be implemented?

---

No no no. He''s multiplying 2 vectors together with a dot product(* symbol) which results in a scalar. Do you even know what a dot product *is*?

And for the second question, I think that''s a typo...

Thanks for you''re negativity, it helped a lot :-p.

I thought he was multiplying the vectors, often someone will use a function called ''dot'' for the dot product.

~SPH

Sorry, I get excessively sarcastic sometimes. There's no real meaning to "multiplying" vectors, unless you define cross product as "multiplication". I don't think it is a good idea to define either cross or dot as "vector multiplication".*

Damn, there needs to be a dot key on the keyboard so we can put this thing up easily: œ

[EDIT]:Alright, the internet does not like extended ASCII...

[edited by - Promit on February 15, 2003 4:48:40 PM]

Well anyways, I''ve got it to compile now but it allways returns true, so I investigated what I was getting for the dot products, I am getting ''-1.#IND00'', anyone have any ideas on what this might be a result of?

My dot product function is as follows:

float vector::dot(float dx, float dy){return (this->x * dx) + (this->y * dy);}

and the ''Inside'' function was edited to become:

int Inside( vector x0, vector x1, vector x2, vector x3 )
{
vector x01 = x0-x1;
vector x12 = x1-x2;
vector x20 = x2-x0;
vector n01( -x01.getY(), x01.getX() );
vector n12( -x12.getY(), x12.getX() );
vector n20( -x20.getY(), x20.getX() );
n01.normalize();
n12.normalize();
n20.normalize();printf("%f\r\n",n01.dot(x3-x0));
if( n01.dot(x3-x0) > 0 ||
n12.dot(x3-x1) > 0 ||
n20.dot(x3-x2) > 0 )
return 0;

return 1;
}


~SPH

Bump...

~SPH

I am still wondering about this???

~SPH

Check the forum FAQ. It''s a standard "point-in-polygon" answer. There are numerous solutions.

Cédric