point in a self-intersecting / complex polygon

Question

I've read http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test but I'm not sure if the solution would apply to a polygon that is divided down the middle by an interior segment. Think of a squared-off figure 8 or simply two squares stacked on one another. A point inside either square would surely be "inside" the polygon but the crossing count would differ depending on which direction you went (and whether you crossed that interior segment).

I suppose one way of dealing with this is to treat the polygon as two separate polygons... (in which case I'll need an algorithm to divide a complex polygon into a set of simpler ones?)

Or is there a refinement to the ray-casting algorithm, or another point-in-polygon algorithm, to deal with the case I described?

Answer 1

I'm not sure if this is the optimal solution; but the ray-casting algorithm works for any convex polygon. Any polygon can be decomposed into triangles, which are convex. (The double box is not a convex polygon, since if you connect two of the vertices with a line segment, in some cases you will cross over the center edge.) So, to clarify: first decompose the polygon into triangles, then use ray-casting to determine whether the point is inside a triangle.

[Edit: ray-casting does work for concave polygons. Sorry, I was mistaken.]

Answer 2

The algorithm described will work fine, cause if you take a look closer at it, you see that it's just the number of crossings that counts. If we start in either "sub-polygon" of the "8" we will cross in worst case the edges 3 times, normally once. And it's true that it's inside. Otherwise it's outside.

However, one may assume that there's one special case. If the ray goes EXACTLY through a crossing point. But note that in that case, you'll ALSO get 2 intersections :).