Home > IT & Software > A Programming Job Interview Challenge #14 – 2D Geometry

A Programming Job Interview Challenge #14 – 2D Geometry

August 10th, 2008

Well I could tell a lie and say that I knew how to do this, but i dont – so i’ve done a little bit of research and i’m now taking an educated guess as to how I would approach this problem. This might get me disqualified from the comp, but when i was doing interviews, i didnt care so much if someone didn’t know the answer to a problem if they could show that they had the capabilities of working the problem out themselves :)

Either way, i’m not convinced this is the most efficient nor is it the best way to solve this problem…There would be a mathematically more appropriate way without all the fussing around.

http://www.dev102.com/2008/08/05/a-programming-job-interview-challenge-14-2d-geometry/

Your input:

1. 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).
2. A single point in a 2D space.

You need to determine whether the given point is inside or outside the given polygon.

According to wikipedia (this is the part i cheated on), we can use the ray-casting algorithm to determine whether a point is inside or outside a polygon.

So my algorithm (this is all my doing) for this process would be:

  1. Loop through all segments of the polygon formed by joining each successive point to the next.
  2. For each segment, determine the equation of the segment using the formula f(x) = mx + b (function for a line).
  3. Determine the equation for a segment from the single point along the x-axis up to the highest value for x in all the existing points, plus 1 (so that we know we get an intersection if one exists). This segment is parallel to the x-axis
  4. Use the formula to determine the intersection of two lines by solving the equations with each other (simultaneous equations). If the equation is unsolvable, then the lines don’t intersect. If they do intersect, then record the intersection and move onto the next segment.
  5. After all segments have been hit-tested, if the number of hits is odd, then the point is within the polygon. If the number of hits is even then the point is outside the polygon.

Not so simple, and i don’t feel it’s elegant enough just yet. :(

i’ll submit it anyway – better to be in it and lose, than never try.

Bookmark this post:
  • DotNetKicks
  • DZone
  • TwitThis
  • Digg
  • del.icio.us
  • Facebook
  • Google Bookmarks
  • LinkedIn
  • Live
  • MySpace
  • Slashdot
  • StumbleUpon
  • Technorati

Related posts:

  1. A Programming Job Interview Challenge #13 – Brackets As the title suggests, here is my solution for A...
  2. A Programming Job Interview Challenge #11 – Summing Numbers In it’s 11th installment in a series of posts of...
  3. Back to high-school Trig basics Given this diagram, i need to find the coordinate X,Y....

Xerxes IT & Software