The fourteenth post of the series of programming job interview challenge is out, 83 readers provided an answer to job interview challenge #13. We didn’t publish a question last week due to a sever lack of time, so another week is gone and here we are again.

Mark R was the first to provide a correct and detailed answer (which I can quote here):

As you examine each character, classify it as either an opening or closing bracket. If it’s an opening bracket, push it onto a stack. If it’s a closing bracket, pop the top character off of the stack; if the stack was empty, or the character was not the matching open bracket, then return an error. At the end of input, if the stack is empty, you have a legal expression.

C++ has a built-in stack class, so this becomes a trivial problem. I’m not sure about other languages. You could always simulate a stack by appending and deleting characters from the end of a string.

So, in one word, the most efficient answer is use a stack. Here is a nice image which was crafted by David Tchepak in his blog post Brackets, braces, parentheses, and other such creatures:


Those are other blog entries where you can find answers to the brackets question:

  1. by James Curran.
  2. by unknown.
  3. by Alex moskalyuk.
  4. by Levi.
  5. by Jon von Gillern.
  6. by Xerxes Battiwalla.
  7. by Hugh Brown.
  8. by DaveG.
  9. by ZagNut.
  10. by Claudio Cherubino.
  11. by gav.
  12. by Richard Harrison.
  13. by Oliver Reeves.
  14. by Hegi.
  15. by Norbert Rakosi.
  16. by Chris Marisic.
  17. by unknown.

Those are the readers who provided correct answers in the form of a comment: sirrocco, Omar, Jason Kikel, Trinity, Justin Etheredge, Michael Mrozek, Nate, Kevin Hjelden, Jeremy Weiskotten, Alex, S Javeed, Steven Baker, leppie, Morgan Cheng, Hello world, herval, Samuel Williams, dextar, macmariman, Darrell Wright, Ryan, Shams Mahmood, Kimmen, Terje Myklebust, Jelle Hissink, Matt Howells, Dave Amphlett, Mark Brackett, configurator, Tim Kington, valera, Christof Jans, Michael, Richard Vasquez, Gerhard Balthasar, Daniel Jimenez, ilitirit, Sayre, Dejan Dimitrovski, Phi, Arni Hermann, Carl Anderson, bartek szabat,  Klemen K., Petar Petrov, Niranjan Viswakarma, Michael Dikman, Alessio Spadaro, Santa, Marcos Silva Pereira and Joost Morsink.

This Week Question:

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. Here is an example of a point which is outside the polygon:


Provide the most efficient and simple algorithm. Please don’t provide Code snippets alone (without explanation), I don’t know each and every programming language… :) words will be enough.

Get updates by RSS to catch up with the next posts in this series and to get the correct answer for today’s question. As always you may post the solution in your blog or comment. Comments with answers will be approved only next week.

Tags :

