Search This Blog


Friday, August 8, 2008

Solution to Programming Job Interview Challenge #14 - 2D Geometry

This is a solution to A Programming Job Interview Challenge #14 - 2D Geometry.

Here's the code

public bool IsPointInPolygon(List polygon, Point pt)
for(int i=0; i<polygon.Count; i++)
if(!IsPointOnLeftLine(polygon[i], polygon[(i+1)%polygon.Count], pt))
return false;
return true;

Basically, the idea is that we connect adjacent points in the polygon together to form lines, and then, we check whether the given point is located on the left or right of the lines. If we find that the given point locates at at least one of the right side of any polygon lines, then we can conclude that this point is outside the polygon. Else the point is inside the polygon.

To check whether the point is on the left or right side of a line, we can construct a polygon that has three points, namely, the start point of the line, the end point of the line, and also the given point. Then we test the area of this polygon, if it's positive, then the point is on the left side, else it's on the right side. Here's the code

 public bool IsPointOnLeftLine(Point linePtStart, Point linePtEnd, Point pt)
List polyTriangle = new List({linePtStart, linePtEnd, pt});
double area =0;
for(int i=0; i<polytriangle.count; i++)
int j=(i+1)% polyTriangle.Count;
area += polyTriangle[i].x * polyTriangle[j].y-polyTriangle[i].y * polyTriangle[j].x;
return area>0;

The solution assumes that the polygon is in anti-clockwise order. If the polygon is in clockwise order, then just reverse the algorithm :).

No comments: