Первая страница / Теория / Компьютерная математика /

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

Голосование: 338, 11

Введение

Вычислительная геометрия — это раздел математики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании, черчении и др. Исходными данными в такого рода задаче могут быть множество точек, набор отрезков, многоугольник (заданный, например, списком своих вершин в порядке обхода против часовой стрелки) и т. п. Результатом может быть либо ответ на какой-то вопрос (пересекаются ли эти два отрезка?), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, содержащий данные точки).

Хотя вычислительная геометрия берет начало от задач на построение циркулем и линейкой, которые изучались еще в Древней Греции, вычислительной сложностью геометрических задач начали интересоваться только в начале XX века (E. Lemoine, 1902).

Основная задача вычислительной геометрии

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

Работа с точками и отрезками на плоскости

Наиболее простыми геометрическими объектами на плоскости являются точки и отрезки. Для начала напомним некоторые определения.

Основные определения

Далее мы будем полагать, что на плоскости задана декартова прямоугольная система координат, причем базис имеет правую ориентацию, т. е. ось Oy «получается» поворотом оси Ox против часовой стрелки. Также мы предполагаем знакомство читателя с основами векторной алгебры и аналитической геометрии.

Точка на декартовой плоскости задается двумя числами: ее абсциссой и ординатой. В дальнейшем точку будем отождествлять с ее радиус-вектором (вектором, соединяющим начало координат с точкой).

Отрезок с концами в точках p1 и p2 — это множество точек, представимых в виде p = ap1 + (1 − a)p2, где 0 ≤ a ≤ 1.

Направление поворота

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

Векторным произведением A×B двух векторов A = (AxAy) и B = (BxBy) назовем число (!), равное Ax×By − Bx×Ay.

Если сопоставить данное нами определение векторного произведения с тем, которое дается в курсах аналитической геометрии (наше произведение оказывается z-координатой «стандартного»), то ответ на поставленный вопрос очевиден: если A×B > 0, то A надо поворачивать против часовой стрелки, если A×B < 0, то A надо поворачивать по часовой стрелке, если A×B = 0, то векторы либо сонаправлены, либо направлены в противоположные стороны.

По часовой стрелке Против часовой стрелки

Проверка пересечения отрезков

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

  1. Проверим пересечение ограничивающих прямоугольников для этих отрезков. Ограничивающим прямоугольником для некоторой фигуры F называется прямоугольник минимальной площади со сторонами, параллельными осям координат и содержащий фигуру F. Если ограничивающие прямоугольники не пересекаются, то отрезки также не пересекаются.

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

  2. Теперь проверим для каждого из отрезков, пересекает ли он прямую, на которой лежит другой. Отрезок пересекает прямую, если его концы лежат по разные стороны от прямой или один из концов лежит на прямой. Последнее легко проверить, используя векторное произведение — векторы p1p3 и p1p4 должны иметь различную ориентацию относительно вектора p1p2.

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

Итог

Отрезки p1p2 и p3p4 пересекаются тогда и только тогда, когда одновременно выполнены три условия:

  1. Пересекаются ограничивающие их прямоугольники.
  2. (p3 − p1) × (p2 − p1) · (p4 − p1) × (p2 − p1) ≤ 0
  3. (p1 − p3) × (p4 − p3) · (p2 − p3) × (p4 − p3) ≤ 0

Теперь рассмотрим задачу, также связанную с отрезками, но решающуюся не так просто.

Есть ли пересекающиеся отрезки?

Постановка задачи

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

Метод решения задачи

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

Введем отношение порядка на отрезках. Будем говорить, что два отрезка сравнимы относительно x, если вертикальная прямая с абсциссой x пересекает оба отрезка. При этом s1 выше s2, если точка пересечения s1 с вертикальной прямой выше точки пересечения s2 с этой же прямой.

В точке пересечения отрезков отношение порядка между ними меняется на противоположное. По предположению никакие три отрезка не проходят через одну точку, поэтому в окрестности точки пересечения пересекающиеся отрезки непосредственно следуют друг за другом (в смысле введенного на них порядка).

В точке пересечения отношение порядка меняется на обратное

Движение прямой

Будем хранить следующую информацию:

  1. Состояние дел у прямой — упорядоченное множество отрезков, пересекаемых прямой в данный момент времени.
  2. Расписание — список критических точек — состояние дел у прямой может измениться только в них.

