# 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)$?

-
Is it the most general polygon or is it a simple polygon? or even a convex polygon? – Chao Xu Jul 21 '10 at 2:37
I have to admit I was picturing a convex polygon (in fact, originally a triangle is what I had in mind, but I thought I might as well ask the more general question). I'll leave it without the restriction of convexity, but perhaps someone will ask the simpler question about the triangle case. I would not consider that a duplicate of my question, since special cases can have special algorithms. – bryn Jul 21 '10 at 4:49
I think I'll leave this here for posterity: Point-in-polygon on Wikipedia. Casebash's answer describes the ray casting algorithm, while rondan has just posted the winding number algorithm. – Rahul Aug 26 '11 at 4:52

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

-
Wikipedia article – Casebash Jul 21 '10 at 3:02
Lolz, I just realised that when I originally stuffed up the corner cases, I actually stuffed up corner cases – Casebash Jul 21 '10 at 6:02

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 problem involves test many points on the same polygon. It can be done in O(log n) per query with Kirkpatrick's triangulation refinement method. Which is like triangulating the polygon at different levels. – Chao Xu Jul 21 '10 at 12:35

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;)

-
In Rahul Nahrain's comment to the original question, this link is given; this coincide with the second method given there. For those of you who are familiar with differential topology or complex analysis, this is based on computing the winding number. +1 – Willie Wong Sep 5 '11 at 13:31