I want to check whether a given point lies inside a polygon.
I have looked into the point in polygon method using ray casting, but I'm unsure of how it will work in cases where the given polygon in disjoint. For example, if the polygon has a "hole" right in the center. How do I use this function in such cases?
Best How To :
I've answered a similar question here, even though it wasn't clear if I understood the OP's question too well. Well , here it is again -
Let's take a very general case . Polygon with a hole and Intersections
The ray casting (point in polygon) algorithm shoots off a ray counting the intersections with the sides of the POLYGON (Odd intersections = inside, Even = outside).
Hence it accurately gives the correct result regardless of whether you start from inside the disjoint trapezoidal hole or the triangular hole (inner edges?) or even if a part of the polygon is completely seperated and/or self intersecting.
However, in what order do you feed the vertices of the polygon such that all the points are evaluated correctly?
Though this is code specific, if you're using an implementation that is counting every intersection with the sides of the polygon then this approach will work -
- Break the master polygon into polygonal components. eg - trapezoidal hole is a polygonal component.
- Start with (0,0) vertex (doesn't matter where (0,0) actually lies wrt your polygon) followed by the first component's vertices, repeating its first vertex after the last vertex.
- Include another (0,0) vertex.
- Include the next component , repeating its first vertex after the last vertex.
- Repeat the above two steps for each component.
- End with a final (0,0) vertex.
Let's take the picture to the right, the shell with the hole and apply the above method. The vertices of a singular continuous polygon which is mathematically equivalent to the 2 components (polygon+hole) is -
To understand how it works, try drawing this mathematically equivalent polygon on a scratch pad.-
1. Mark all the vertices but don't join them yet.
2. Mark the repeated vertices separately also. Do this by marking them close to the original points, but not on them. (at a distance e, where e->0 (tends to/approaches) ) (to help visualize)
3. Now join all the vertices in the right order (as in the example above) You will notice that this forms a continuous polygon and only becomes disjoint at the e=0 limit.
You can now send this mathematically equivalent polygon to your ray casting function (and maybe even winding number function?) without any issues.