Question

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?

Answer 1

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

Answer 2

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 3

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.

友情链接