The following is challenge #14 in the dev102 series of programming interview challenges and my solution:
The question
Your input:
- List of points in a 2D space. If you draw lines between one point
to the next one, a closed polygon is created (can be either concave or
convex).
- A single point in a 2D space.
You need to determine whether the given point is inside or outside
the given polygon.
My solution
Draw a ray starting at the given point that will intersect at least one of the edges of the polygon. Run a simple intersect algorithm with this ray against all edges of the polygon. If the ray intersects the polygon an odd number of times, then the point is inside the polygon. If the ray intersects the polygon an even number of times, then the point is outside the polygon.
The reason for this is because whenever you cross an edge of a polygon, you are either entering it or leaving it. Since a polygon cannot be infinitely large, the last edge the ray crosses must be one that leaves the polygon. An odd number of intersections must indicate that the ray started from within the polygon because if the converse were true, that is if a ray with an odd number of intersections with the polygon were to have started from outside the polygon, then the final status of the ray would be within the polygon (e.g. 3 intersections -> entering, leaving, entering), which cannot happen.
As for what to do when the ray intersects the vertex of two edges of the polygon or when the ray lies right on the edge(s) of the polygon, I have no idea. Pick a ray that doesn't do either of those. :-P
Enjoyed this post? Share it with others!