Лекция 5 | Вычислительная геометрия | Кира Вяткина | Лекториум

• Разработанные методы позволяют решать простые, но важные задачи.  

• Можно находить пересечение, объединение, разность и симметрическую разность многоугольников.  

• Для пересечения нужно найти наложение и выбрать грани с внутренними метками.  

• Алгоритм Сзерленда и Хогмана используется в компьютерной графике.  

• Пересечение многоугольников находится путем последовательного отсечения по ребрам.  

• Эффективная реализация включает фиксацию полуплоскости и переход от одной вершины к другой.  

• Рассматриваются четыре случая: вершина в полуплоскости, вершина вне полуплоскости, переход в полуплоскость, переход вне полуплоскости.  

• В каждом случае выдаются соответствующие вершины пересечения.  

• Алгоритм прост и может быть реализован на аппаратном уровне.  

• Алгоритм Шеймуса позволяет пересекать выпуклые многоугольники более эффективно.  

• Проводится вертикальная прямая через каждую вершину, разбивая плоскость на полосы.  

• Пересечения внутри полос объединяются для получения результирующего пересечения.  

• Процесс нахождения пересечений можно представить как заметание плоскости вертикальной прямой.  

• Вершины многоугольников упорядочиваются, что позволяет эффективно находить пересечения.  

• Объединение пересечений выполняется за линейное время.  

• Пример с решеткой показывает, что сложность пересечения невыпуклых многоугольников может быть линейной.  

• Общий алгоритм может быть адаптирован для решения этой задачи.  

• Задача пересечения полуплоскостей решается методом "разделяй и властвуй".  

• Множество полуплоскостей разбивается на подмножества, и пересечение находится путем объединения результатов.  

• Разделяем множество на два примерно равных по мощности подмножества.  

• Вычисляем пересечение полуплоскостей с помощью рекурсивной процедуры.  

• Объединяем полученные результаты для получения пересечения двух областей.  

• Обобщаем алгоритм пересечения многоугольников на случай неограниченных областей.  

• Используем метод заметания для пересечения горизонтальных прямых с областями.  

• Храним четыре ребра для каждой области, упорядочивая их за константное время.  

• Точки события определяются как вершины областей.  

• Если прямая пересекает четыре ребра, следующая точка события - это верхний или нижний конец пересекаемых ребер.  

• Очередь событий не нужна, так как следующая точка события определяется за константное время.  

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

• Если точка лежит между ребрами, она является вершиной пересечения.  

• Полуплоскость, соответствующая ребру, заносится в список ребер для соответствующей области.  

• Если ребро пересекает правое ребро области, возможны два варианта: ребро входит внутрь области или выходит за ее пределы.  

• В первом случае ребро заносится в список левых ребер, во втором - в список правых ребер.  

• Если ребро пересекает левое ребро области, также возможны два варианта: ребро входит внутрь или выходит за пределы области.  

• В обоих случаях определяется точка пересечения и ребро, которое вносит вклад в границу пересечения.  

• Полуплоскость, соответствующая ребру, заносится в список левых или правых ребер.  

• Последовательность проверок не взаимоисключающая, так как могут быть случаи, когда точка лежит между ребрами и ребро пересекает как правое, так и левое ребро.  

• Рассматриваются все возможные случаи пересечения плоскостей.  

• Пример с точкой P и ребром, пересекающим левое ребро.  

• Проверка на шаге 1 учитывает часть ребра, проигнорированную на шаге 3.  

• Алгоритм работает корректно, если все вершины области пересечения учтены.  

• Вершины области пересечения либо являются вершинами исходных областей, либо точками пересечения двух ребер.  

• Алгоритм гарантирует правильную обработку всех вершин.  

• Алгоритм работает за линейное время по суммарной сложности областей.  

• Сложность алгоритма зависит от количества вершин в областях.  

• Алгоритм находит пересечение плоскостей за время O n log n.  

• Звездный многоугольник имеет точку, из которой видны все точки многоугольника.  

• Множество таких точек называется ядром многоугольника.  

• Задача нахождения ядра решается за время O n log n и требует O n памяти.  

