point in a self-intersecting / complex polygon

4
votes

I've read How can I determine whether a 2D Point is within a Polygon? 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).

sample polygon

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?

3
geometrypolygon
There are many different approaches that would make things work in this case, but they all depend critically on how you interpret this situation. More specifically, how do you represent such "polygons"? What data structure is used? Can you have more than one interior segment? If so, can interior segments intersect each other? – AnT
Basically, at this time it appears that all you have is a sketch of a problem. You haven't finished formulating the problem yet. It is too early to search for a solution, when the problem itself is not fully stated. – AnT

3 Answers

2
votes

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 :).

0
votes

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.]

0
votes

The referenced intersection algorithm works for any closed polygon, even if concave or self-intersecting. In order for your two-box polygon to be closed (starting and ending at the same point), the middle segment must be traversed twice. That means that your example ray going through the bottom crosses three edges, so it is inside using the odd-even rule.