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

Question

Ищет алгоритм O (logn) для идентификации сегментов линии выпуклого многоугольника, которые пересекаются с расширенным отрезком линии. Как известно, сегмент линии лежит внутри выпуклого многоугольника.
Пример: Входной сигнал: AB/Отрезок /, {1,2,3,4,5,6}/выпуклого многоугольника вершины в порядке КОО Alongwith их координаты/
Выход: 3-4,5 -6

Это может быть сделано путем получения уравнения всех линий и проверить, если они пересекаются, но это было бы O (п) в п строк, должны быть проверены на наличие пересечения. Я думаю, что должно быть возможно использовать Двоичный поиск (из-за логарифмической привязки), чтобы уменьшить сложность, но я не могу понять, что его применять.

Answer 1

Сначала вам необходимо работать с ориентированными краями многоугольника и хранить их в массиве (или может быть в другой структуре данных, что позволяет получить прямой доступ со временем сложности не более O (logN)). Связанный список не подходит для этой проблемы.

Также вам нужно назначить ориентацию для вашего расширенного сегмента - предположим, он ориентирован от A до B. Затем он разбивает плоскость на две полуплоскости - слева и справа. Вы выбираете свой начальный ребро (с вершинами 0 и 1), а затем средний край (с вершинами [n/2] -1 и [n/2]). Есть два случая: исходный край пересекает расширенный сегмент, или нет. Я рассмотрю первый случай здесь, оставив второй вам. Также я предполагаю, что исходный край целиком лежит в правой полуплоскости (случай левой плоскости симметричен). Средний край разбивает многоугольник на два крайних пути - Я позвоню им первые один (вершины от 0 до [п/2]) и вторых одной (вершин из [п/2], чтобы 0).

Пять возможны случаи - средний край может: полностью

1. Ли в правой halplane (так же, как начальный край) и следовать начальный край - то вы рекурсивно проанализировать второй путь.
2. Ложь целиком в правом полуплоскости (то же, что и исходный край) и предшествует начальный край - тогда вы рекурсивно анализируете первый путь.
3. Ложитесь целиком в левую полуплоскость (а не ту, где находится начальный край) - тогда вам придется рекурсивно анализировать как пути.
4. Пересечение расширенного сегмента, идущего от правой полуплоскости к левой полуплоскости - найдено одно пересечение, а затем вы рекурсивно анализируете второй путь.
5. Пересечение расширенного сегмента, идущего от левой полуплоскости к правой полуплоскости - найдено одно пересечение, затем вы рекурсивно анализируете первый путь.

Так что наиболее «неудобным» случаем является (2) - вы не можете удалить какие-либо дорожки в этом случае, но похоже, что его нельзя повторить для всего полигона.

Также вам нужно будет рассчитать соотношение между ориентированными краями многоугольника - «следует/предшествует». Это можно сделать, используя относительный краевой угол - «следующий» край должен поворачиваться влево относительно «предыдущего» края (из-за выпуклости).