rock_lee's blog

Point Inside a polygon O(lg n)
By rock_lee, 11 years ago, In English

Can anyone please help me with a tutorial on "How to check whether a point inside a Convex polygon " with complexity O(lg n). I know the O(n) approach which use ray casting algorithm. But i need a better approach for solving a certain problem. Thnx in advance :) .

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

One possible solution is to choose some point of the polygon (the lowest and leftmost point fits perfectly), draw all the diagonals outcoming from it and split the polygon into triangles and the plane into infinite sectors. Now for an arbitrary point you can find the sector, in which it lies, using a binary search. Finally, you need just to check if a point lies inside the corresponding triangle.

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Well, the idea of O(logN) derives from the ray algorithm. You need to consider that if you launch a ray algorithm, you will get at most 2 crossings ( polygon is convex). So if you get the leftmost and the rightmost points and divide the polygon in 2 parts — an upper part and a lower part(just imagine that you have a line between these to points). Now, if you use a vertical ray to to check crossing all you need is to do a binary search in both parts and check for crossings only with the segment(or vertex) containing the 'x' value of the point. Note that both parts of the polygon are sorted by x due to the input and the division of the polygon. Lower part will be ascending and upper part would be descending or the opposite, depending on the direction of input(clockwise or counter-clockwise). I hope my explanation was clear enough. If you have any other questions be free to ask.

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Bare with me, i'm thinking out loud. Lets say we have a polygon P with N vertices and the point we want to check is called k. You find a diagonal on that poligon that separates P in P1 and P2, each with n/2 vertices (can be 1 less, but you get the idea). Lets call the ends of the diagonal e1 and e2. Now we can check in which part of polygon the point would be, by checking counter-clockwise rotation with points (e1,e2 and k). We can get the idea where the point could be and solve the same problem on a smaller (decreases by half) polygon. At the end, we will reach a polygon that looks like a triangle. Now we can check in constant time (3*counter-clockwise) if the point is inside the triangle by taking every 2 adjacent ends and doing counter-clockwise check and if for all pairs, the point is inside the triangle then it is inside our original polygon.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain the rotation part more specifically and bare in mind that the rotation itself is a slow operation.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      you don't actually rotate anything, you can imagine this operation like this: between the diagonal points draw an infinitely long line (that line splits everything in 2 parts). Now what you want to know is in which part the point k could be. Checking this takes constant time:

      # Three points are a counter-clockwise turn if ccw > 0, clockwise if
# ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
# gives the signed area of the triangle formed by p1, p2 and p3.
function ccw(p1, p2, p3):
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)
      → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you all for sharing your's idea . I will try to implement it.
Thnx again :) .

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -22 Vote: I do not like it

Don't discuss about problems during contest. Edit: Oh wait, sorry, I've mixed with an other contest who was on e-olimp. He's already finished, so no problem.

→ Reply