При этом структура данных, реализующая состояние дел у прямой, должна поддерживать следующие операции:

  1. INSERT(s) — добавить отрезок s
  2. DELETE(s) — удалить отрезок s
  3. ABOVE(s) — указать отрезок, располагающийся непосредственно выше s
  4. BELOW(s) — указать отрезок, располагающийся непосредственно ниже s

С использованием сбалансированного дерева поиска (например, AVL-дерева или красно-черного дерева) все эти операции можно реализовать за O(logn).

Итог: общий алгоритм


 1 сортируем концы отрезков в порядке возрастания абсцисс
         (точки с равными абсциссами идут в порядке возрастания
         ординат); проверяем, нет ли совпадающих точек среди
         концов (если есть — возвращаем TRUE)
 2 for для каждой точки p из полученного списка do
 3     if (p — левый конец некоторого отрезка s) then
 4         INSERT(s)
 5         if (ABOVE(s) существует и пересекает s)
                     или  (BELOW(s) существует и пересекает s) then
 6             return TRUE        
 7     if (p — правый конец некоторого отрезка s) then
 8         if (определены ABOVE(s) и BELOW(s))
                     и (они пересекаются) then
 9            return TRUE
10         DELETE(s)         
11 return FALSE  

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

NB! Метод движущейся прямой является одним из основных методов вычислительной геометрии.

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

Задача о ближайших точках

Постановка задачи

Дано множество точек на плоскости. Найти среди них две ближайшие (с наименьшим расстоянием).

Метод решения задачи

Алгоритм со временем работы O(nlogn) может быть построен методом разделяй и властвуй. Он имеет рекурсивную структуру.

Входные данные для рекурсивной процедуры

Входные данные для каждого рекурсивного вызова алгоритма состоят из некоторого множества p точек и двух массивов — X и Y. Каждый из них содержит точки из этого множества, но в разных порядках: X — в порядке возрастания абсцисс, а Y — в порядке возрастания ординат.

Разделяй

Найдем вертикальную прямую, разделяющую множество p на две части половинного размера — pR и pL. Это можно сделать, например, взяв средний элемент в массиве X, отсортированном по возрастанию абсциссы. При этом точки, попадающие на прямую, можно отнести в любую из частей — главное, чтобы ни одна из частей не оказалась пустой.

Разделение на две части

Властвуй

После деления выполняем два рекурсивных вызова — для левой и правой частей. Пусть dR и dL — результаты для левой и правой частей соответственно. Положим d = min(dRdL).

Соединяй

Для всего множества p ответом будет либо d (и соответствующая ему пара), либо какая-то пара приграничных точек, в которой одна точка принадлежит pR, а другая — pL. Очевидно, что точки такой пары отстоят от разделяющей прямой не более, чем на d.

Приграничная полоса

Нахождение приграничной пары

Для нахождения приграничной пары точек поместим все точки, лежащие в полосе шириной 2d и симметричной относительно разделяющей прямой, в массив в порядке возрастания ординаты. В [1] доказывается, что для нахождения приграничной пары достаточно для каждой точки просмотреть 7 идущих за ней в этом массиве. Для достижения времени работы O(nlogn) необходимо отсортировать все точки перед началом работы по возрастанию ординаты, а затем при каждом рекурсивном вызове разделять этот массив.

Итог: алгоритм


NEAREST_POINTS(p, X, Y)
 1 Если в переданном нам множестве p 2 точки, то возвращаем
   расстояние между ними; если одна — возвращаем бесконечность
 2 Находим вертикальную прямую (с абсциссой xm), 
   разделяющую множество точек на две части примерно 
   одинакового размера
 3 Разделяем его на две части — "левую" pL и "правую" pR
   (получили массивы XR, YR, XL, YL) 
 4 dR := NEAREST_POINTS(pR, XR, YR) // Обработка правой части
 5 dL := NEAREST_POINTS(pL, XL, YL) // Обработка левой части
 6 d := min(dR, dL)                    // Ширина полосы
 7 В массив S поместим все точки, лежащие в полосе — 
   пусть их ns штук.
 8 for i := 1 to ns do
 9     for j := i + 1 to min(ns, i + 7) do
10         if distance(S[i], S[j]) < d then 
11             d := distance(S[i], S[j])
12 return d

NB! Изложенный алгоритм можно обобщить на многомерные случаи и случаи неевклидовой метрики.

NB! Описанный алгоритм асимптотически оптимален в модели разрешающих деревьев.

Теперь перейдем к задаче о наиболее удаленных точках.

Задача о наиболее удаленных точках

Постановка задачи

