0

I'm trying to do some SPOJ problem it's https://www.spoj.pl/problems/FSHEEP/

We have to find out if point is inside the polygon. As we see it's not convex polygon ( image from problem ).

I was trying to solve it in O(n*m) time with Ray Casting algorithm described on wikipedia or any other site.

But how to solve it in O(n log m ) ? So in other words how to check if point is in polygon in logarithmic time?

Nimantha
  • 6,405
  • 6
  • 28
  • 69
Krzysztof Lewko
  • 982
  • 7
  • 24

1 Answers1

1

Since this is a homework-esque problem, I'll give you homework-esque help.

Rule of thumb: Whenever you see log n, you should think "binary-something" (search, tree, etc). When you see n log n, you should think "sort." You'll be surprised how often that works. Can you sort the vertices and binary search on them within your big-O constraints?

UPDATE:

I didn't want to spoil your fun: You are actually given the polygon vertices in sorted order, so the important sorting was done for you. You don't need to make an interval in angle-space, use the indexes of the sorted vertex array as your interval.

Cast your ray out from the farmer to the vertex. If it is clockwise, binary search clockwise. If it is anti-clockwise, binary search that direction. The two vertices and the farmer form a bounding triangle. Is the sheep in the bounding triangle?

Crazy lazy pseudocode:

if vertex[m] and vertex[0] trivially bound the sheep
  l=m, r=0
else
  l=0, r=m
  while (r-l > 1)
    middle = (r-l)/2
    if vertex[l] and vertex[middle] bound sheep
       r = middle
       continue
    else if vertex[middle] and vertex[r] bound sheep
       l = middle
       continue
    else some_jerk_gave_you_a_sheep_on_a_ray

check vertex[l],vertex[r],farmer triangle

Binary search is O(log m). The triangle check is O(1). Iterating over n sheep gives you O(n)*O(log m)*O(1) = O(n log m).

ccoakley
  • 3,235
  • 15
  • 12
  • Hey, thanks for answer. It's not my homework, just hobby. And could you elaborate this binary search method ? I've read that we have to make intervals and search for our point, but i couldn't find how big intervals and simply what's next ?:) – Krzysztof Lewko May 23 '11 at 18:34
  • I don't know if i understood correctly : let s - start vertex let l - last vertex mid=(s+l)/2 so t[mid-1] t[mid] t[mid+1] forms a triangle, if point is in triangle : it's in polygon, if point has lower coords ( x (?) and y (?) ), keep searching in l=s; s=s; if higher - vice versa. Did i understood correctly ? Thanks for nice idea. – Krzysztof Lewko May 23 '11 at 20:12
  • 1
    Sorry, no. First do the binary search until you have two adjacent vertices such that the ray from the farmer to vertex a is to the left of the sheep and the ray from the farmer to vertex b is to the right of the sheep. You can actually just use the farmer, a, b as a bounding triangle (ignore the wedge facing back at you, that is unnecessary). The rest you got right. – ccoakley May 23 '11 at 20:22
  • Very full and nice explaination ! Thanks for it i got it :) – Krzysztof Lewko May 23 '11 at 20:41
  • I eventually get there :) Thanks for being patient with me. – ccoakley May 23 '11 at 20:42
  • Be careful with off-by-one errors. My pseudocode uses both 0 and m as indices. That's probably 0 and m-1 in practice. Finally, the co-linear case is more complicated than I implied. Since you are possibly using floats, you should be aware that sometimes due to imprecision, you can get a point that is both to the right AND to the left of a line (or neither). Both are typical tests for co-linearity. This is usually presented in computational geometry textbooks as a gotcha. It's possible you don't care right now. Just be aware that it happens. – ccoakley May 23 '11 at 20:48
  • For checking colinearity we can use cross-product, can't we ? – Krzysztof Lewko May 23 '11 at 22:14
  • Depends on how small you are willing to accept an epsilon away from zero. Remember that since floating point numbers are not exact, multiplying them and adding them in different ways can produce different results, even for mathematically equivalent statements. A google search on "Robustness in Computational Geometry" can provide you with a rich source of examples. – ccoakley May 24 '11 at 01:11