Interior points in a polygon

Question

i have to find all interior points in a polygon. I used the following function, to check every point (x,y), but for some points returns true even if the point is exterior or is on the edge of the polygon.

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

Also, it would probably be a good idea to *describe* what the code should do. The code seems to indicate that *polygon* might be limited to a square? — David Rodríguez - dribeas, Aug 24 '12 at 15:25
The poly has 8 vertices: (5,10)(8,9)(11,6)(10,2)(6,0)(1,1)(0,4)(2,8). it returns true for (0,1)(0,2) untill (0,9), then for(1,0)(1,1) untill (1,9). (0,1)(0,2) untill (0,9) and (1,0)(1,1) are exterior points — laura, Aug 24 '12 at 15:27
i replaced by c=!c , but i still have exterior points in the list of the interior points. — laura, Aug 24 '12 at 15:44
@laura: your code is the same as what I use here (we might even have used the same source). Did you check that your problem is not due to rounding errors? To check that, I suggest you get a point right on the edge and slightly perturb it (say by small increments of 1E-15). I'm 99% sure the behavior you see is due to the use of finite precision and not a bug at all. — , Aug 24 '12 at 15:47
Using doubles instead of floats is generally a good idea when you have to do numerical computations. Try to "run your algorithm" in a piece of paper with a small subset of the possible inputs given. It will help you to find the erroneous operation on your algorithm. — Kapoios, Aug 24 '12 at 15:48
@delnan: in computational geometry it's commom to use floats since the arithmetic operations are then done faster than with doubles. — , Aug 24 '12 at 15:49
@laura: Can you explain the idea behind your decision test, as I find it somehow complicated? — Kapoios, Aug 24 '12 at 15:56
@curvature, it is cleary a bug. For it to return true, it is enough that the condition holds for *one* side. Being inside is a property for the whole set of them. — AProgrammer, Aug 24 '12 at 16:02
i am trying to solve the **Interior Points of Lattice Polygons** problem. — laura, Aug 24 '12 at 16:07
@AProgrammer: I meant it's not a bug with the line `c = true` replaced by `c = !c` (sorry, I should have been more clear). This would make her algorithm the same as what I have used here (successfully) for years. Here is my original source: http://paulbourke.net/geometry/insidepoly/ (and this works also for non-convex polygons). — , Aug 24 '12 at 18:55
My idea was to have a function that will verify every point of the bouding box (the minimum value and the maximum value on the poligon coordinates x&y) and if it is inside to save the coordinates of that point into an array. — laura, Aug 26 '12 at 10:10

score 3 · Accepted Answer · answered Aug 24 '12 at 15:55

3

What you want to do isn't to test that

testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i])

but that the relationship stay the same (i.e. always < or always >).

The common way to do that would be something like (not tested, doesn't have to special case for equality)

bool result = true;
bool sign = ((xt-x[n-1])*(y[0]-y[n-1]) < (yt-y[n-1])*(y[0]-y[n-1]));
for (i = 0; result && i < no_vert; i++) 
{
   if (sign != ((xt-x[i])*(y[i]-y[i-1]) < (yt-y[i-1])*(y[i]-y[i-1]))
      result = false;
}
return result;

BTW, this work only for convex polygons.

answered Aug 24 '12 at 15:55

AProgrammer

51,233
8
91
143

n is the same as no_vert? – Rodrigo Oct 09 '17 at 19:13
Looks like your code is wrong, shouldn't you do a cross product instead? – Rodrigo Oct 10 '17 at 00:06

score 1 · Answer 2 · 2012-08-24T15:37:37.397

Your problem might occur due to rounding errors. Even if a point is on the edge of the polygon (or very close to the edge but still outside), your method to determine if it is inside is subject to numerical errors due to the use of finite precision. In other words, it is normal to get false answers in tests like these (I suggest you read about floating point arithmetic).

I recommend you don't rely heavily on exact verifications of this type but instead write code and develop algorithms which can deal with this false positives/negatives. This kind of stuff is ubiquitous in Computational Geometry.

EDIT: I think another possible mistake is you should have c = !c instead of c = true inside the if block.

score 1 · Answer 3 · edited May 23 '17 at 12:16

1

I don't see how your algorithm could work as a general point inside polygon test.

Take a look here for working algorithms: How can I determine whether a 2D Point is within a Polygon?

edited May 23 '17 at 12:16

Community

1
1

answered Aug 24 '12 at 16:05

Jens Agby

410
2
9

Interior points in a polygon

3 Answers3