Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
2  
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

3 Answers 3

up vote 7 down vote accepted

I will assume the polygon has no intersections between the edges except at corners. Call the point (x0, y0). 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 (x1,y1), (x2,y2). We check that x1<=x0<=x2 or x2<=x0<=x1 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).

share|improve this answer
2  
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.

share|improve this answer
    
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 poligoon is: A,B,C,D,E,F
and the point is P.
(angle1 = angle betwen PA and PB)
(angle2 = angle betwen PB and PC)
(angle3 = angle betwen PC and PD)
(angle4 = angle betwen PD and PE)
(angle5 = angle betwen PE and PF)
(angle6 = angle betwen PF and PA)

clockwise are positive
counterclockwise are negative

if ( angle1+ ...+ angle6 == 2*PI or -2*PI ) is inside;
else (is zero then is outside;)

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.