Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
метод обхода Грэхема (шаг 3 алгоритма ОБОЛОЧКА-ГРЭХЕМА), требующий лишь линейное время. Теперь получена выпуклая оболочка Pi U Р2.
Если многоугольник Pi имеет тп вершин, а Р2 имеет п вершин, то время выполнения этого алгоритма равно 0(m-\-n), что со всей очевидностью является оптимальным. Так что теперь известно, что U(N) = O(N), и решением рекуррентного соотношения (3.8) в этом случае является T(N)= 0(N\ogN). Таким образом, имеет место
Теорема 3.9. Выпуклая оболочка объединения двух выпуклых многоугольников может быть найдена за время, пропорциональное суммарному числу их вершин.
Побочным результатом описанного метода слияния является вычисление (нахождение) «опорных прямых», если они имеют-
Рис. 3.13. Точка р находится вне многоугольника Р2. Многоугольник Р2 находится внутри угла, определяемого точками v, р, и. Точки v и и разбивают последовательность вершин многоугольника Р2 на две цепи. Одну из них можно удалить, а слияние вершин второй цепи с упорядоченным множеством вершин многоугольника Pi можно выполнить за линейное время.
Pj
изменения полярного угла с началом в р. При движении по одной цепи угол увеличивается, при движении по другой — уменьшается. Одна из этих двух цепей, являющаяся выпуклой по направлению к точке р, может быть немедленно удалена, так как ее вершины будут внутренними точками CH(SiUS2).Другая цепь Р2 и граница Pi представляют два упорядоченных списка, содержащих в сумме не более N вершин. За время О (N) их можно слить в один список вершин Pi U Р2, упорядоченных по углу относительно точки р.
5. Теперь к полученному списку можно применить
3.3. Алгоритм построения выпуклой оболочки
143
ся, для двух выпуклых многоугольников. Опорной прямой к выпуклому многоугольнику Р называется прямая /, проходящая через некоторую вершину многоугольника Р таким образом, что внутренность Р целиком находится по одну сторону от / (в некотором смысле понятие опорной прямой аналогично понятию касательной). Очевидно, что два выпуклых многоугольника Pi и Р2 с п и m вершинами соответственно, таких, что один не лежит целиком внутри другого, имеют общие опорные прямые (по крайней мере не более 2min(n, m)). Если уже получена выпуклая оболочка объединения Pi и Рг, то опорные прямые вычисляются в результате просмотра списка вершин CH(PiUP2). Каждая пара последовательных вершин CH(Pi U Рг), одна из которых принадлежит Pi, а другая Р2, определяет опорную прямую.
Препарата и Хонг (Preparata, Hong (1977)) предложили иной метод нахождения выпуклой оболочки объединения двух непересекающихся выпуклых многоугольников, основанный на нахождении за линейное время двух опорных прямых к этим многоугольникам. Однако этот метод здесь демонстрироваться не будет.
3.3.6. Динамические алгоритмы построения выпуклой оболочки
В каждом из рассматривавшихся ранее алгоритмов требовалось, чтобы все обрабатываемые данные (а именно точки) были целиком представлены до начала работы алгоритма. Во многих прикладных областях, где возникают геометрические задачи, в частности связанные с обработкой данных в реальном времени, такое ограничение отсутствует, а ряд вычислений должен выполняться по мере поступления точек (данных). В общем случае алгоритм, обрабатывающий данные по мере поступления, называется открытым, а алгоритм, обрабатывающий всю совокупность целиком, называется закрытым.
Основной чертой открытых алгоритмов является отсутствие ограничений на время коррекции, что равносильно тому, что новый элемент данных (точка) вводится по запросу сразу же после того, как завершается коррекция, связанная с предыдущим элементом данных. Будем называть временной интервал между вводом двух последовательных элементов данных задержкой поступления данных. Более сложный в смысле предъявляемых требований случай применения открытых алгоритмов возникает, когда задержка поступления данных находится вне контроля алгоритма. Иначе говоря, данные поступают не по запросу алгоритма, а подаются на вход алгоритма в некоторые моменты времени, никак не связанные с работой алгоритма.
144
Г л. 3. Выпуклые оболочки: основные алгоритмы
Однако мы будем считать, что поступление данных происходит (распределено) равномерно по времени. В такой ситуации коррекция должна выполняться за время, не превышающее постоянную задержку поступления данных. Алгоритмы, работающие в таком режиме, и называются соответственно алгоритмами реального времени. Следует отметить, что обычно открытые алгоритмы глобально являются менее эффективными по сравнению с соответствующими закрытыми алгоритмами (какая-то плата должна быть внесена за открытость алгоритма).
Целью этого раздела является разработка открытых алгоритмов построения выпуклой оболочки, в полной мере удовлетворяющих конкретным требованиям.
Задача В05 (ОТКРЫТЫЙ АЛГОРИТМ ДЛЯ ВЫПУКЛОЙ ОБОЛОЧКИ). На плоскости задана последовательность из N точек ри . .., pN. Требуется найти их выпуклую оболочку, организовав обработку таким образом, чтобы после обработки точки pi имелась СН({рь . . . , pi}).
