In this programming challenge it involves collecting a series of points to form a polygon in a 2d field and then 1 additional point in the field by itself. The goal is to determine if the point is either inside or outside of the polygon.
http://www.dev102.com/2008/08/05/a-programming-job-interview-challenge-14-2d-geometry/
This problem sounds a lot more complex than I believe it actually is since we are only going to deal with closed form polygons I believe we only need 2 vectors to simulate an X, Y coordinate plane.
Enter Polygon Coordinates: For every coordinate position add the x value to ordered VectorX, and y value to ordered VectorY. Ignore duplicates.
Take hanging coordinate position: ValueX, ValueY
With VectorX and VectorY already being sorted
bool xInside = false;
for (int i=0; i<VectorX.Count; i++)
if(VectorX[i] <= ValueX && ValueX <= VectorX[i]
{
xInside = true;
break;
}
Now repeat process for yInside, if xInside and yInside are both true the point is inside the polygon otherwise it is outside. Ignoring the time for sorting this algorithm solves this problem in 2*O(n), it could further be sped up to O(log n) by using a divide and conquer pattern to determine if the 1 dimensional point exists in the line.
BloggingContext.ApplicationInstance.CompleteRequest();