Дано множество точек. Найти две наиболее удаленные точки (точки с наибольшим расстоянием друг от друга).

Более простая задача

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

Алгоритм решения задачи

Будем поддерживать два указателя: A — на ребро многоугольника, B — на вершину многоугольника. Инвариантом будет то, что B — самая удаленная вершина от ребра A. Для инициализации просто установим A на ребро, соединяющее первую и вторую вершину в порядке обхода, а B установим на самую удаленную от A вершину (это можно сделать за линейное время). Далее, на каждом шаге будем сдвигать A на следующее ребро по часовой стрелке. Нетрудно видеть, что при этом B может сдвинуться также только по часовой стрелке (это следует из выпуклости многоугольника). В результате на каждом шаге получился треугольник, состоящий из ребра Ai и вершины Bi. Покажем, что самая длинная диагональ является ребром одного из таких треугольников.

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

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

Описанный выше алгоритм легко представить так: многоугольник катится по прямой, и, когда он «встает» на очередное ребро, выбирается самая верхняя вершина.

Первый шаг Второй шаг

FARTHEST_POINTS
 1 Установить A на первое ребро
 2 Установить B на самую удаленную от A вершину
 3 answer := distanceEdgeVertex(A, B)
 4 for i := 1 to n − 1 do 
 5     A := nextEdge(A)  // Переходим на следующее ребро в порядке обхода
 6     while distanceEdgeVertex(A, B) < distanceEdgeVertex(A, next(B)) do
 7         B := next(B)
 8     answer := max(answer, distanceVertexVertex(begin(A), B))
 9     answer := max(answer, distanceVertexVertex(end(A), B))
10 return answer

Методами амортизационного анализа легко доказать, что этот алгоритм работает за O(n).

NB! Так как поиск выпуклой оболочки требует O(nlogn) операций (это будет показано далее), то две самые удаленные точки на плоскости можно найти за O(nlogn).

Работа с многоугольниками

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

Определения

Многоугольник — замкнутая ориентированная ломанная без самопересечений и самокасаний, а также ограниченная ею область.

Выпуклый многоугольник — многоугольник, две любые внутренние точки которого можно соединить отрезком, целиком в нём лежащим.

Выпуклая вершина — вершина, внутренний угол при которой меньше, либо равен 180 градусов.

Внутренняя вершина — вершина, внутренний угол при которой больше 180 градусов.

Красным цветом выделены выпуклые вершины, а синим — вогнутые

Монотонная цепочка вершин — цепочка вершин, каждая следующая вершина которой располагается не левее предыдущей.

Монотонный многоугольник — многоугольник, граница которого представима в виде объединения двух монотонных цепочек вершин.

При этом верхней (нижней) цепочкой называется та, вторая вершина которой лежит выше (ниже) второй вершины другой.

Свойства выпуклых многоугольников:

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

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

Для проверки выпуклости произвольного многоугольника достаточно проверить выпуклость каждой его вершины. Это можно сделать, учитывая следующий факт: вершина многоугольника является выпуклой тогда и только тогда, когда при обходе его границы против часовой стрелки в данной вершине не происходит отклонения вправо. Таким образом, многоугольник является выпуклым тогда и только тогда, когда при обходе его границы в каждой его вершине не происходит отклонения вправо.

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

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

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

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

Прежде всего, проверим, лежит ли точка A на границе имеющегося многоугольника. Если оказалось, что она не лежит на границе многоугольника, то пустим из точки A луч AB в случайном направлении (не нарушая общности, можно считать, что луч AB не проходит ни через одну вершину многоугольника).

Теперь подсчитаем количество рёбер, пересекаемых лучом AB. Если это количество чётно, то точка A лежит вне многоугольника, иначе — внутри многоугольника.

Описанный выше алгоритм работает за 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 соответственно (1 ≤ i ≤ uCnt, 1 ≤ j ≤ dCnt).

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

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

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

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

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

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

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

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

Для решения поставленной задачи можно применить метод сканирующей прямой. Здесь под сканирующей линией будем понимать некоторую вертикальную линию, а также все рёбра, либо пересекаемые ею, либо касающиеся её, отсортированные по возрастанию ординаты. Кроме того, в сканирующей линии для каждой пары соседних вершин будем хранить представителя этих ребер — самую правую из вершин лежащих внутри четырёхугольника, построенного на этих рёбрах, но слева от сканирующей линии.

