Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Подход, основанный на поиске нижних оценок, в данной ситуации неприменим даже для случая упорядоченной оболочки, так что следует довольствоваться тривиальной нижней оценкой Q(N). Поэтому вполне естественно искать алгоритмы, имеющие в худшем случае сложность, меньшую 0(N log N). И ряд таких алгоритмов, каждый со сложностью O(N), был предложен. К сожалению, некоторые из них оказываются неработоспособными в некоторых очень частных случаях i[Sklansky (1972); Shamos (1975а)], но другие алгоритмы правильно решают данную задачу. Среди последних следует упомянуть довольно сложный алгоритм Маккаллума — Эйвиса [McCallum, Avis (1979)], использующий два стека. Впоследствии были предложены два новых алгоритма, использующих один стек, — первый Ли [Lee (1983а)], а второй Грэхемом и Яо [Graham, Yao 1983)]. Ниже описывается авторский вариант алгоритма Ли.
Пусть р\ — самая левая вершина заданного простого многоугольника, а (р\, р2, ¦ ¦ ¦ , Pn) —упорядоченная циклическая последовательность его вершин (за вершиной Pn следует р{). Предполагается, что внутренность Р находится по правую сторону при обходе его границы в указанном порядке, т. е. циклическая последовательность вершин многоугольника ориентирована по часовой стрелке (рис. 4.8). Пусть рм — самая правая вершина. Ясно, что р\ и рм являются граничными точками выпуклой оболочки многоугольника Р. Кроме того, они разбивают последовательность вершин многоугольника на две цепи: одна от pi до рм, другая от рм до р\. Достаточно рассмотреть построение выпуклой оболочки лишь для цепи (ри р2, рм), которую, согласно использовавшейся ранее терминологии (разд. 3.3.2), будем называть верхней оболочкой. Пусть подпоследовательность (q\, q2, ..., qR) последовательности (р\, р2, ¦ ¦ ¦ .... рм), у которой qi = pi и qR = рм, — искомая выпуклая оболочка многоугольника. Каждое из ребер qiqi+i (i=l, ...
4.1. Расширения и варианты
205
.... г—1) можно рассматривать как «крышку» «кармана» Ki, где карман Ki — это подцепочка последовательности (рь р2, ...
рм), первой и последней вершинами которой являются qi и qt+i соответственно.
Рис. i
!. Верхняя оболочка простого многоугольник^
4i = Ps
Алгоритм проходит цепь (р\, ..., рм) и последовательно строит крышки всех карманов. Особым событием в ходе работы алгоритма является обнаружение вершины типа q, образующей карман вместе с последней найденной вершиной типа q. Такие вершины q будем называть критическими вершинами. Заметим, однако, что не каждая критическая вершина является вершиной окончательной выпуклой оболочки. Они являются лишь кандидатами в число таковых. По сути дела, единственное, что утверждается перед_з_авегщ?ндем работы алгоритма, это то, что построенная к этому моменту последовательность критических вершин (qu q2, .. •) согласуется с предположением о простоте многоугольника Р (более детальная характеристика будет дана далее).
Карман Н(.
4.9. Карман
. Так что теперь внимание будет сконцентрировано на процедуре перехода от одной критической точки к другой. Эта процедура называется шагом продвижения.
Предположим, что граница многоугольника просмотрена от вершины р\ до ps (s М) и вершина ps = q, является критической. Соответствующая ситуация показана на рис. 4.9, где карман Ki-i закрыт крышкой qi-iqi. Обозначим через и вершину
206
Гл. 4. Выпуклые оболочки: расширения и приложения
границы Р, предшествующую <?,. В зависимости от положения и относительно ориентированного отрезка qMqi имеют место два случая.
1. Вершина и находится справа от q^q-i или на нем. В этом случае в вертикальной полосе, задаваемой вершинами qx и qM, можно рассмотреть и три области, обозначенные на рис. 4.10(a)
Рис. 4.10. Области, в которых может находиться вершина v, следующая за qi (показаны два случая — в зависимости от относительною положения и и qMqi).
©, ф и ф. Эти области определяются: прямой, проходящей через вершины <7,_! и qi\ лучом, являющимся продолжением отрезка qtu, и частью границы многоугольника Р, соответствующей карману Ki-\.
2. Вершина и находится слева от qiuqi. В этом случае в дополнение к предыдущим определим еще одну область 0), показанную на рис. 4.10(b).
Обозначим через v вершину, следующую за qt на границе многоугольника Р. Вершина v находится в одной из областей, определенных выше. Если v находится в областях© или ф, то она является критической вершиной, а если она находится в областях ф или 0, то она не является критической. Рассмотрим четыре указанных случая более подробно.
1. Вершина v принадлежит области ф. В этом случае граница многоугольника заходит в карман. Будем продвигаться по границе до тех пор, пока не достигнем первого ребра границы, одна из вершин которого w находится вне кармана, т. е. в области ф (рис. 4.11(a)). Так как многоугольник Р простой, а карман и его крышка также образуют простой многоугольник, то, согласно теореме о жордановой кривой, граница многоугольни-
4.1. Расширения и варианты
207
ка Р обязательно пересекает крышку кармана. Далее обрабатываем w, как вершину v в случае, когда v принадлежит области ф, рассматриваемом ниже.
