arjun17's blog

Point In Convex Polygon.
By arjun17, history, 6 years ago, In English

Is there any way for checking a point strictly inside a convex polygon in O(1)?

I know the logarithm technique.

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

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share O(log n) Solution ?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Let p1, ..., pn be points of polygon in clockwise order.

    Now you're given point q and have to check whether it lies in polygon. At first check that it lies in angle formed by points p2, p1, pn. If that's false, then answer for sure is no. Otherwise let's notice that function "f(i) =  is it true that triplet (p1, pi, q) is right-orientated" is monotone (i.e. it's always true at first, then always false). Do binary search on i checking the condition using orientated triangle area. After you've found the first i such that triplet (p1, pi, q) is left-orientated, check that q is in triangle p1, pi - 1, i. Done!

    → Reply