Finding whether a point is within a polygon

[oswaler]

Hey guys, its been a while since I had to do something like this, so any help would be appreciated

I'm working on a project and I have a polygon defined by n vertices (there will be multiple polygons overall, each with an arbitrary number of vertices). I need to know whether a given point falls within the boundaries of the polygon. Can someone give some insight into how to calculate this? Is this a linear algebra problem?

Thanks

[NickThissen]

Check out the raycasting algorithm here:
http://en.wikipedia.org/wiki/Point_in_polygon

It doesn't describe an implementation of the algorithm, but its easy to understand how it works. You simply draw a line from left to right through the point. You count how many times that line intersects an edge of the polygon. The number of intersections determines if the point is inside or outside the polygon. If the number of intersections is even, the point lies outside the polygon. If it is odd, the point lies inside.
If the point lies exactly on the edge of a polygon it can turn out either way, but in most cases this doesn't matter. Most of the time this is used to determine if a mouse click is inside a polygon (or something like that). If the user clicks right on the edge then is it essential that the algorithm always returns 'inside' or 'outside'? I think not.

Anyway, here's some C code I found that implements the algorithm. It should be easy to convert to VB or C# or java or whatever you want to use. Just realize that 'vertx' and 'verty' are arrays (containing the x and y vertices, respectively). nvert is the number of vertices, and testx, testy is the point you want to test for.
Finally, in most languages you would implement 'c' as a boolean instead of an integer.

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

[oswaler]

Thanks for the help. This does involve a program to see whether a user has clicked inside a polygon. I think if they click exactly on the line we would call it outside and just have them click again.

I have a question about a ray that travels exactly through a vertex. Technically the ray has gone through 2 sides but it just happens to go through the exact pixel where the 2 sides meet. Would you then count the vertex as 2 sides and calculate it from there or is there a special situation for that that has to be programmed?

[NickThissen]

I'm not sure whether the algorithm I posted counts that as inside or outside. But does it really matter? It will be very hard for the user to click exactly on an edge (let's face it, pixels are small ) so it will probably never happen. And even if it does happen, it doesn't matter. Suppose the algorithm counts it as outside. Then the user clicks exactly on the edge, but the click doesn't register. Problem? No, I don't think so, because the user will assume he clicked outside the polygon and will try again.

I've used this algorithm a few times before and it always felt very natural. I think you'll find it good enough for anything but the most exact purposes.

[oswaler]

Thanks, that was pretty much the assumption I was going on. My concern was mainly about the ray passing exactly through one of the vertices. Depending on the orientation of the vertex to the ray, it seems like the vertex should count either as 1 side or 2 sides. Is the likelihood of this happening so small that it is usually ignored?

[jemidiah]

If there are 100 vertexes on your polygon, say they correspond to 100 pixels which might give bad results. If your polygon is quite small relatively speaking and covers an area equal to an area of about 200x200 pixels, there are around 40000 "good" pixels for you to pick, and only 100 "bad" pixels. This gives a probability of clicking a bad pixel, given the unrealistic assumption that clicking is uniform, of 100/40000 = 1/400 = 0.25%. This decreases greatly if you have fewer vertexes or a larger polygon.

The uniform assumption above is a lie, but then again even if it's remotely true the probability is still going to be quite tiny. I don't think there's any reason to worry about edge clicks. I don't think one convention or another is even standard--does a click on the edge mean inside or outside? If we don't really know, it doesn't matter if the program knows.

Also, that C code is hard to read, so I didn't figure out how it handles edges or corners.