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

Question

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

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

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

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

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

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

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

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

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

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

Любые идеи?

Answer 1

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

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

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

Answer 2

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