Вопрос по polygon – Очень полное и приятное объяснение! Спасибо за это, я понял :)

0

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

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

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

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

ура

Ваш Ответ

1   ответ
1

я дам вам помощь в выполнении домашнего задания.

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

ОБНОВИТЬ:

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

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

Сумасшедший ленивый псевдокод:

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).

Я не знаю, правильно ли я понял: let s - начальная вершина let l - последняя вершина mid = (s + l) / 2, поэтому t [mid-1] t [mid] t [mid + 1] образует треугольник, если точка находится в треугольнике: она в многоугольнике, если точка имеет более низкие координаты (x (?) и y (?)), продолжайте поиск в l = s; S = S; если выше - наоборот. Я правильно понял? Спасибо за хорошую идею. Krzysztof Lewko
Извините но нет. Сначала выполняйте бинарный поиск до тех пор, пока у вас не появятся две смежные вершины, так что луч от фермера к вершине a находится слева от овцы, а луч от фермера к вершине b справа от овцы. На самом деле вы можете просто использовать фермера a, b в качестве ограничивающего треугольника (игнорируйте клин, обращенный назад к вам, в этом нет необходимости). В остальном ты получил права. ccoakley
Я обновил свой ответ. Все понятно? ccoakley
Эй, спасибо за ответ. Это не моя домашняя работа, просто хобби. И не могли бы вы разработать этот метод двоичного поиска? Я читал, что мы должны делать интервалы и искать свою точку зрения, но я не мог найти, насколько велики интервалы и просто, что дальше? :) Krzysztof Lewko
Очень полное и приятное объяснение! Спасибо за это, я понял :) Krzysztof Lewko

Похожие вопросы