Checking whether a point is inside/outside/on a polygon (not necessarily convex)

Question

I need to write an algorithm for checking whether a given point belongs to a polygon or not. I also need to be able to tell when a point is located on one of the edges. The most popular "point in polygon" approach, ray casting, seems to be okay, but its answer is binary i.e doesn't cover the boundary case.

I know there is a solution for the convex case when we first calculate the area of the polygon and then compare it to the sum of areas of triangles formed after connecting the given point with each vertex.

If the latter sum of areas is greater than the polygon area, we make the conclusion that the point is outside.

Else, if the areas are the same and one of the triangle areas equals 0, the point is on one of the polygon's edges. Else, the point is said to be internal.

It seems that this approach is not applicable (at least in this form) when dealing with a non-convex polygon. Is there any way to solve the problem making some adjustments for arbitrary polygons?

Thank you!

Answer 1

Assuming that the polygon has no self-intersections, a point is exterior to the polygon iff its winding number is zero. Here’s a sketch of how this might be computed:

First, assign a consistent orientation to the edges; whether the polygon is traversed clockwise or counterclockwise doesn’t matter here. Then, consider a ray originating at the point $\mathbf p$ being tested. A convenient choice is the horizontal ray $\mathbf p+(t,0)$. Initialize the winding number to $0$. Now, for each edge that intersects the ray, add $1$ to the winding number if the edge crosses the ray “right-to-left” and subtract $1$ if “left-to-right.” If a vertex lies on the ray, you’ll need to look a bit more closely at the edges that meet at that vertex to determine the correct adjustment to the winding number, the details of which I’ll leave to you. If the final result is $0$, the point is external to the polygon.

If the polygon has self-intersections, you’ll have to decide whether or not those overlaps represent “holes” in the polygonal region. If not, then you can use the above process more-or-less unchanged. If they are holes, on the other hand, then you’ll need to use what’s known as the even-odd convention: the point is external to the region when the winding number is even.