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

  концов (если есть — возвращаем 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(dR, dL).

Соединяй

Для всего множества 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 лежит вне многоугольника, иначе — внутри многоугольника.