Point in Polygon function troubles

[Sgraffite]

I'm having trouble getting point in polygon to work correctly in lua. I converted it from this C code from this site:

Code: Select all

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
	 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

To this lua code:

Code: Select all

function pnpoly( vertx, verty, testx, testy )
    nvert = table.getn(vertx);
    c = -1;
    j = nvert - 1;
    for i = 1, nvert do
        if ( ((verty[i] > testy) ~= (verty[j] > testy)) and (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ) then
            c = c * -1;
        end
        j = i;
    end
    return c;
end

I was testing it on a 4 sided polygon, and it works sometimes, but there are spots in the polygon where it should register as being inside but does not. I was reading about this issue and it appears that that problem is associated with variables being passed as integers and not floating points. But after further reading it seems lua should have any issues with this happening.

The best example I could find to what is happening is these pictures:


Where my defined region is the blue, but when testing if I am inside the polygon only the red part shows true.

Any ideas as to why this would be happening?

[Administrator]

Ah, the good ol' point inclusion method. Simple, yet effective. If I had to guess, it's because of your 'c'. You are initializing c as '-1' instead of 'false'. Also, you are then multiplying it by additional '-1's later on.

Code: Select all

local = false;

Code: Select all

c = not c;

Also,

Code: Select all

j = i;

May need to be

Code: Select all

j = i + 1;

[Sgraffite]

I tried out your suggestions but it did not fix the problem. I also tried adding a step of .1 to the for loop but it gives me a cannot compare nil value error. Any other ideas? I'd really like to get this working

[Administrator]

It looks like your implementation was correct. Many polygon collision routines (specifically, those which are fast and easy) only work on convex polygons. It's possible that this is one of those. I'd suggest trying another algorithm.

Here's some old (but good) C++ code of mine:

Code: Select all

/* tests if point hitPos is within the polygon.
   very fast, efficient, but cheap collision. */
bool Poly2D::PointInPoly(Point2D *hitPos)
{
    short edge, lastedge;
    Point2D *pnt1, *pnt2;
    bool inside = false;
    bool flag1, flag2;

    edge = 0;
    lastedge = pointList.size() - 1;

    while( edge <= lastedge )
    {
      pnt1 = &pointList[edge];
      flag1 = ( hitPos->y >= (posy + pnt1->y) ); // is first point over or under the line

      if (edge < lastedge) // "normal" case edge
        pnt2 = &pointList[edge+1];
      else // special case for last point to first point edge
        pnt2 = &pointList[0];

      flag2 = (hitPos->y >= (posy + pnt2->y) );// is second point over or under the line

      if (flag1 != flag2)
      { // make sure it actually crossed the X axis
        if ((( (posy + pnt2->y) - hitPos->y) * ( (posx + pnt1->x) - (posx + pnt2->x) ) >=
          ( (posx + pnt2->x) - hitPos->x) * ( (posy + pnt1->y) - (posy + pnt2->y) )) == flag2 )
          inside = !inside; // toggle the "inside" flag
      }

      edge++;
    }

    return inside;
}