Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
2. Вершина v принадлежит области ф. Вершина v является критической. Ищется опорная прямая из вершины v к цепи (<7ь qi-\). Если эта прямая содержит qr (г < i), то вершины qr+\, ..., qi удаляются, a v берется в качестве новой q,+\
Рис. 4.11. При обходе границы многоугольника Р, следующей за выделенной вершиной qi, возможны четыре случая.
(рис. 4.11(b)). Ясно, что v является вершиной выпуклой оболочки (критической точкой), так как она является внешней по отношению к текущей оболочке (q\, q2, <7м). Проведение опорной прямой эквивалентно построению conv(<7i, qr,
Qr+\, Ям).
3. Вершина v принадлежит области ф. Вершина v является критической, и она берется в качестве qi+i. Действительно (рис. 4.11(c)), v является внешней по отношению к текущей оболочке (<7i, q2, ..., qi, <7м), и так как она находится справа от прямой, проходящей через <7,--i и qi (и ориентированной в направлении от qi-\ к qi), то угол (qi-xqiv) является выпуклым. (Заметим, что рис. 44.11(c) иллюстрирует случай, соответствующий рис. 4.10(b).)
(а)
(Ъ)
208
Гл. 4. Выпуклые оболочки: расширения и приложения
4. Вершина v принадлежит области @). В этом случае граница многоугольника заходит внутрь выпуклой оболочки. Как и в случае 1, рассмотренном выше, будем продвигаться по границе многоугольника до тех пор, пока не достигнем первого ребра, обладающего следующим свойством: одна из его вершин является внешней по отношению к области (D или совпадает с qM. В последнем случае процедура завершается. В первом же случае вершина, являющаяся внешней по отношению к области ф, находится либо в области © (такая ситуация обрабатывается способом, указанным в пункте 3 выше), либо в области © (такая ситуация обрабатывается способом, указанным в пункте 2 выше) (рис. 4.11(d)). Действительно, обозначим через С часть границы многоугольника от <7, до qM- С является простой кривой. Кроме того, прежде чем она пересечет qiqM, она не может выйти ни в область, находящуюся справа от вертикальной прямой, проходящей через <7м, ни в область, находящуюся слева от вертикальной прямой, проходящей через q\. Так как многоугольник Р простой, то С не может пересечь ни одну из границ карманов Ки .... Ki-i, и, следовательно, она не может пересечь ни одну из крышек этих карманов. Отсюда следует, что С может пересечь только qiqM. Если она не пересекает указанный отрезок, то она заканчивается в точке qM-
Предыдущее обсуждение включает доказательство корректности любой реализации, в которой обработка случаев 1—4 производится указанным выше способом. Дадим формальное описание одного из таких алгоритмов. Наиболее подходящими структурами данных являются: (1) очередь Р, содержащая последовательность {р2, Рз.....рм); (2) стек Q для хранения
последовательности (<7о, qu q% • • •) — ввиду того, что для вставки и удаления точек выпуклой оболочки используется механизм «последний вошел — первый вышел», где <7о — фиктивная вершина, имеющая ту же абсциссу, что и р\ = q\, но меньшую ординату и обеспечивающая единообразие обработки. Как было сказано выше, и — это вершина на границе многоугольника Р, непосредственно предшествующая вершине q,, a v — текущая вершина. Упорядоченная тройка вершин (siw) называется правым поворотом, если до находится справа от прямой, проходящей через s и t с учетом направления от s к t; в противном случае она называется левым поворотом. Кроме того, наряду с обычным использованием операции U<=v, означающей: «ЗАТОЛКНУТЬ v В U», операция ВЫТОЛКНУТЬ U означает: «v<=U; игнорировать v»; q, обозначает вершину, находящуюся на вершине стека, а ПЕРЕДНИЙ (Р) обозначает первый элемент очереди Р,
4.1. Расширения и варианты
procedure ОБОЛОЧКА-МНОГОУГОЛЬНИКА (Pi.....Рм)
1. begin Р<=(р2, .... рмУ>
2. Q<=qQ;
3. Q<=Pu
4. while^ ф 0) do
5. begin v<=P;
6. — правый поворот) (¦области ©,®,®*) then
7. if((uqtv) — правый поворот (* области
®,®*) then
8. if((qMqiV) — правый поворот
(¦область ф*) then Q<=v
9. else (* область Я) *)
10. >уЫ1е(ПЕРЁДНИЙ(Р) находится
слева от qMqt или на нем) do ВЫТОЛКНУТЬ Р
11. else (* область © *)
12. \уЖ1е(ПЕРЕДНИЙ(Р) находится слева
от QiQi-i или на нем) do ВЫТОЛКНУТЬ Р
13. else (* область ©*)
14. begin while ((<7;_]<7;i>) — левый поворот) do ВЫТОЛКНУТЬ Q;
15. Q<=v end
end
end.
Анализ сложности алгоритма ОБОЛОЧКА-МНОГОУГОЛЬНИКА не вызывает затруднений. После инциализации (строки 1—3) каждая вершина границы посещается в точности один раз, прежде чем она будет либо принята (строки 8, 15), либо отвергнута (строки 10, 12). Обработка каждой вершины многоугольника осуществляется за постоянное время. При построении опорной прямой в цикле while (строка 14) на каждую операцию удаления затрачивается постоянное время. Учитывая, что последовательности (pi, . . ., рм) и (<7ь . .., qR) содержат О(М) элементов, а рассуждения, аналогичные приведенным, можно применить и для построения нижней оболочки прямоугольника Р, то в завершение имеем следующую теорему:
Теорема 4.12. Выпуклая оболочка простого многоугольника с N вершинами может быть построена за оптимальное время в (Л/) при использовании памяти объемом Q(N).
