Programming Job Interview Challenge Answer Week #14

Posted: 8/5/2008 7:33:09 PM

Here is the question: Programming Job Interview Challenge Question Week #14

This week was a fun and interesting question. Here is the answer

Step 1. As you're adding points to the polygon, determine a bounding rectangle by keeping track of the min x/y and the max x/y.

Step 2. Draw a line from the point you're interested in, to any point outside the bounding rectangle (because you know the outside point can't be within the polygon).

Step 3. Count the number of intersections between your newly created line and the polygon, if the number is even (0 included) the point in question is not within the polygon, if the number of intersections is odd, then the point is within the polygon.

Examples:

Outside = Even Intersections

Inside = Odd Intersections


Tags:

---