Точка в многоугольнике - PullRequest
Новая
       24

Точка в многоугольнике

0 голосов
/ 23 мая 2011

Я пытаюсь решить проблему с SPOJ, это https://www.spoj.pl/problems/FSHEEP/

Мы должны выяснить, находится ли точка внутри многоугольника. Как мы видим, это не выпуклый многоугольник (изображение из задачи).

Я пытался решить это за O (n * m) время с помощью алгоритма Ray Casting, описанного в Википедии или на любом другом сайте.

Но как решить это в O (n log m)? Другими словами, как проверить, находится ли точка в многоугольнике в логарифмическом времени?

Приветствия

1 Ответ

1 голос
/ 23 мая 2011

Поскольку это проблема домашнего задания, я дам вам помощь в выполнении домашнего задания.

Правило: всякий раз, когда вы видите журнал n, вы должны думать «что-то двоичное» (поиск, дерево и т. Д.). Когда вы видите n log n, вы должны думать «сортировать». Вы будете удивлены, как часто это работает. Можете ли вы отсортировать вершины и выполнить бинарный поиск по ним в рамках ограничений big-O?

UPDATE:

Я не хотел портить вам веселье: вы фактически дали вершины многоугольника в отсортированном порядке, поэтому важная сортировка была сделана для вас. Вам не нужно создавать интервал в угловом пространстве, используйте индексы отсортированного массива вершин в качестве интервала.

Изгони свой луч от фермера к вершине. Если это по часовой стрелке, бинарный поиск по часовой стрелке. Если это против часовой стрелки, бинарный поиск в этом направлении. Две вершины и фермер образуют ограничительный треугольник. Находятся ли овцы в ограничительном треугольнике?

Безумный ленивый псевдокод: 

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

Двоичный поиск - O (log m). Проверка треугольника - O (1). Итерирование по n овам дает O (n) * O (log m) * O (1) = O (n log m).

...