Алгоритм O (n) для обнаружения пересечения линии с выпуклым многоугольником состоит в проверке того, пересекает ли какая-либо ребро многоугольника линию и смотрит ли число пересечений является нечетным или четным.Асимптотически оптимальный алгоритм для вычисления, если линия пересекает выпуклый многоугольник
Существует ли асимптотически более быстрый алгоритм, например. O (log n) один?
Ответ 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 (п/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 (п/2)
Этот случай рассматривается аналогично случаю 2.2, но с использованием соответствующего соседа V (N/2).
Мы готовы. Для каждого уровня это требует двух пересечений линий, проверки влево-вправо и определения, где точка находится на линии. Каждая рекурсия делит число вершин на 2 (технически делит их как минимум на 4/3). И поэтому мы получаем время выполнения O (log n).
Ограничительные коробки могут оказаться полезными.
Напомним, что выпуклая часть аффинного пространства является пересечением всех ее гиперплоскостей огибающей: вы можете получить приближение своего многоугольника (прочитайте «ограничивающий выпуклый многоугольник»), рассмотрев только пересечение подмножества огибающей гиперплоскости, тест для пересечения вашей линии с этим приближением и, при необходимости, уточнить.
Все это работает лучше, если вы ожидаете небольшого количества пересечений.
Вам просто нужно найти точку А, расположенную на левой стороне линии, и другую точку, расположенную с правой стороны. Остается вопрос, как быстро найти точки.
возьмите случайные две точки A и B из выпуклого полигона.
, если эти две дальние точки на другую сторону вашей линии, пересекает Полигон, в противном случае она не
Кстати, вы также можете найти фактические точки пересечения в O (log n).
Алгоритм недействителен. 1) последовательности вершин AB и BA могут быть недействительными для тройного поиска. 2) Наличие точек с максимальным расстоянием от l на этих полилиниях не гарантирует, что точки находятся на противоположных сторонах исследуемой линии. Даже когда линия пересекает многоугольник. –
Любое расстояние не должно быть абсолютным (так что с одной стороны отрицательно, на другом положительном), или для одной стороны l проходит через A и через B на другое. – Sarmun
Не абсолютное расстояние помогло бы, но не во всех случаях. См. Http://jurajblaho.wz.cz/path2816.png. A-> B в порядке CW недействителен для тройного поиска, поскольку он увеличивается, уменьшается и, наконец, увеличивается. –
Я думаю, this article дает четкое решение O (log n). Найдите крайности в направлении, перпендикулярном данной линии.
Пожалуйста, уточните, что находится в левой/правой половине полигона. Возможно, было бы лучше использовать термины v0-> vk или vk-> v0 при условии, что порядок CCW. –
Каждый раз, когда я говорил влево/вправо, я выяснял, я перечислил вершины в этой половине. В частности, левая половина - это вершины, которые не находятся справа от линии (v0, v (n/2)), {v0, v1, ..., v (n/2)}. Я использую этот термин не вправо, потому что это набор вершин слева от строки плюс те, что указаны на линии. –
+1 Пока я не найду противоположный пример. Примечание. Я думаю, что разъяснение неверно. В порядке CCW правая половина равна v0-> v (n/2). –