• Определение диагонали многоугольника: открытый отрезок с концами в вершинах, целиком лежащий внутри многоугольника.  

• Доказательство существования диагонали для многоугольника с четырьмя вершинами.  

• Триангуляция многоугольника: разбиение на треугольники с попарно непересекающимися диагоналями.  

• Для любого многоугольника существует триангуляция.  

• Любая триангуляция содержит n-3 диагонали и n-2 треугольника.  

• Доказательство существования триангуляции многоугольника.  

• Использование индукции для доказательства.  

• Пример с треугольником, который является триангуляцией.  

• Индукционный переход для многоугольника с n вершинами.  

• Построение диагонали, разбивающей многоугольник на два.  

• Объединение триангуляций для каждого из полученных многоугольников.  

• Подсчет диагоналей и треугольников в триангуляции.  

• Использование индукции для доказательства соотношения между диагоналями и треугольниками.  

• Объяснение, почему триангуляция содержит n-3 диагонали и n-2 треугольника.  

• Конструктивное доказательство существования триангуляции.  

• Последовательное добавление диагоналей для разбиения многоугольника.  

• Применение леммы для построения триангуляции.  

• Описание наивного алгоритма построения триангуляции.  

• Сложность алгоритма: O n^2.  

• Заключение о сложности и неэффективности алгоритма.  

• Определение уха многоугольника.  

• Введение понятия графа двойственной триангуляции.  

• Описание графа двойственной триангуляции и его свойств.  

• Доказательство связности графа двойственной триангуляции.  

• Утверждение о том, что граф является деревом.  

• Следствие: любой многоугольник имеет по крайней мере два уха.  

• Многоугольник с четырьмя вершинами имеет диагональ.  

• Для триангуляции треугольника можно считать вырожденную вершину.  

• Степень вершины не должна быть равна трем.  

• Любой угол имеет по крайней мере два уха.  

• Алгоритм отрезания ушей: на каждом шаге отрезается ухо, уменьшая количество вершин на одну.  

• Поиск уха занимает линейное время, что приводит к времени O n^2.  

• После отрезания уха могут появиться не более двух новых ушей.  

• На этапе предобработки находятся все уши за O n^2.  

• После отрезания уха корректируется список ушей за линейное время.  

• Триангуляция многоугольника может быть раскрашена в три цвета.  

• После обработки очередного треугольника все вершины будут раскрашены в три цвета.  

• Это свойство используется в задаче о картинной галерее.  

• Задача о картинной галерее: расставить охранников внутри многоугольника, чтобы все стены были под наблюдением.  

• Охранники могут смотреть во все стороны, но не видят сквозь стены.  

• Существует множество вариаций задачи, включая ограничения на угол обзора и движение охранников.  

• Наивный алгоритм: поставить охранника в каждую вершину или каждую вторую вершину.  

• Внутрь каждого треугольника достаточно поставить одного охранника.  

• Для некоторых треугольников достаточно одного охранника, чтобы видеть весь треугольник.  

• Разбиение на звезды - хорошая идея, но задача сложная.  

• Задача распознавания NP-полна, а задача оптимизации NP-трудна.  

• Эффективные и приближенные решения возможны, но задача остается сложной.  

• Многоугольник с вершинами требует определенного количества охранников.  

• Иногда это количество необходимо, иногда достаточно.  

• Использование регуляции для эффективного размещения охранников.  

• Раскраска вершин в три цвета для предотвращения треугольников.  

• Выбор цвета с наименьшим числом окрашенных вершин.  

• Размещение охранников в вершинах с наименьшим числом окрашенных вершин.  

• Пример с расческой иллюстрирует необходимость охранников.  

• Продление ребер показывает количество треугольников, требующих охраны.  

• Доказательство завершено.  

• Упражнение: сколько охранников достаточно для ортогонального многоугольника.  

• Обсуждение алгоритмов для триангуляции многоугольника.  

• Алгоритм за время O n log n для простого многоугольника, предложенный Бернаром в 1991 году.  

• Алгоритм Бернара сложен и малоприменим на практике.  

• Задача построения эффективного алгоритма регуляции остается актуальной.  

• Завершение разговора и анонс следующей лекции.