Поиск луча, который пересекает многоугольник как можно чаще

Вот интересное упражнение:

Пусть P - простой, но не обязательно выпуклый многоугольник и q - произвольная точка, не обязательно в P.

Создайте эффективный алгоритм, чтобы найти отрезок линии, исходящий из q, который пересекает максимальное количество ребер P.

Другими словами, если вы стоите в точке q, в каком направлении вы должны прицелиться в пушку, то пуля пройдет через наибольшее количество стен?

Пуля через вершину Р получает кредит только для одной стены.

Алгоритм O (n log n) возможен. n - количество вершин или ребер, так как это многоугольник, число ребер примерно равно числу вершин.

Вот моя мысль:

Соедините q со всеми вершинами (скажем, есть N вершин) в P вначале. Будут N строк или N-1 пар линий.

Конечная линия стрельбы должна находиться между этими парами. Поэтому мы должны найти пару, которая содержит наибольшее количество ребер.

Я не думаю, что это решение - O (n log n).

Любые идеи?

Ответы

Ответ 1

Ну, сначала преобразуйте координаты точек в полярную систему с центром в P.

  • Без ограничения общности можно выбрать направление по часовой стрелке как специальное по отношению к координате угла.
  • Теперь давайте проведем круговую прогулку по всем краям многоугольника и заметим начальную и конечную точки этих ребер, где прогулка ведет нас по часовой стрелке относительно P.
  • Позвольте называть конечную точку такого ребра a 'butt' и отправной точкой a 'head'. Это все должно быть сделано в O (n). Теперь нам придется сортировать эти головы и приклады, поэтому с быстрой сортировкой это может быть O(nlog(n)). Мы сортируем их по координате угла (φ) от наименьшего φ вверх, следя за тем, чтобы в случае равной φ координаты считались меньшими, чем приклады (это важно для соответствия последнему правилу проблемы).
  • Как только мы закончим, мы начнем их с наименьшего числа φ, увеличивая текущую сумму всякий раз, когда мы сталкиваемся с прикладом, и уменьшаемся всякий раз, когда сталкиваемся с головой, замечая глобальный максимум, который будет интервалом по координате φ. Это также должно быть сделано в O (n), поэтому общая сложность O(nlog(n)).

Теперь вы могли бы рассказать мне, почему вы задаете такие вопросы?

Ответ 2

Я использовал алгоритм Бориса Ститницкого и написал свое решение на Java. Но я выбрал направление против часовой стрелки и чтобы проверить, какая точка интервала является начальной точкой, а какая точка - конец интервала, который я использовал в перекрестном продукте. Вы можете найти его здесь: https://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java