Google interview question

Write the code to determine if a 2D point is inside a 2D closed polygon.

Interview Answers

Anonymous

29 Apr 2009

Write a function that given two line segments L1 and L2, determine if they intersect. Computer a point (x1,y1) outside the polygon (this is easy because such a point can be found simply by finding the bounding box of the polygon and finding a point outside that bounding box). Since polygon is represented by n segments L1...LN, determine how many of the segments intersect with the line segment formed by (x1,y1) and the point mentioned in the problem. If the number is ODD, the problem point is INSIDE, otherwise outside. Note that we have to be careful about intersections where the line segment formed by (x1,y1) and the point mentioned at one of the polygon's vertices (thus making the line segment intersect with TWO of the polygon's line segments instead of just one). Tweaking the algorithm to deal with this problem is easy.

1

Anonymous

20 Mar 2009

This is actually not a super hard question -- any good algorithms book will have some details on various approaches for this -- I was not expecting this question, however, as the position I was interviewing for had nothing to do with graphics at all. Be prepared to be able to write the code and explain it, of course.