Inside and outside a polygon | Tangente

A simple polygon, or Jordan polygon, has an interior and an exterior (see the article What is a polygon?). Which algorithm can determine whether a point in the plane lies inside or outside the polygon? The question seems trivial for a reasonably uncomplicated polygon such as the one in the following figure:

The human brain needs only a quarter of a second to tell us that point M lies inside the polygon, whereas point N lies outside. But how can this be done algorithmically? This question arises repeatedly in geographic information systems, graphical user interfaces, computer graphics, computer-aided design systems and robotics. Moreover, in more complex cases, the eye can be deceived.

The polygon is indeed simple, but does point M lie inside or outside it?

The "ray-crossing method" ---------------------------------

The simplest "point-in-region" algorithm is the "ray-crossing method," which originated in Stig Nordbeck and Bengt Rystedt's 1967 work on cartography. It involves drawing a line through the point whose position is to be determined. Starting from the outside, we then count the intersections with the polygon. Whenever this number is odd, the point lies inside the polygon. Using a horizontal or vertical line simplifies the calculations.

This algorithm is easy to implement. Care must be taken when the line passes through a vertex. A point very close to an edge can also cause problems. This widely used algorithm has numerous refinements designed to reduce its computational complexity.