Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 220
Текст из файла (страница 220)
Развернутых углов быть не должно, посюльку ни одна из вершин выпуклого многоугольника не может быть выпуклой комбинацией других вершин этого многоугольника.) После снятия со стека всех вершин, в которых при переходе к точке р; не производится левый поворот, в стек заносится точка р,.
На рис. 33.7б-л показано состояние стека Я после каждой итерации цикла 1ог. По окончании работы в строке 10 процедуры Оклнлм Бслн возвращается стек Я. На рис. 33.7м показана полученная выпуклая оболочка. В сформулированной ниже теореме формально доказывается юрректность процедуры Оклнлм Ясли. Теорема 33.1 (Корректность сканирования по Грэхему). Если процедура Оялнлм Бслн обрабатывает множество точек Я, где ~Я~ > 3, то по завершении этой процедуры стек Я будет содержать (в направлении снизу вверх) только вершины оболочки СН Я) в порядке обхода против часовой стрелки.
Доказаювольсагао. После выполнения строки 2 в нашем распоряжении имеется последовательность точек (ры рз,..., р ). Определим подмножество точек Я; = = (ро,рм...,рг) при 1 = 2,3,...,т. Множество точек Я вЂ” Я„, образуют те из них„что были удалены из-за того, что их полярный угол относительно точки ро совпадает с полярным углом некоторой точки из множества Я . Эти точки не принадлежат выпуклой оболочке СН Я), так что СН (Я ) = СН (Я). Таким образом, достаточно показать, что по завершении процедуры Оклнлм Бслн стек 5 состоит из вершин оболочки СН (Я ) в порядке обхода против часовой стрелки, если эти точки просматриваются в стеке снизу вверх. Заметим, что точно так же, как точки ро, ры р,„являются вершинами оболочки СН Я), точки ро, ры р; являются вершинами оболочки СН (Я;).
В доказательстве используется сформулированный ниже инвариант цикла. В начале каждой итерации цикла )ог в строках 6-9 стек Я состоит (снизу вверх) только из вершин оболочки СИЯ 1) в порядке их обхода против часовой стрелки. Инициализация. При первом выполнении строки 6 инвариант поддерживается, поскольку в этот момент стек Я состоит только из вершин Яз — — Яг и и это множество трех вершин формирует свою собственную выпуклую оболочку. Кроме того, если просматривать точки снизу вверх, то они будут расположены в порядке обхода против часовой стрелки.
Сохранение. При входе в новую итерацию цикла 1ог вверху стека Я находится точка р; и помещенная туда в конце предыдущей итерации (или перед 1068 Часть Чй. И эбранные тем, Рив Ра ° Рн :'Ро 0з Рб ° Р в Г/ Р ./'РЗ Р ° . р Рп Рз рз Рб Рв Рз Рн ° Ро Ра Рзо ° Рзо ° Рн Рв Рп Ро Рз Рб Ро Рз Рп ° Рз Ро ) Ро Ри ° Рзо Рб Рб Рн° Рз Ра ° Рз Ро а) Рис. 33.7. Обработка Ро о) Рис... отка процедурой Оклнлм Бс слн множеств а точек , показанного на первой нтерацие, еи, когда в = 3~. П б е но п~р~д тем после Рб. Пу~~ также Р троке 9 в стек точка Распоп Я очкои оженная в стеке , а точка .
е , когда точка точки, что рб еще туда не доб рр находится и после -й и до .авлена, стек содержит те а ог. оэто с же му, согласно инва ва ианту Глава 33. Выч ычислительная ге ометрия 1069 Рзо ° Рзо ° Рь Рь Рз Рз Рз Рз Ра Ро ж) Ро з) Рз Рз Ра Ра Ро и) Ро к) Рз Рз Ра Ра Ро Ро м) л) цикла, в этот мом их обхо ент стек "~~ в~р~ины СН 5 содержит тол в порядке как в него олжим размышлять о ма ив ерх. матривать их снизу вв полярнь " него будет добавле ена точка рь Об Я непосредстве венно перед тем ныи угол точки от рагимся к рис.
33. точки р и п р; относительно точки с..8а. Поскольку от чки ро больше, чем поля ный точка р была б л рьр р; сворачивает в ( )ла ы снята со стека влево (в противном с ока), после д~Ж~~~~~й~~ ом случае и только вершины СН(Я ' 1 )в нем буд с ения в стек Я точки ( р; до уг содержаться вершины Часть Ч11. Избранные темы 1070 Рис. 33.8. Доказательство корректности процедуры Оклнлм 8слн СН (ф 1.1 (рД). При этом они будуг расположены в порядке обхода против часовой стрелки, если просматривать их снизу вверх. Теперь покажем, что множество вершин СН (ф 0 (р;)) совпадает с множеством точек СН (Я;). Рассмотрим произвольную точку рн снятую со стека во время выполнения г-й итерации цикла 1ог, и пусть р, — точка, расположенная в стеке Я непосредственно под точкой р~ перед снятием со стека последней (этой точкой р„может быть точка р ). Угол ~р„р~р; не сворачивает влево, и полярный угол точки р~ относительно точки ро больше полярного угла точки р,.
Как видно из рис. 33.86, точка р~ должна располагаться либо внутри треугольника, образованного точками ро, р, и р;, либо на стороне этого треугольника (но не совпадать с его вершиной). Очевидно, что поскольку точка р~ находится внутри треугольника, образованного тремя другими точками множества Я,, она не может быть вершиной СН (Я,). Так как р~ не является вершиной СН (ф), можно записать соотношение (33.1) Пусть Р; — множество точек, снятых со стека во время выполнения г-й итерации цикла 1ог. Поскольку равенство (33.1) применимо ко всем точкам множества Р;, в результате его многократного применения можно показать, что выполняется равенство СН Я, — Р;) = СН(Я;).
Однако Я; — Р; = = ф О (р,), поэтому мы приходим к заключению, что СН(ф О (р;)) = = СН٠— Р,) = СНЯ;). Мы показали, что сразу после вытеснения из стека Я точки р; в нем содержатся только вершины СН Я,) в порядке их обхода против часовой стрелки, если просматривать их в стеке снизу вверх. Последующее увеличение на единицу значения переменной г приведет к сохранению инварианта цикла в очередной итерации. Глава 33. Вычислительная геометрия 1071 Завершение.
По завершении цикла выполняется равенство ! = т+ 1, поэтому из инварианта цикла следует, что стек Я состоит только из вершин СН (Я ), т.е. из вершин СН (Я). Эти вершины расположены в порядке обхода против часовой стрелки, если они просматриваются в стеке снизу вверх. На этом доказательство завершается. й Теперь покажем, что время работы процедуры ОкАНАм Вслх равно 0 (и !8 п), где и = ~ф. Выполнение строки 1 занимает время 6 (о). Для сортировки полярных углов методом слияния или пирамидальной сортировки, а также сравнения углов с помощью векторного произведения, как описано в разделе 33.1, в строке 2 требуется время 0 (и !я п). (Все точки с одним и тем же значением полярного угла, кроме самой удаленной, можно удалить в течение времени О (и).) Выполнение строк 3-5 занимает время О (1).
В силу неравенства гп < п — 1 цикл !ог в строках 6-9 выполняется не более п — 3 раз. Так как выполнение процедуры Рози занимает время 0(1), на выполнение каждой итерации требуется время 0(1), если не принимать во внимание время, затраченное на выполнение цикла зг!и!е в строках 7 — 8. Таким образом„общее время выполнения цикла 1ог равно О (п), за исключением времени выполнения вложенного в него цикла згййе. Покажем с помощью группового анализа, что для выполнения всего цикла ий!!е потребуется время 0(п). При ! = 0,1,...,гл каждая точка р; попадает в стек Я ровно по одному разу. Как и при анализе процедуры Мыт!Рог в разделе 17.1, нетрудно заметить, что каждой операции Розн соответствует не более одной операции РоР.
По крайней мере три точки (ро, р1 и р ) никогда не снимаются со стека, поэтому всего выполняется не более гп — 2 операций Рог. В каждой итерации цикла згн!!е выполняется одна операция Рог, следовательно, всего этих итераций не более гп — 2. Так как проверка в строке 7 занимает время 0(1), каждый вызов Рор также требует О (1) времени, и в силу неравенства т < п — 1, полное время, которое требуется для выполнения цикла зяЫ!е, равно О (и). Таким образом, время выполнения процедуры ОкАнАМ Ясли составляет О (и !8 и). Обход по Джарвису При построении выпуклой оболочки множества точек Я путем обкода ло Джарвису (Уагч1з'з шаге!з) используется метод, известный как упаковка лаке>ил (рас!сабе старр!п8) или упаковка подарка (81Й итарр!пб).
Время выполнения алгоритма равно 0 (пй), где й — количество вершин СН (Я). В том случае, когда Ь равно о (!8 и), обход по Джарвису работает быстрее, чем сканирование по Грэхему. Интуитивно обход по Джарвису моделирует обертывание плотного куска бумаги вокруг множества Я. Начнем с того, что прикрепим конец бумаги к нижайшей точке множества, т.е. к той же точке рс, с которой начинается сканирование по Грэхему. Эта точка является вершиной выпуклой оболочки. Натянем бумагу вправо, Часть ЧИ.
Избранные темы 1072 Левая цепь, Правая цепь Левая цепь ' Правая цепь Рис. 33.9. Работа алгоритма обхода по Джарвису чтобы она не провисала, после чего переместим ее вверх до тех пор, пока она не коснется какой-то точки. Эта точка также должна быть вершиной выпуклой оболочки.
Сохраняя бумагу натянутой, продолжим наматывать ее на множество вершин, пока не вернемся к исходной точке ро. Если говорить более формально, то при обходе по Джарвису строится последовательность Н = (ро, ры..., рь 1) вершин СН Я). Начнем с точки ро. Как видно из рис.
33.9, следующая вершина выпуклой оболочки р1 имеет наименьший полярный угол относительно точки ро. (При наличии совпадений выбирается точка, самая удаленная от точки ро.) Аналогично, точка рз имеет наименьший полярный угол относительно точки р1 и т.д. По достижении самой высокой вершины, скажем, рь (совпадения разрешаются путем выбора самой удаленной из таких вершин), оказывается построенной (рис. 33.9) правая цепь (пя)п сиваш) оболочки СН Я). Чтобы сконструировать левую цепь (1ей сиваш), начнем с точки рь и выберем в качестве рь+1 точку с наименьшим полярным углом относительно точки ры но относительно отрицательного нанравления оси х.
Продолжаем выполнять зту процедуру, отсчитывая полярный угол от отрицательного направления оси х, пока не вернемся к исходной точке ро. Обход по Джарвису можно было бы реализовать путем единообразного обхода вокруг выпуклой оболочки, т.е. не прибегая к отдельному построению правой и левой цепей. В такой реализации обычно отслеживается угол последней стороны выпуклой оболочки и накладывается требование, чтобы последовательность Глава 33. Вычислительная геометрия 1073 углов, образованных сторонами оболочки с положительным направлением оси х строго возрастала (в интервале от 0 до 2к радиан).
Преимущество конструирования отдельных цепей заключается в том, что исключается необходимость явно вычислять углы; для сравнения углов достаточно методов, описанных в разделе 33.1. При надлежащей реализации время выполнения обхода по Джарвису равно О (пЛ). Для каждой из Ь вершин оболочки СН(Я) находится вершина с минимальным полярным углом. Каждое сравнение полярных углов длится в течение времени 0 (1), если используются методы, описанные в разделе 33.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
