How do you determine if a point sits inside a polygon?

Given the coordinates of a point $(x, y)$, what is a procedure for determining if it lies within a polygon whose vertices are $(x_1, y_1), (x_2, y_2), \ldots , (x_n,y_n)$?

Solutions Collecting From Web of "How do you determine if a point sits inside a polygon?"

I will assume the polygon has no intersections between the edges except at corners. Call the point $(x_0, y_0)$. First we determine whether we are on a line – this is simple using substitution and range checking. For the range checking, suppose we have a segment $(x_1, y_1)$, $(x_2, y_2)$. We check that $x_1\leq x_0\leq x_2$ or $x_2\leq x_0\leq x_1$ and do the same for $y$.

Now, if we aren’t on a line, we draw a ray from the point and count how many lines you intersect. If the line doesn’t intersect a corner or contain a non-degenerate segment of an edge, then an odd number of intersections should mean you are inside and an even number mean outside.

If we intersect with a corner, it is more difficult. Clearly, the ray could leave with it only intersecting a corner, but it could also pass through the corner without entering the polygon. One solution is to pick the ray so that it doesn’t intersect a corner or go along a line – this should always be possible. We can also use cross product to determine whether we are crossing the lines at their corner or not (just check if the adjacent vertices are on the same side of the line or not).

Representing a polygon by its edge path might not be the most useful, especially if you want to ask about inclusion for many points. Consider triangulating the polygon, which is trivial for convex polygons, and not difficult to find O(n log(n)) for hairier cases. Then determining whether the point is in the polygon reduces to whether it is in anyone of the triangles, which is easy.

If the polygon is: $A,B,C,D,E,F$
and the point is P.
($\text{(angle)}_1$ = angle between $PA$ and $PB$)
($\text{angle}_2$ = angle between $PB$ and $PC$)
($\text{(angle)}_3$ = angle between $PC$ and $PD$)
($\text{(angle)}_4$= angle between $PD$ and $PE$)
($\text{(angle)}_5$ = angle between $PE$ and $PF$)
($\text{(angle)}_6$ = angle between $PF$ and $PA$)

Clockwise are positive
counterclockwise are negative

If ( $\text{(angle)}_1+ …+ \text{(angle)}_1=2\pi\space \text{or}\space -2\pi$) is inside;
else (is zero then is outside;)