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

Question

Алгоритм O (n) для определения того, пересекает ли линия выпуклый многоугольник, состоит в проверке, пересекает ли какой-либо край многоугольника линию, и проверяет, является ли количество пересечений нечетным или четным.

Isсуществует асимптотически более быстрый алгоритм, например O (log n)?

Answer 1

LHF ответ близок к правильному.Вот версия, которая должна решить проблему с его.

Пусть у многоугольника есть вершины v0, v1, ..., vn против часовой стрелки.Пусть точки x0 и x1 находятся на прямой.

Обратите внимание на две вещи: во-первых, найти пересечение двух линий (и определить его существование) можно в постоянное время.Во-вторых, определение, находится ли точка слева или справа от линии, может быть выполнено за постоянное время.

Мы будем следовать той же базовой идее lhf, чтобы получить алгоритм O (log n).Базовые случаи, когда многоугольник имеет 2 или 3 вершины.Оба могут обрабатываться в постоянное время.

Определить, пересекает ли линия (v0, v (n / 2)) линию (x0, x1).

Случай 1:Они не пересекаются.

В этом случае интересующая нас линия находится либо слева, либо справа от линии, разделяющей многоугольник, и поэтому мы можем вернуться в эту половину многоугольника.В частности, если x0 находится слева от (v0, v (n / 2)), то все вершины в правой «половине», {v0, v1, ... v (n / 2)} находятся на одной сторонеof (x0, x1), и поэтому мы знаем, что в этой «половине» многоугольника пересечения нет.

Случай 2: Они пересекаются.

Этодело немного сложнее, но мы все же можем сузить пересечение до одной «половины» многоугольника за постоянное время.Есть 3 случая:

Случай 2.1: Пересечение между точками v0 и v (n / 2)

Мы закончили.Линия пересекает многоугольник.

Случай 2.2: пересечение ближе к v0 (то есть вне многоугольника на стороне v0)

Определите, является ли линия (x0, x1) пересекается с прямой (v0, v1).

Если это не так, то мы закончили, линия не пересекает многоугольник.

Если это так, найдите пересечение, с.Если p находится справа от линии (v0, v (n / 2)), тогда вернитесь в правую «половину» многоугольника, {v0, v1, ..., v (n / 2)}, в противном случае рекурсивнослева "половина" {v0, v (n / 2), ... vn}.

Основная идея в этом случае состоит в том, что все точки в многоугольнике находятся на одной стороне линии (v0, v1).Если (x0, x1) расходится от (v0, v1) на одной стороне его пересечения с (v0, v (n / 2)).Мы знаем, что на этой стороне не может быть пересечения с многоугольником.

Случай 2.3: Пересечение ближе к v (n / 2)

Этот случайобрабатывается аналогично случаю 2.2, но с использованием соответствующего соседа v (n / 2).

Все готово.Для каждого уровня это требует двух пересечений линий, проверки влево-вправо и определения местоположения точки на линии.Каждая рекурсия делит количество вершин на 2 (технически делит их как минимум на 4/3).И поэтому мы получаем время выполнения O (log n).

Answer 2

Я думаю, эта статья дает ясное решение O (log n). Найти крайности в направлении, перпендикулярном данной линии.

Answer 3

Ограничительные рамки могут оказаться полезными.

* 1002. , проверьте на пересечение вашей линии с этим приближением и уточните при необходимости.

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

Answer 4

Вам просто нужно найти точку А, которая находится на левой стороне линии, и другую точку, которая находится на правой стороне.Остается вопрос, как быстро найти эти точки.

Answer 5

взять случайные две точки A и B из выпуклого многоугольника.

• если они находятся на другой стороне линии, они пересекаются
• если они находятся на одной стороне, на обеих частях многоугольника (скажем, по часовой стрелке AB и BA) выполните:
  
  • создать линию, параллельную вашей линии l, проходящей через A
    
  • найти точку на максимальном расстоянии от l на полигоне, что аналогично нахождению максимума в функции, которая сначала монотонно не убывает, а затем монотонно не увеличивается. это можно сделать в O (log n) с помощью троичного поиска

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

Кстати, вы также можете найти фактические точки пересечения в O (log n).