PDA

View Full Version : Is a point in a polygon

HairyFotr
02-28-2004, 10:21 AM
Hi.

I have a array of points, from which i draw multiple polygons from.

I'm using polygons for terrain in a 2d game, so I'd need a function, to tell me, if a point is outside a polygon, or if it is touching it, or is inside (in short: for terrain collision detection).

How, would i do that?

Thanks!

chemdog
02-28-2004, 10:22 PM
First you determine if the point is in the same plane as the polygon. The plane for a polygon can be retrieved by taking the crossproduct of any two adjacent edges (for the plane normal), and then determing the offset (the D in the plane equation 0 = Ax+By+Ca+D). Usually the last and first edge of a polygon are used, that way the numbers always come out the same(floating point math can lose precision, so different answers are possible depending on where the normal is taken).

In a right-hand coordinate system, the plane normal P = (v0-vn)cross(v1-v0), and the offset D = - P dot v0.

Now you can plug the suspect point S into plane equation. value = (P dot S) + D. If value is zero, (smaller in size than some choosen epsilon, because of floating point error), then the point is in the plane.

Now to determine if the point is in the polygon, iterate over the edges. If the point is on the right hand side of every edge, then the point is in the polygon. (left hand side, if the vertices are clockwise, and flipped again for both if a left-hand coordinate system is used).

The turn-test is to determine the angle that is made from vi to v(i+1) to S. If the angle is 0 to pi radian (0 to 180 degrees), then the turn is a right turn.(Books would call this a non-left turn, because I included straight; the difference is this will include points on the polygon boundary). One can determine the angle from sign of the dot product, from (vi+1 - vi) dot (S - vi+1). If the two vectors point in the same half-plane, (right-hand turn), it is positive, and if they point in opposite half-planes (left-hand turn), it is negative.

If you want a ray to polygon intersection. Do the same thing, except add a ray to plane intersection to determine the point on the plane where the ray intersects it.

You can precompute P and D, and place them in lookup tables, for speed if necessary.