МЕТОД ОБХОДА ГРЭХЕМА

 

Алгоритм со временем выполнения 0(N⁴) не позволит обрабатывать очень большие наборы данных. В этом разделе мы исследуем наш алгоритм с точки зрения наличия в нем ненужных вычислений.

Так ли необходимо проверять все треугольники, определяемые множеством из N точек, чтобы узнать, лежит ли некоторая точка в каком-либо из них? Если пет, то имеется некоторая надежда, что крайние точки можно найти за время, меньшее, чем О (N⁴). Грэхем в одной из первых работ, специально посвященных вопросу разработки эффективных геометрических алгоритмов [Graham (1972)], показал, что, выполнив предварительно сортировку точек, крайние точки можно найти за линейное время. Использованный им метод стал очень мощным средством в области вычислительной геометрии.

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

Представив упорядоченные точки в виде дважды связанного кольцевого списка, получаем ситуацию, представленную на рис. 24. Обратите внимание: если точка не является вершиной выпуклой оболочки, то она является внутренней точкой для некоторого треугольника (O pq), где р и q— последовательные вершины выпуклой оболочки. Суть алгоритма Грэхема состоит в однократном просмотре упорядоченной последовательности точек, в процессе которого удаляются внутренние точки. Оставшиеся точки являются вершинами выпуклой оболочки, представленными в требуемом порядке.

Рис. 24. Начало обхода точек в методе Грэхема. Вершина р₂ удаляется, если угол р₁р₂р₃ оказывается вогнутым

 

Просмотр начинается с точки, помеченной как НАЧАЛО, в качестве которой можно взять самую правую с наименьшей ординатой точку из данного множества, заведомо являющуюся вершиной выпуклой оболочки. Тройки последовательных точек многократно проверяются в порядке обхода против часовой стрелки с целью определить, образуют или нет они угол, больший или равный л. Если внутренний угол р₁р₂р₃ больше или равен л, то говорят, что р₁р₂р₃, образуют «правый поворот», иначе они образуют «левый поворот». Из выпуклости многугольника непосредственно следует, что при его обходе будут делаться только левые повороты. Если р₁р₂р₃ образуют правый поворот, то р₂ не может быть крайней точкой, так как она является внутренней для треугольника (O р₁р₃ ). В зависимости от результата проверки угла, образуемого текущей тройкой точек, возможны два варианта продолжения просмотра:

1) р₁р₂р₃ образуют правый поворот. Удалить вершину р2, и проверить тройку р₀р₂р₃.

2) р₁р₂р₃ образуют левый поворот. Продолжить просмотр, перейдя к проверке тройки р₂р₃р₄.

Просмотр завершается, когда, обойдя все вершины, вновь приходим в вершину НАЧАЛО. Заметим, что вершина НАЧАЛО никогда не удаляется, так как она является крайней точкой, и поэтому при отходе назад после удаления точек, мы не сможем уйти дальше точки, предшествующей точке НАЧАЛО. Простой анализ показывает, что такой просмотр выполняется лишь за линейное время. Рассмотренный метод обхода границы многоугольника называется методом обхода Грэхема. Ниже дано более точное описание этого алгоритма

procedure ОБОЛОЧКА-ГРЭХЕМА(S)

1. Найти внутреннюю точку q.

2. Используя q как начало координат, упорядочить точки множества S лексикографически в соответствии с полярным углом и расстоянием от q. Организовать точки множества в виде кольцевого, дважды связанного списка со ссылками СЛЕД и ПРЕД и указателем НАЧАЛО на первую вершину. Значение true логической переменной f указывает на то, что вершина НАЧАЛО оказалась достигнутой при прямом продвижении по оболочке, а не в результате возврата.

3. Обход.

Begin

v:= НАЧАЛО; w:= ПРЕД[ v ]; f:= false;

while (СЛЕД[ v ] ¹ НАЧАЛО or f = false) do

Begin

if (СЛЕД[ v ]= w) then f:=true;

if (три точки: v, СЛЕД[ v ], СЛЕД[СЛЕД[ v ]] образуют левый поворот) then v:= СЛЕД[ v ] else

begin УДАЛИТЬ СЛЕД[ v ];

v:=ПРЕД[ v ]

End

End

End.

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

Итак, мы приходим к следующему выводу: выпуклая оболочка N точек на плоскости может быть найдена за время О(N log N) при памяти О(N) с использованием только арифметических операций и сравнений.

Если вспомнить нижнюю оценку, обсуждавшуюся в разд. 1, то видно, что этот простой и изящный алгоритм имеет оптимальное время выполнения. Однако имеется одно обстоятельство, которое может вызвать некоторое беспокойство у читателя, — это использование полярных координат. В самом деле, это предполагает выполнение преобразования координат, что может быть затруднительным в системах с ограниченным набором примитивных операций. Кроме того, рассмотренный алгоритм является оптимальным в худшем случае, но мы, однако, не изучили его поведение в среднем. И ещё одно замечание заключается в том, что так как алгоритм основывается на теореме 3, применимой только в случае плоскости, алгоритм не имеет обобщения на случай пространств более высокой размерности. Поэтому имеет смысл рассмотреть какие-то другие методы решения проблемы, не обременённые вышеуказанными недостатками.