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

migrated from stackoverflow.comSep 11 '12 at 11:40

This question came from our site for professional and enthusiast programmers.

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? –  ElKamina 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.

-