A Programming Job Interview Challenge #14

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();

Advertisements

One thought on “A Programming Job Interview Challenge #14

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s