Working out an algorithm for finding out whether a point is in or outside of a 2D closed polygon

I'm having a bit of an issue with the following problem:

Write a brief (1/2 page) design specification document (including pseudo code for the algorithm itself) that describes your approach to solving the following geometric problem: Given two straight lines in 2D (each line defined by a pair of points), determine whether they intersect.

Explain how you could apply the test in to write an algorithm to find whether a point lies inside or outside a 2D closed polygon consisting of $N$ points joined by straight lines.

As far as I am aware, it is possible to work out whether 2 lines intersect by working out each line equation, and then simultaneously solving those. IE:

2 lines at $(4, 2)$ to $(2, 0)$ and $(0, 4)$ to $(4, 0)$.

Solving simultaneously, the two lines intersect at $(3, 1)$

However, I am not quite sure how I would apply this method into an algorithm that for a 2D polygon as specified in the question.

Any help would be greatly appreciated!

• it has to do with finding how many times a certain line is intersecting with the polygon. i could be more specific but i didn't want to spoil your enthusiasm for research.
– muratgu
Sep 11 '12 at 4:36
• This should be on Math Exchange
– wich
Sep 11 '12 at 4:56

You have one point p1 (x1, y1) that is given. Now, create another point far away from everything (one way to do: you can find maximum y coordinate of the polygon and add 1 to it. That is your y coordinate. Keep the x coordinate as x1. That is p2 = (x1, max(polygon_y)+1 ).

Let the vertices of the given polygon be v1, v2, ... , vn. So the edges are (v1,v2)...(vn,v1). Check how many of these edges intersect with (p1,p2). If it is even then the point is outside the polygon and if it is odd then it is inside.

• I can't see how the number of edges that intersect with the line joining $p_1$ and $p_2$ will change depending on whether $p_1$ is inside the polygon or not. Do you also include the intersections where one or both of the line segments have to be extended?
– ajay
Sep 11 '12 at 12:06
• @ajay I am talking about intersection of the "line segments", not "lines". Is it not obvious that the line to the horizon intersects the polygon odd number of times if the point is inside the polygon? Sep 12 '12 at 4:14

As noted above, you can solve the intersection question by fence hopping. The real-life analogy is that if a field is surrounded by a fence then you can walk in a straight line and count how many times you have to jump the fence until you're definitely away from the field. If it was an odd number of times then you must have started inside the field. If it was even then you must have started outside. That follows from the observation that if you're outside at the end then either you exited or you exited then entered then exited or you exited then entered then exited then entered then exited, etc.

As for line intersections, you can do a little better than solving both simultaneously — you can apply separating planes. If both points of either line are on the same side of the other then there's no intersection. Otherwise there is an intersection. In terms of computer coding that's a better solution because it can be implemented with no divides, which — apart from the historic cost of divides that's barely relevant now — has the nice effect that you don't have to insert alternative code paths to ensure you're not dividing by zero.

This problem is really asking you to describe the Convex Hull of the polynomial.

For this, you'll want to arrange the points along the boundary of the polygon and then compute the line segments that border the polygon. The interior of that bounding region is what you're after.

• I think you have misinterpreted the problem. The polygon does not have to be convex, and there are points that are inside the convex hull defined by the points that might not be in the interior of the given polygon as stated.
– MBennett
Sep 11 '12 at 5:29
• @MBennett Good point. It's not necessarily convex. Still, I think many of the ideas that handle the convex case are applicable, so I'll leave this flawed answer up in case it helps. Thanks for the catch. Sep 11 '12 at 5:30
• "polynomial" or "polygon"?
– lhf
Sep 19 '12 at 3:44