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

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

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

5 18
algorithm asymptotic-complexity computational-geometry

5 ответов:

Ответ 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)} находятся на одной стороне (x0, x1), и поэтому мы знаем, что в этой "половине" многоугольника нет пересечения.

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

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

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

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

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

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

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

Если это так, найдите пересечение, p. если 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).

16

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

3

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

Напомним, что выпуклая часть аффинного пространства является пересечением всех его гиперплоскостей огибающей: вы можете получить аппроксимацию вашего многоугольника (читай "ограничивающий выпуклый многоугольник"), рассматривая только пересечение подмножества гиперплоскостей огибающей, проверить пересечение вашей прямой с этим приближением и при необходимости уточнить.

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

2

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

1

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

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


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

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

0