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

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

Спасибо

Ответы

Ответ 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)} находятся на одной стороне (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).

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

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


если эти две самые удаленные точки находятся на другой стороне вашей линии, линия пересекает полигон, иначе это не будет
Кстати, вы также можете найти фактические точки пересечения в O (log n) тоже.