46 Responses to “A Programming Job Interview Challenge #14 – 2D Geometry”

  1. Omar

    Said on August 5, 2008 :

    Draw a line from the single point (any direction will do).
    Count the number of times that this line intersects with lines of the polygon.
    An even count (including zero) indicates that the point is outside of the polygon.
    An odd count indicates that the point is inside the polygon.

  2. David

    Said on August 5, 2008 :

    1) Find all line segments that intersect the horizontal line that the point is on (same y value).

    2) For each of those segments, interpolate the x value for the point where it crosses the horizontal line that the point is on then add that value to a list.

    3) Sort the list.

    4) For each pair of values in the list, check if the x value of the point is at or between those 2 values. If it is the point is inside the polygon.

  3. Tristan

    Said on August 5, 2008 :

    It has been a while since i have done a line fill algorithm, but as I remember you create a list/ table of edges(sorted by low y, low x), you can then discard (or not add) all edges that begin and end below the point in question, same for above.

    so now we could have a shape such as

    \//\\||||//\\ .

    the first step is to check and make sure the point is to the right of the first line in the table. the second step is that it is to the left of the last edge in the table.

    if it isnt, it is outside the table and we end.

    if it is we introduce a state variable, inOrOut.

    we then use simple math (y=mx+b) to find the relevant points on each entry in the table.

    initial state is out. we cross the first entry in the table at {(y[point]-b)/m,y[point]} and switch the state (inOrOut = !inOrOut) we then calculate the x,y position of the next intercept. since we are at the same level of y, we compare the values of x to the point. if it is less than or equal to the intercept point, than the point is in. if it is greater than we switch the state to out and we repeat this step until the point is found giving the point the state held in inOrOut.

  4. Joost Morsink

    Said on August 5, 2008 :

    A point is never in a shape of zero, one or two points.

    If the shape is convex it is easy:
    1. map the points to line segments
    2. map the line segments to lines
    3. the given point needs to be on the same side of the line for every given line for it to be in the convex shape.

    For concave shapes, the shape needs to be split up into convex shapes, and the given point must lie in one of the convex shapes, calculated as follows:
    1. Start with the first three points in the list.
    2. Keep the first point as a fixed point
    3. If the angle between 1st-2nd < angle between 1st-3rd, don’t include the triangle, otherwise do.
    4. If the traingle was included, repeat.
    4b. Otherwise, make the current second point the new fixed point and take the next two from the list for the second and third and repeat.
    5. When the list has no more points, take the first point once more and repeat, then stop.

    6. Repeat for a list of all the points that have been the fixed point in the previous iteration.

    That’s about it, I think.

  5. Michael Mrozek

    Said on August 5, 2008 :

    Find the minimum and maximum X and Y for the polygon (that is, the bounding rectangle that encloses the polygon). If the point is outside that rectangle (x maxX || y maxY), the point is outside the polygon. Otherwise, draw lines from the point to points outside the bounding box on each side. Count the number of times each line crosses a vertex of the polygon. If any line crosses an odd number of vertices, the point is inside the polygon; if they all cross an even number, the point is outside

  6. Jonathan Starr

    Said on August 5, 2008 :

    I will post a more rigorous solution on my web site, but this is my most efficient solution (should be sufficient I think).

    1. Get any random point that is not collinear with the point in question (the one you do not know is inside or outside the shape) and any one of the vertices of the shape. Create a ray from the point in question through this arbitrary point.

    2. Check for intersection between this ray and all of the line segments that make up the shape.

    3. If the number of intersections is an even number, then the point in question is outside the shape. Otherwise it is inside.

    Voila! I hope that is satisfactory (it was for me).

    Thanks for the sweet!!!! problem.

    Jonathan Starr

  7. Mark R

    Said on August 5, 2008 :

    Hey, thanks for the quote! And now you follow it up with a question I first solved 30 years ago…

    Go through each segment of the polygon and determine if it intersects the point on the y axis, excluding the higher of the two endpoints (min(Y0,Y1) <= Yp < max(Y0,Y1)). If it intersects, calculate the X coordinate of the intersection; if it is equal to the X coordinate of the point, the point lies on the boundary of the polygon and should be considered inside. If it isn’t equal, increment a counter if it is less than the X coordinate of the point. When you are finished with all of the segments, the point is inside if the count is odd, and outside if the count is even.

    Excluding the maximum Y coordinate of each segment avoids some special cases, when the segment is horizontal or the point is at the intersection of two segments.

    A small optimization can be made when comparing the X coordinates – if both endpoints of the segment are greater than the point, the segment can be ignored, and if both are less than the point, you can increment the count without calculating the intersection.

  8. Chris Marisic

    Said on August 5, 2008 :

    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;

    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.

  9. Michael Russell

    Said on August 5, 2008 :

    Well, your description misses the corner case of if the point is on one of the lines, but I would first check to see if the point is outside of (minX, minY)-(maxX, maxY) to fail fast.

    I would then create a line segment from (minX, pointY) to (pointX, pointY) and count the number of line segments that intersect with it.

    If the count is even, the point is outside. If the count is odd, the point is inside.

  10. Dejan Dimitrovski

    Said on August 5, 2008 :

    For now I only now half of the solution, which would only work IF all of the angles of the final polygon do not exceed 180 degrees. In that case the solution is to find if the XY coordinates of the testing point are within the range Xmin < X < Xmax and Ymin < Y < Ymax, where XYmin/max are the smallest/largest values in the list of the provided polygon coordinates.

    Looking forward to seeing the full solution

  11. redge

    Said on August 5, 2008 :

    There’s a simple and quite elegant solution for this problem. I can’t say that it is was my idea, though — I read about it a while ago.

    Starting at the single point, create a very long line segment. A useful approach could be a segment parallel to the x-Axis, starting at the single point and reaching far to the right.

    Now calculate the intersections between this line segment and all the line segments that form the shape. When you are finished, just count the intersections: when there is an even number of intersections, you are outside the shape — an odd number signifies that you are inside.

    That’s it!

  12. buzzard

    Said on August 5, 2008 :

    Computational Geometry in an interview?

  13. Jon von Gillern

    Said on August 5, 2008 :

  14. Tim Kington

    Said on August 5, 2008 :

    Draw a line from the point to the outside of the polygon, and count how many lines you cross. If the number is even, it’s on the outside.

  15. Gabriele Cannata

    Said on August 5, 2008 :

    A simple way is to “draw” a line from the point and intersecting at least an edge of the polygon (for example taking a median point of two vertex). Then we could count how many edges this line will cross (with simple line-segment intersection algorithm). If the number of intersection is even, the point is outside. If it’s odd it’s inside.

  16. Alex

    Said on August 5, 2008 :

    If the point is well and truly within a polygon, than a line drawn from that point in any direction will cross the borders of that polygon an odd number of times- For example, it will either leave the polygon once, or leave, re-enter due to some funky polygon angle, but eventually leave again. If the point is NOT in the polygon, it will either cross 0 borders, or enter and leave again, or enter,leave,enter again, and leave again. You get the idea.

    Run through the list once, and get an xmax, ymax, xmin, and ymin (So we’re not drawing this line all the way out into infinite).

    Then, “draw” 4 lines from the point being evaluated.
    point.x,point.y -> point.x,ymax + 1
    point.x,point.y -> xmax + 1,point.y
    point.x,point.y -> point.x, ymin – 1
    point.x,point.y -> xmin – 1,point.y
    (I added those +1 and -1′s just to make sure there’s no confusion if the line ends directly on one of those listed points.

    Now, for each of these 4 lines, check if they intersect any of the lines provided in the list of points which make up the polygon. Determining whether two lines intersect or not can be done in constant time.

    Keep a counter for the number of times each of these 4 test lines crosses a polygon boundary. If that number odd for every test line, the point in question is inside a polygon.

    Of course, this all depends on what you mean by “efficiency”. If the question is how fast you can write the code, it’s an entirely different solution:

    Programatically draw a white box. Draw the polygon inside it using those coordinates. Use the programmatic equivalent of the bucket tool to fill the area near pixel 0,0 (top left in programming terms) green.

    Then check the pixel in question. If the area at those coordinates are green, return false, since the bucket can’t cross line boundaries:D

  17. steven

    Said on August 5, 2008 :

    this is a simple collision detection algorithm.

    you really need to come up with original questions.

  18. Morgan Cheng

    Said on August 6, 2008 :

    The easiest way is to sum up all angles of given point and neighboring vertex points. If given point is inside the polygon, the sum of the angles should be 360 degrees (2*Pi); if it is out of the polygon, the sum is supposed to be zero. The time complexity is O(n), assuming Math.Atan2 is O(1). The space complexity is O(1).

    Below is the code. Since the sum may be inaccurate for large of double numbers, the angleSum might not be 2*Math.PI or 0 exactly, so I just check compare it with Math.PI.

    public static bool CheckPolygon(Point[] polygonPoints, Point point)
    double angleSum = 0.0;

    for (int i = 0; i Math.PI)
    angle -= 2 * Math.PI;
    while (angle < -Math.PI)
    angle += 2 * Math.PI;

    angleSum += angle;

    return (Math.Abs(angleSum) < Math.PI);

  19. Shahar Y

    Said on August 6, 2008 :

    @ buzzard
    You are not required to provide the equations needed to solve the question, just describe it in words. It is a “thinking” problem.

  20. Carl Anderson

    Said on August 6, 2008 :

    Moving clockwise around the polygon, we extend each line infinitely and think of it as [a vector] pointing in the direction from the first point of the line to second point. Then we take the point and determine whether it is to the left or to the right of our line, with respect to the line’s direction. If the point is to the right of all the lines, it is within the polygon.

    Code-wise here is the relevant method:
    // isLeft(): tests if a point is Left|On|Right of an infinite line.
    // Input: three points P0, P1, and P2
    // Return: >0 for P2 left of the line through P0 and P1
    // =0 for P2 on the line
    // <0 for P2 right of the line
    inline int
    isLeft( Point P0, Point P1, Point P2 )
    return ( (P1.x – P0.x) * (P2.y – P0.y)
    – (P2.x – P0.x) * (P1.y – P0.y) );

  21. Stefan M

    Said on August 6, 2008 :

    Fire a beam from the single point into any direction. Calculate the number of intersections with the sides of the polygon.

    #intersections=even => point is outside
    #intersections=odd => point is inside

    0 intersections count as even.
    Special case: the beam hits a corner of the polygon.
    In this case do not count the hit when the corner point is a local minimum or maximum, i.e. the neighbour points of the hit polygon corner point are on the same side of the beam.

  22. Ahmad

    Said on August 6, 2008 :

    A “theoretical” solution.
    -Take a point A known to be inside the polygon.
    -Connect this point A with the given poiint
    - if the line intersects the polygon edge, the given point is outside otherwise inside.
    (The problem with this solution is how to determine the first point is inside the polygon..recursive problem :D )

  23. Jon von Gillern

    Said on August 6, 2008 :

    Shahar, I bet you’d get more traffic if you added a “kick it” button from

  24. Andrew

    Said on August 6, 2008 :

    Course grain the 2D space and determine the maximal/minimal values on each axis to provide a simple mapping from the problem space to a finite canvas of pixels; include at least one pixel padding in the canvas so the edges are less than and greater than the minimal and maximal values respectively. Initialize the canvas’ pixels with color0, then plot the lines using color1. Next flood fill the canvas, using color2, staring from the pixel that maps to the single point given in part 2 of the problem statement. Now, just test any edge pixel: if any edge pixel is color2 then the point is exterior; otherwise it is interior.

    Any decent line plotting and flood fill algorithms will work.

    An algorithm is required to determine a suitable course graining. If the point maps to a pixel colored with color1 (the color of the lines) then finer course graining is required; otherwise the current course graining is fine enough. An iterative approach of re-attempting the solution, with finer course graining on each iteration until a suitable one is found, would work.

    If the 2D points are given as integer values then there is an obvious mapping to a canvas, but with large values it would still make sense to find a suitable course graining.

    The above algorithm has terrible worse case behavior. But, if the point is not very close to any line then it should work in a reasonable time.

    I’m sure that this is not the ‘correct’ solution the author has in mind, but I’m stuck on trying to reduce the problem to simpler parts.

  25. Shahar Y

    Said on August 6, 2008 :

    @ Jon von Gillern
    We (Dev102 team) will discuss about it tomorrow, thanks for your advice and involvement :)

  26. Niki

    Said on August 6, 2008 :

    If you test only one point, I don’t think you can get better than O(n), where n is the number of lines. An algorithm could look like this:
    Iterate through each line in the polygon
    Let the line go from points P1-P2:
    Test if the point Q in question is inside the triangle 0-P1-P2, where 0 is the origin (0,0).
    Count the number of triangles that contain Q. If Q is contained in an even number of triangles, it’s outside the polygon, otherwise it’s inside.

    (Triangle hit-testing is a lot easier, because triangles are always convex. I leave it as an exercise to the reader ;-) )

    If you test many points with respect to the same polygon, sorting the points and using a plane-sweep algorithm might be more efficient.

  27. Erik

    Said on August 6, 2008 :

    What I would do is to create an array of triangles using the array of points as input; then for each triangle, determine if the reference point is inside the triangle geometrically; if none of these triangles contain the reference point, then the point lies outside the polygon; otherwise, if one of the triangles does contain the point, then the polygon contains the point.

    - for cutting a polygon up into triangles:

    - for determining if a point lies inside an individual triangle:

  28. Marc Melvin

    Said on August 6, 2008 :

    I don’t have time to get into the math involved while I’m at work (snicker), but I’m sure someone else will do that sooner or later. Conceptually, however, starting at the point specified, you need to calculate a vector in any direction and determine the number of lines that the vector intersects. If the number of intersections is odd, then you are inside the polygon. If it is even, you are outside the polygon.

  29. Kevin Pang

    Said on August 6, 2008 :

  30. Ian Qvist

    Said on August 6, 2008 :

    This could be done by ray testing.

    By using ray testing, you make a line that goes from the point (x,y) and in any direction to the outside of the boundary of the polygon. as an example, we could just let this line go straight down.
    Then we count the number of times the line passes a side of the polygon. If the number of times it crosses a line is an odd number, then the point is outside the polygon. An even number means it’s inside the polygon.

    This kind of testing would have problems if the point we test for is on the edge of the polygon.

    There is also other solutions to this problem. Some needs the polygon to be convex, some sums up the angles relative to the point, but the ray testing is the simplest by far.

  31. Ian Qvist

    Said on August 6, 2008 :

    Oh, I’m not sure if it is a requirement to post source code, but there is some that works in XNA 3.0 and .NET 3.5 written in C#:

    public static bool Inside(Vector2 point, Vector2[] polygons)
    Vector2 tempP1, tempP2;
    bool inside = false;

    if (polygons.Length < 3)
    return false;

    Vector2 lastPoint = new Vector2(polygons[polygons.Length - 1].X, polygons[polygons.Length - 1].Y);

    for (int i = 0; i lastPoint.X)
    tempP1 = lastPoint;
    tempP2 = currentPoint;
    tempP1 = currentPoint;
    tempP2 = lastPoint;

    if ((currentPoint.X < point.X) == (point.X <= lastPoint.X)
    && ((long)point.Y – (long)tempP1.Y) * (long)(tempP2.X – tempP1.X)
    < ((long)tempP2.Y – (long)tempP1.Y) * (long)(point.X – tempP1.X))
    inside = !inside;
    lastPoint = currentPoint;
    return inside;

    The code could be optimized by not using the expensive multiplications, but it works relative fast.

    And as an added bonus, I’ve uploaded a picture of the good old red (outside) versus blue (inside) test of the algorithm:

  32. Catalin

    Said on August 6, 2008 :

    I describe the solution in my (newbie) blog

    The core of the algorithm is: count the intersections of a ray originating in the input point with the polygon

  33. Andy

    Said on August 7, 2008 :

    You haven’t specified whether the polygon can be re-entrant (i.e. the edges can intersect, forming a ‘loop’). A point inside the loop is outside the polygon’s boundary, but inside the closed region.

  34. Kimmen

    Said on August 7, 2008 :

    The first solution I remembered was for convex polygons, but I didn’t remember the solution which works for concave polygons as well. It ended up with me cheating using google =P. Then it struck me that the solution I learned in school was the ray-casting solution. You cast a ray from the point through the polygon. If the ray crosses even number of edges, the point is outside otherwise it’s inside.

  35. Shahar Y

    Said on August 7, 2008 :

    @ Andy
    The polygon edges can not intersect.

  36. leppie

    Said on August 7, 2008 :

    The simplest solution is just to use GraphicsPath and Region in .NET :)

    I will think of a real solution during the day ;p

  37. Valera KOlupaev

    Said on August 7, 2008 :

    The solution:
    Draw imaginative beam from target point, for example to the left, and count number of intersections with polygon edges.
    If counted number is even – target point is outside of the polygon and vice versa.

    This algorithm have some problems in joints, but we can skip joints which formed by lines that all placed below or above target point.


    def assert
    raise “Assert Error” unless yield

    class Point
    attr_accessor :x, :y

    def initialize(x, y)
    @x = x;
    @y = y;
    def sub(pt)
    return – @x, pt.y – @y)
    def to_s()
    return @x.to_s + “, ” + @y.to_s + “; ”

    class Poly
    attr_accessor :points
    def initialize(points)
    @points = points;

    def self.isCross(pt1, pt2, pt0)
    swapped = false

    if pt1.x > pt2.x
    t = pt1
    pt1 = pt2
    pt2 = t
    swapped = true

    return :corner if (pt0.x < pt2.x and pt2.y == pt0.y and not swapped) or (pt0.x < pt1.x and pt1.y == pt0.y and swapped)
    return :false if (pt0.x < pt2.x and pt2.y == pt0.y and swapped) or (pt0.x < pt1.x and pt1.y == pt0.y and not swapped)

    return :true if pt0.x [pt1.y, pt2.y].min and pt0.y pt2.x or pt0.y [pt1.y, pt2.y].max

    # actually corner, but it was checked before
    return :false if pt2.y == pt1.y

    dx = (pt2.x – pt1.x) * (pt0.y – pt1.y) / (pt2.y – pt1.y)
    return :true if dx + pt1.x > pt0.x and dx + pt1.x pt.y and npt.y < pt.y) or (ppt.y pt.y)
    count = count + 1
    print “Error”

    print count , “\n”
    return true if count.modulo(2) == 1
    return false

    poly =[, 5),, 9),, 9),, 5),, 3),, 2)])

    inPoly = [, 6),, 5),, 7)]

    outOfPoly = [, 2),, 5),, 6)]

    inPoly.each {|pt| assert {poly.inPoly(pt) == true}}
    outOfPoly.each {|pt| assert {poly.inPoly(pt) == false}}

  38. Maneesh Chaturvedi

    Said on August 7, 2008 :

    One simple way would be to perform the following checks
    1) Check that the x co-ordinate of the given point(p) lies within the maximum and minimum x co-ordinates of the list of points. If it does not then return false.
    2) Similarly perform a check for the y co-ordinate. If it does not lie between the minimum and maximum values, return false.
    3) If the point(p) equals any given point(x=x1 and y=y1) within the list of points return true.
    4) Take the point(p1) in the list with the minimum value of y. Calculate the slope from this point to the given point(p) using s=y2-y1/x2-x1. Also calculate the slope of the adjacent points lets say p2 and p3. If the slopes are s1 and s2 and s lies between s1 and s2, then the point lies within the polygon, else it lies outside the polygon.

  39. Kivanc Ozuolmez

    Said on August 7, 2008 :

    Hi all,

    Here is my solution :

    I didn’t mind about the points which are exactly on the edges (It is not mentioned in the question though) but, for the others my code seems working.

  40. Shams Mahmood

    Said on August 7, 2008 :

    We need to breakdown the polygon into triangles by creating appropriate diagonals. Need to handle the vertex having a concave angle specially while forming these triangles.
    Once we have the set of triangles we can use line equations of the sides of the triangles and the center point of the triangle (average of the vertices of the triangle) to determine whether the given point is inside this triangle or not.

  41. leppie

    Said on August 8, 2008 :

    OK, serious attempt :)

    1. Create a function of each line in order, iow f(x) = ax + b.
    2. Create a function of each line from the start point to the single point, say g(x).
    3. Compare each function (in 1) gradient to the gradient of the function (in 2). Normalize the gradient, multiply the sign of f(x)’s gradient with both gradients.
    4. If all comparisons are f(x)’s gradient < g(x)’s gradient, the point will be inside, else outside.

    I think that will work, too lazy to test :)

  42. Ngu Soon Hui

    Said on August 8, 2008 :

  43. Xerxes

    Said on August 10, 2008 :


    I’ve submitted a solution to the 14th Challenge on my website.


3 Trackback(s)

  1. Aug 6, 2008: Catalin’s Zeroes and Ones » Blog Archive » Programming Challenge: 2D Geometry
  2. Aug 11, 2008: A Programming Job Interview Challenge - The End |
  3. Sep 11, 2008: DEV102 - AUGUST 2008 BLOG STATS |

Post a Comment