Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Соответствующий БЬ1СТРОБОЛ-метод разбивает множество S m N точек на два подмножества, каждое из которых будет содержать одну из двух ломаных, соединение которых дает многоугольник выпуклой оболочки. Начальное разбиение множества определяется прямой, проходящей через две точки / и г, имею-
') [Aho, Hopcrott, Ullman (1974)]-с. Ill русск. изд. и [Knuth (1973)]-с. 140 русск. изд. — Прим. перев.
3.3. Алгоритм построения выпуклой оболочки
137
щие соответственно наименьшую и наибольшую абсциссы (рис. 3.10), точно так же, как в варианте алгоритма Грэхема, предложенном Эндрью (см. разд. 3.3.2). Обозначим через S<'> подмножество точек, расположенных выше или на прямой, проходящей через / и г, а через S<2> симметричным образом определяемое подмножество точек, расположенных ниже или на той же самой прямой. (Более точно, S(2)} не является разбие-
нием множества 5, так как S(1) П S(2) Э {/, г}; эта несущественная деталь, обеспечивающая удобную симметрию, никоим образом не должна вводить в заблуждение читателя.)
Рис. 3.10. Точки I, г и h определяют разбиение множества S<". Все точки, попавшие в заштрихованный треугольник, не рассматриваются.
На каждом последующем шаге обработка множеств, подобных S(1) и S(2), выполняется следующим образом (для конкретности мы рассмотрим множество на рис. 3.10). Определим точку /г, для которой треугольник (hlr) имеет максимальную площадь среди всех треугольников {(plr): psSO}, а если таких точек имеется более одной, то выбираем ту из них, у которой угол Z (hlr) больше. Заметим, что точка h гарантированно принадлежит выпуклой оболочке. Действительно, если провести через точку h прямую, параллельную отрезку 1г, то выше этой прямой не окажется ни одной точки множества S. Возможно, кроме точки h на этой прямой окажутся другие точки из множества S, но, согласно сделанному нами выбору, h является самой левой из них. Так что точка h не может быть представлена в виде выпуклой комбинации двух других точек множества 5.
Затем строятся две прямые: одна L\, направленная из / в h, другая L2 — из h в г. Для каждой точки множества S(1) определяется ее положение относительно этих прямых. Ясно, что ни одна из точек не находится одновременно слеза как от L\, так и от L2, кроме того, все точки, расположенные справа от обеих
138
Гл. 3. Выпуклые оболочки: основные алгоритмы
прямых, являются внутренними точками треугольника (Irh) и поэтому могут быть удалены из дальнейшей обработки. Точки, расположенные слева от L\ или на ней (и расположенные справа от L2), образуют множество [); аналогично образуется множество S(U 2). Вновь образованные множества S(1> 1) и S(t>2) передаются на следующий уровень рекурсивной обработки.
Данный метод использует в качестве примитивных процедуры вычисления площади треугольника и определения положения точки относительно прямой. Каждая из этих процедур требует нескольких операций сложения и умножения.
Объяснив в общих чертах предлагаемый подход, укажем способ, позволяющий подогнать под общую схему обработки явную аномалию, связанную с первоначальным разбиением множества точек. Соответствующий выбор начальных значений {/о, г0) точек / и г может быть выполнен следующим образом. Выберем в качестве / точку (хо, г/о), имеющую наименьшую абсциссу, а в качестве г0 возьмем точку (х0, у0 — е), где е — произвольное малое положительное число. Это приводит к тому, что в качестве исходной прямой, разбивающей множество на части, выбирается вертикальная прямая, проходящая через /о. После завершения алгоритма точка г0 удаляется (положив е = 0, делаем точки /0 и г0 совпадающими).
Теперь можно привести более формальное описание предлагаемого метода. Предполагается, что множество S содержит по крайней мере две точки, а функция САМАЯДАЛЬНЯЯТОЧ-КА(5;/, г) вычисляет точку lieS описаным выше способом; кроме того, БЫСТРОБОЛ возвращает в качестве результата упорядоченный список точек, а «*» обозначает операцию сцепления (конкатенации) списков.
function БЫСТРОБОЛ^; I, г)
1. begin if(S = {/, г}) then return(/, г) (* выпуклая оболочка состоит из единственного ориентированного ребра *)
2. else begin h := САМАЯДАЛЬНЯЯТОЧКАф I,г);
S(1):= точки множеств S, расположенные слева от lh или на ней;
4. 5(2) :== точки множества S, расположенные слева от hr или на ней;
5. return БЫСТРОБОЛ^'»;/,г)* (БЫСТРОБОЛ(5(2>; h,r) - К)
end
end
Таким образом, если уже имеется функция БЫСТРОБОЛ, то поставленную задачу можно решить с помощью следующей простой программы:
3.3. Алгоритм построения выпуклой оболочки
begin 10 = (х0, г/о) := точка множества 5 с наименьшей абсциссой;
Га ¦== (*о. Уо — е);
БЫСТРОБОЛ(5; 10,г0);
удалить точку г0(*это эквивалентно тому, чтобы положить е = 0 *)
end.
Для того чтобы выделить из множества S подмножества S(1) и S(2) (с неявным удалением точек, попадающих внутрь треугольника (Irh)), как это делается в строках 2, 3 и 4 приведенной выше программы, требуется O(N) операций. Затем следует рекурсивное обращение к функции для обработки S(1) и S(2). Теперь, если мощность каждого из этих множеств не превосходит мощности множества S, умноженной на некоторую константу, меньшую 1, и это условие имеет место на каждом уровне рекурсии, то время выполнения алгоритма равно 0(N\ogN). Однако в худшем случае БЫСТРОБОЛ, несмотря на его простоту, имеет тот же недостаток, что и БЫСТРСОРТ, дающий время выполнения 0(N2).
