Некоторые основные понятия вычислительной геометрии

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

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

Опр. Пусть S конечный набор точек на плоскости. Выпуклая оболочка conv(S) равна пересечению всех выпуклых полигонов, которые содержат S. Т.е. conv(S) – это выпуклый полигон минимальной площади, содержащий все точки S.

Построение звездчатого полигона

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

Совокупность точек многоугольника, из которых видны все точки этого многоугольника, называется его ядром. Многоугольник называется звездчатым, если его ядро не пусто. Ядро звездчатого многоугольника всегда выпукло.

Рассмотрим задачу: на плоскости задан набор точек s₀, s₁, …, s_n-1. требуется построить минимальный звездчатый многоугольник так, чтобы его ядро содержало точку s₀.

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

Для определения того, в какое место границы текущего многоугольника нужно вставить точку s_i, заметим, что все вершины звездчатого многоугольника должны быть полярно упорядочены вокруг любой точки его ядра, а значит относительно точки s₀, принадлежащей ядру. Будем обходить границу многоугольника по часовой стрелке, начиная с точки s₀, сравнивая каждый раз вставляемую точку и очередную точку границы. Функцию сравнения вершин определим, основываясь на вычислении полярных координат (r, ) точки относительно полюса s₀. Введем следующее правило сравнения: точка p(V_p, _p) считается меньше точки q(V_q, _q), если _p < _q или _p = _q и V_p < V_q. При таком упорядочении, обход текущего многоугольника по часовой стрелке будет производится от больших точек к меньшим.

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

Опр. Точка р выпуклого множества S называется крайней, если не существует пары точек a, b  S таких, что р лежит на открытом отрезке ab.

Множество Е крайних точек S представляет собой наименьшее подмножество S, обладающее тем свойством что conv(E)=conv(S), и Е в точности совпадает с множеством вершин conv(S).

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

0. Определить крайние точки.

1. Упорядочить эти точки так, чтобы они образовывали выпуклый полигон.

Теорема 1. Точка р не является крайней плоского выпуклого множества S только тогда, когда она лежит в некотором треугольнике, вершинами которого являются точки из S, но сама она не является вершиной этого треугольника.

Рис. Точка р не является крайней, так как она находится внутри треугольника (р1р2р3).

Пусть имеется О(N³) треугольников, определяемых N точками множества S. Проверка принадлежности точки заданному треугольнику может быть выполнена за некоторое постоянное число операций, так что за время О(N³) можно определить, является ли конкретная точка крайней. Повторение этой процедуры для всех N точек множества S потребует О(N⁴). Подобный алгоритм неэффективен, но прост. Кроме того, необходимо упорядочить найденные точки.

Теорема 2. Луч, выходящий из внутренней точки ограниченной выпуклой фигуры F, пересекает границу F в точности в одной точке.

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

Представим луч, выходящий из внутренней точки q полигона Р и заметающий вершины полигона Р в порядке движения против часовой стрелки, начиная из положения, совпадающего по направлению с положительным направлением оси Х. По мере движения от вершины к вершине полярный угол^* луча монотонно увеличивается (т.е. вершины упорядочиваются).

Рис. Вершины полигона Р упорядочены относительно точки q.

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

Алгоритм со временем выполнения О(N⁴) не позволит обрабатывать большие наборы данных, поэтому рассмотрим алгоритм Грэхема.