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!
 A: 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.
A: 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.
A: 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.
