Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Предположим, что внутренняя точка уже найдена, а координаты других точек тривиальным образом преобразованы так, что найденная внутренняя точка оказалась в начале координат. Упорядочим лексикографически N точек в соответствии со значениями полярного угла и расстояния от начала координат. При выполнении сортировки, естественно, не нужно вычислять действительное расстояние между двумя точками, так как требуется лишь сравнить две величины. Можно работать с квадратом расстояния, избегая тем самым операции извлечения квадратного корня, но рассматриваемый случай еще проще. Сравнение расстояний необходимо выполнять лишь в случае, если две точки имеют один и тот же полярный угол. Но тогда они лежат на одной прямой с началом координат, и сравнение в этом случае тривиально.
Представив упорядоченные точки в виде лважлы сиязяннпт кпгтьтгрреео-^Спйска,, получаем ситуацию, представленную на рис. 3.6. Обратите внимание: если точка не является вершиной выпуклой оболочки, то она является внутренней точкой для некоторого треугольника (Opq), где р и q — последовательные вершины выпуклой оболочки. Суть алгоритма Грэхема состоит в однократном просмотре упорядоченной последовательности точек, в процессе которого удаляются внутренние точки. Оставшиеся точки являются вершинами выпуклой оболочки, представленными в требуемом порядке.
Просмотр начинается с точки, помеченной как НАЧАЛО, в качестве которой можно взять самую правую с наименьшей ординатой точку из данного множества, заведомо являющуюся
130
Г л. 3. Выпуклые оболочки: основные алгоритмы
вершиной выпуклой оболочки. Тройки последовательных точек многократно проверяются в порядке обхода против часовой стрелки с целью определить, образуют или нет они угол, больший или равный я. Если внутренний угол Р\р2Рг больше или равен я, то говорят, что pip2p3 образуют «правый поворот», иначе они образуют «левый поворот». Это можно легко определить, воспользовавшись формулой (3.4). Из выпуклости многоугольника непосредственно следует, что при его обходе будут делаться только левые повороты. Если р!р2рз образуют правый
Рис. 3.6. Начало обхода точек в методе Грэхема. Вершина р2 удаляется, если угол Р\Ргрг оказывается вогнутым.
поворот, то р2 не может быть крайней точкой, так как она является внутренней для треугольника (Орхрз). В зависимости от результата проверки угла, образуемого текущей тройкой точек, возможны два варианта продолжения просмотра:
1. Р1Р2Р3 образуют правый поворот. Удалить вершину р2 и проверить тройку рор\р$.
2. Р1Р2Р3 образуют левый поворот. Продолжить просмотр, перейдя к проверке тройки р2р3р*.
Просмотр завершается, когда, обойдя все вершины, вновь приходим в вершину НАЧАЛО. Заметим, что вершина НАЧАЛО никогда не удаляется, так как она является крайней точкой и поэтому при отходе назад после удаления точек, мы не сможем уйти дальше точки, предшествующей точке НАЧАЛО. Простой анализ показывает, что такой просмотр выполняется лишь за линейное время. Проверка угла может быть выполнена за фиксированное (постоянное) число операций. После каждой проверки происходит либо продвижение на одну точку (случай 2), либо удаляется точка (случай 1). Так как множество содержит лишь N точек, то продвижение вперед не может происходить более N раз, как не может быть удалено и более N точек. Рассмотренный метод обхода границы многоугольника является настолько полезным, что в дальнейшем мы будем называть его
Рз,
Начало-—*-*
3.3. Алгоритм построения выпуклой оболочки
131
методом обхода Грэхема. Ниже дано более точное описание этого алгоритма. В алгоритме S — это исходное множество из N точек на плоскости.
procedure ОБОЛОЧКА-ГРЭХЕМА (S)
1. Найти внутреннюю точку q.
2. Используя q как начало координат, упорядочить точки множества S лексикографически в соответствии с полярным углом и расстоянием от q. Организовать точки множества в виде кольцевого дважды связанного списка со ссылками СЛЕД и ПРЕД и указателем НАЧАЛО на первую вершину. Значение true логической переменной f указывает на то, что вершина НАЧАЛО оказалась достигнутой при прямом продвижении по оболочке, а не в результате возврата.
3. (Обход)
begin v := НАЧАЛО; о>:=ПРЕД[о]; f:= false; \уЫ1е(СЛЕД[у] Ф НАЧАЛО or f = false) do begin if CJlER[v] = w then f:=true;
if (три точки v, СЛЕДИ СЛЕД[СЛЕД[о]]
образуют левый поворот) then v := СЛЕД[и] else begin УДАЛИТЬ СЛЕДИ; у:=ПРЕДИ
end
end
end.
По окончании выполнения алгоритма список содержит упорядоченные нужным образом вершины оболочки.
Теорема 3.7. Выпуклая оболочка N точек на плоскости может быть найдена за время О (N log TV) при памяти О (N) с использованием только арифметических операций и сравнений.
Доказательство. Из предыдущего обсуждения алгоритма Грэхема видно, что в нем используются лишь арифметические операции и сравнения. Шаги 1 и 3 требуют линейного времени, тогда как шаг 2, являющийся определяющим по времени работы, выполняется за время O(NlogN). Для представления связного списка точек достаточно O(N) памяти.
