Вычислительная геометрия (стр. 3 )

Описанный выше алгоритм работает за O(n), где n — количество вершин многоугольника.

Случай выпуклого многоугольника

Имеется выпуклый многоугольник и некоторая точка A; необходимо определить, принадлежит ли точка A данному многоугольнику.

Найдём верхнюю и нижнюю цепочки многоугольника. Теперь найдём точки пересечения вертикальной прямой, проходящей через точку A, с верхней и нижней цепочками многоугольника. Применив двоичный поиск, это можно сделать за O(logn). Для ответа на первоначальный вопрос достаточно проверить взаимное расположение точки A и полученных двух точек (конечно, если таковые нашлись).

Этот алгоритм требует некоторых предвычислений — поиска верхней и нижней цепочек многоугольника. Однако, после предвычислений он позволяет за O(logn) определять принадлежность точек многоугольнику.

Вычисление площади многоугольника

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

Определение звёздчатого многоугольника

Предположим, что точки P и Q лежат внутри некоторого многоугольника. Будем говорить, что точка Q видна из точки P, если отрезок PQ лежит внутри многоугольника. Отношение видимости симметрично (если точка P видит точку Q, то и точка Q видит P), но не транзитивно (если P видит Q, а Q видит R, то из этого не следует, что P видит R).

Набор точек внутри многоугольника, из которых видны все точки многоугольника, называется ядром многоугольника. Говорят, что многоугольник является звёздчатым, если его ядро не пусто. Многоугольник называется веерообразным, если его непустое ядро содержит одну или более вершин (каждая такая вершина называется корнем многоугольника). Каждый выпуклый многоугольник является веерообразным, поскольку его ядро включает все вершины. Каждый веерообразный многоугольник является звёздчатым, поскольку его ядро не пусто.

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

Для данного набора V различных точек V1, V2, …, Vn требуется построить произвольный звёздчатый многоугольник с вершинами в этих точках.

Вначале текущий многоугольник является одноугольником с вершиной V1. Отсортируем остальные точки по полярному углу относительно точки V1. Теперь добавим эти точки в полученном порядке к текущему многоугольнику. Полученный многоугольник является звёздчатым, т. к. из точки V1 по построению видны все остальные его вершины. Более того, он является веерообразным, поскольку его ядро содержит точку V1.

Время работы алгоритма составляет O(nlogn).

Поиск выпуклой оболочки

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

Проход Джарвиса (заворачивание подарка)

Один из способов формирования выпуклой оболочки конечного набора точек S на плоскости напоминает действия по вычерчиванию выпуклой оболочки с помощью линейки и карандаша. Вначале выбирается некоторая точка A из S такая, что она должна явно принадлежать границе выпуклой оболочки — для этого годится самая нижняя точка. Затем горизонтальный луч поворачивается против направления движения часовой стрелки вокруг этой точки до тех пор, пока он не наткнётся на некоторую другую точку B в наборе S; отрезок AB будет ребром выпуклой оболочки. Для поиска следующего ребра будем продолжать вращение луча против часовой стрелки, на этот раз вокруг точки B до встречи со следующей точкой C из набора S, отрезок BC будет следующим ребром выпуклой оболочки. Этот процесс продолжается до тех пор, пока не будет достигнута точка A.

Процесс поворота луча вокруг каждой точки является выбирающей частью алгоритма. При выборе точки, следующей за точкой A на границе выпуклой оболочки, ищем такую точку B, для которой нет ни одной точки, лежащей справа от луча AB. Все точки перебираются по очереди, пока алгоритм не проследит весь путь, вплоть до самой правой точки, обнаруженной к этому моменту.

Поскольку выполняется только h поворотов (h — число вершин в выпуклой оболочке), общее время работы составляет O(nh).

Просмотр Грэхема

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

При рассмотрении очередной точки pi выпуклая оболочка уже содержит l точек V1, V2, …, Vl. Возможны два случая:

угол Vl−1 Vl pi представляет левый поворот:
добавим точку pi в текущую выпуклую оболочку; перейдём к рассмотрению следующей точки pi+1.
угол Vl−1 Vl pi не является левым поворотом:
удалим точку Vl из текущей выпуклой оболочки; продолжим обработку точки pi.

Описанный алгоритм работает за O(nlogn) + O(n) = O(nlogn).

Метод разделяй и властвуй

В основе этого алгоритма лежит метод разделяй и властвуй:

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

Для задачи построения выпуклой оболочки эти три этапа выглядят так:

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

выполняется два рекурсивных вызова для нахождения выпуклых оболочек получившихся множеств;

соединяются две выпуклые оболочки, полученные на предыдущем шаге;

Слияние представляет собой самую сложную задачу в алгоритме.

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

Прямая l называется мостиком двух выпуклых многоугольников p и Q, если прямая l является касательной обоих p и Q.

Мостик l двух выпуклых многоугольников p и Q называется верхним (нижним), если оба многоугольника p и Q лежат выше (ниже) прямой l.

Верхний (нижний) мостик можно найти за линейное время следующим образом:

установим указатель l на самую правую вершину многоугольника L, а указатель r — на самую левую вершину многоугольника R; пока отрезок lr будет лежать между многоугольниками L и R (не будет пересекать их границ в точках, отличных от концов отрезка), будем поочерёдно двигать вверх (вниз) указатели l и r.

Для слияния двух выпуклых оболочек L и R, необходимо найти верхний мостик, соединяющий некоторую вершину l1 из L с некоторой вершиной r1 из R, а также нижний мостик, соединяющий вершины l2 и r2 из L и R соответственно. Вершины l1 и l2 делят границу многоугольника L на левую и правую цепочки и, аналогично, вершины r1 и r2 делят границу многоугольника R на левую и правую цепочки. Граница искомого многоугольника состоит из верхнего и нижнего мостиков, правой цепочки многоугольника L и левой цепочки многоугольника R.

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

Триангуляция многоугольника

Триангуляцией многоугольника называется декомпозиция многоугольника на треугольники.

Триангуляция монотонного многоугольника

Будем считать, что верхняя и нижняя цепочки состоят из вершин Ui и Dj соответственно

Установим указатели pu и pd на U1 и D1 соответственно.

Пока указатели не достигли последней вершины, будем делать следующее:

если вершина Upu+1 расположена левее Dpd+1, то добавим в триангуляцию треугольник Upu Upu+1 Dpd (если он не вырожден) и увеличим pu;

иначе, добавим в триангуляцию треугольник Upu Dpd+1 Dpd (если он не вырожден) и увеличим pd.

Нетрудно видеть, что этот алгоритм линеен.

Регуляризация многоугольника

Для триангуляции произвольного многоугольника достаточно провести регуляризацию — декомпозицию этого многоугольника на монотонные многоугольники.

Вогнутая вершина многоугольника называется изломом, если обе её соседние вершины лежат либо справа от неё, либо слева. Заметим, что многоугольник является монотонным тогда и только тогда, когда он не содержит изломов.