Прежде всего, отсортируем вершины по возрастанию абсциссы. При этом для каждой вершины будем хранить соседние (в многоугольнике) с ней вершины. Определим для каждой вершины её тип:

  • начальная вершина — обе соседние вершины располагаются справа;

  • промежуточная вершина — соседние вершины располагаются и слева и справа;

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

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

Рассмотрим первую фазу (вторая аналогична первой). Пока есть необработанные вершины, выбираем самую правую из них. Возможны три случая:

вершина v является конечной

вершина является конечной:

  • удаляем из сканирующей линии исчезнувшие рёбра (рёбра c и b)
  • обновляем представителя пары рёбер, ставших соседними (теперь вершина v — представитель пары рёбер ad);
вершина v является промежуточной

вершина является промежуточной:

  • обновляем ребро сканирующей линии и представителей верхней (cb') и нижней (ab') пар рёбер;
  • вершина v является начальной

    вершина является начальной:

    • находим пару соседних рёбер ad, между которыми располагается данная вершина, а также их представителя w;
    • добавляем два ребра (b и c) в сканирующую линию;
    • обновляем представителей трех пар ребер (ab, bc, cd);
    • уничтожаем излом v, разрезая многоугольник отрезком vw (это можно реализовать, раздвоив вершины v и w на v1, v2 и w1, w2 и добавив ребра v1w1 и w2v2).

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

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

    Будем говорить, что ребро a находится снаружи ребра b, если конец ребра a расположен слева от b.

    Будем говорить, что ребро a нацелено на ребро b, если бесконечная прямая линия, определяемая ребром b, расположена перед a.

    Идея алгоритма заключается в проталкивании выделенными рёбрами друг друга в процессе поиска точек пересечения рёбер до тех пор, пока одна и та же точка не будет обнаружена вторично.

    Ориентируем границы многоугольников в направлении по часовой стрелке. Выберем в качестве текущих рёбер многоугольников P и Q ребра p и q соответственно.

    Правила перемещения указателей p и q:

    p и q нацелены друг на друга

    p и q нацелены друг на друга:

    • перемещаем тот указатель, который соответствует тому ребру, которое находится снаружи от другого;
    p нацелено на q

    p нацелено на q, а q не нацелено на p:

    • если p не находится снаружи q, то конечная концевая точка ребра p заносится в многоугольник пересечения;
    • перемещаем окно p;
    q нацелено на p

    q нацелено на p, а p не нацелено на q:

    • если q не находится снаружи p, то конечная концевая точка ребра q заносится в многоугольник пересечения;
    • перемещаем окно q;
    p и q не нацелены друг на друга

    p и q не нацелены друг на друга:

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

    Алгоритм состоит из двух частей:

    • перемещаем указатели по указанным выше правилам (не формируя многоугольник пересечения) до обнаружения точки пересечения рёбер. Если такая точка нашлась, то переходим к следующей части, иначе проверяем принадлежность многоугольников друг другу и завершаем работу;
    • перемещаем указатели по тем же правилам (формируя многоугольник пересечения) до повторного обнаружения какой-либо точки пересечения.

    Время работы алгоритма составляет O(n), где n — суммарное количество рёбер в многоугольниках P и Q.

    Литература

    1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.  — М.: МЦНМО, 1999.
    2. Ласло М. Вычислительная геометрия и компьютерная графика на C++. — М.: БИНОМ, 1997.

    Федор Царев, Дмитрий Паращенко


    Е.Багоцкий / 2009-12-29 08:30:20

    Великолепно. Такой геометрии - ни элементарной, ни афинной,ни проективной я еще не видел. Хотя задачу о принадлежности точки внутренности многоугольника знаю в определенной постановке

    Е.Багоцкий / 2009-12-29 08:52:21

    По поводу задачи о принадлежности точки многоугольнику: cтандартная постановка - многоугольник выпуклый.
    Еще один алгоритм- подсчет суммы ориентированных углов между векторами от P до Ai и от P до Ai+1. Если сумма=360 то- P внутри, если=0 -то вне. Если хоть один такой угол=180 - то на границе

    Alex / 2014-11-07 19:30:39

    >> В [1] доказывается, что для нахождения приграничной пары достаточно для каждой точки просмотреть 7 идущих за ней в этом массиве.

    Неверно. Опровергнуть можно контрпримером, и доказать, что сколько бы точек за текущей не проверяли(пусть N штук), найдется такое расположение точек, что 1ая и (N+1)-ая точка будут ближайшими

    Ваше имя
    Email
    Текущий день недели (строчными буквами)
    Комментарий