Game Development Community

Point inside a polygon - Pathfinding

by Renzo Sanchez · in General Discussion · 03/24/2009 (3:34 pm) · 1 replies

Hello,

I need to know if a point is inside a polygon or not. I am using the Jordan Curve Theorem and I found this simple code in Internet:

bool pointInPolygon() 
{
   int i, j=polySides-1;
   boolean  oddNodes=false;
   for (i=0; i<polySides; i++) 
   {
  if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i]<x)      
    oddNodes=!oddNodes; 
  j=i;
   }
  return oddNodes; 
}

The problem is that I don't understand the formula and when I try to use a point outside from the polygon and a simple square as a polygin, I get a wrong oddNodes answer.

For example:

PolyX, PolyY
3 5
3.1 2
8 2.1
8.1 5.1

This is the point I want to check:
x=1, y=3

This is the formula:
E=polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])

The E values:
-97, 3, 53, 8

So, oddNodes=0 at the beginning, and I have to check if E<x.
Only -97 is < than x. Then oddNodes will give me 1, but the point is outside of the polygon.

Any idea why the formula is not working in my example? Thanks.
NextNext Thread
PrevPrevious Thread
More from General Discussion


Torque Owner Renzo Sanchez
#1
03/24/2009 (4:17 pm)
This problem has been resolved :)
I needed an aditional if statement 

if (polyY[i]<y && polyY[j]>=y ||  polyY[j]<y && polyY[i]>=y)
  if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i]<x)      
  oddNodes=!oddNodes;