CODEWITHSUNDEEP
c++ccomputational-geometry
laura
laura

Reputation: 2135

Interior points in a polygon

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;
}

Upvotes: 1

Views: 2004

Answers (3)

Jens Agby
Jens Agby

Reputation: 410

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?

Upvotes: 1

AProgrammer
AProgrammer

Reputation: 52274

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.

Upvotes: 3

user1607425
user1607425

Reputation:

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.

Upvotes: 1

Related Questions