Алгоритмы - построение и анализ (1021735), страница 220
Текст из файла (страница 220)
Все точки входного множества Я заносятся в стек, а потом точки, не являющиеся вершинами СН Я), со временем удаляются из него. По завершении работы алгоритма в стеке Я остаются только вершины оболочки СН Щ) в порядке их обхода против часовой стрелки. В качестве входных данных процедуры бкАнАм БсАн выступает множество точек Я, где (ф ) 3. В ней вызывается функция Тор(Я), которая возвращает точку, находящуюся на вершине стека Я, не изменяя при этом его содержимое. Кроме того, используется также функция 1Чвхт То Тог(Я), которая возвращает точку, расположенную в стеке Я на одну позицию ниже от верхней точки; стек о' прн этом не изменяется. Вскоре будет показано, что стек Я, возвращаемый процедурой бкАнАМ БсАн, содержит только вершины СН Я), причем расположенные в порядке обхода против часовой стрелки, если просматривать их в стеке снизу вверх.
ОКАнАм БсАнЯ) 1 Пусть ро — точка из множества Я с минимальной координатой у или самая левая из таких точек при наличии совпадений 2 Пусть (ры рз,..., р ) — остальные точки множества ь), отсортированные в порядке возрастания полярного угла, измеряемого против часовой стрелки относительно точки ро (если полярные углы нескольких точек совпадают, то из множества удаляются все эти точки, кроме одной, самой дальней от точки ро) 3 Рнзн(ро, ~) 4 РБЯН(ры о) 5 РББН(рз, Я) 6 хогг' -Згот 1066 Часть ЧП. Избранные темы 7 бо и 1п1е (пока) угол, образованный точками Хихт То Тов(Я), Тог(Я) и р,, образует не левый поворот (при движении по ломаной, образованной этими точками, мы движемся прямо или вправо) 8 до Рор(Я) 9 Рази(р;, Я) 1О ге1пгп Я Работа процедуры Оилнлм Ясли проиллюстрирована на рис. 33.7. Выпуклая оболочка, содержащаяся на данный момент в стеке 5, на каждом этапе показана серым цветом.
В строке 1 процедуры выбирается точка ро с минимальной координатой у; при наличии нескольких таких точек выбирается крайняя левая. Поскольку в множестве Я отсутствуют точки, расположенные ниже точки ро, и все другие точки с такой же координатой у расположены справа от точки ро, ро — вершина оболочки СН Я).
В строке 2 остальные точки множества Я сортируются в порядке возрастания их полярных углов относительно точки ро. При этом используется тот же метод, что и в упражнении 33.1-3, т.е. сравнение векторных произведений. Если полярные углы двух или нескольких точек относительно точки ро совпадают, все такие точки, кроме самой удаленной от точки ро, являются выпуклыми комбинациями точки ро и самой удаленной от нее из числа таких точек, поэтому все они исключаются из рассмотрения. Обозначим через гп количество оставшихся точек, отличных от точки ро.
Величина полярного угла каждой из точек множества Я, измеряемого в радианах относительно точки ро, принадлежит полуоткрытому интервалу [О, и). Поскольку точки отсортированы по величине возрастания их полярных углов, они расположены относительно точки ро в порядке обхода против часовой стрелки. Обозначим эту упорядоченную последовательность точек как (ры рз,..., р,„). Заметим, что точки р1 и р являются вершинами оболочки СН(Я) (см.
упражнение 33.3-1). На рис. 33.7а изображены точки из рис. 33.6, последовательно пронумерованные в порядке возрастания полярных углов относительно точки ро. В остальной части процедуры используется стек Я. В строках 3-5 стек инициализируется, и в него заносятся снизу вверх три точки ро, р1 и рз. На рис.
33.7а показано начальное состояние стека Я. В каждой итерации цикла 1ог в строках 6-9 обрабатывается очередная точка подпоследовательности (рз, р4,..., р ). Цель этой обработки — сделать так, чтобы в результате в стеке Я в порядке размещения снизу вверх содержались вершины оболочки СН ((ро, ры..., р;)) в порядке обхода против часовой стрелки. В описанном в строках 7-8 цикле згЫ!е точки удаляются из стека, если будет обнаружено, что они не являются вершинами выпуклой оболочки. При обходе выпуклой оболочки против часовой стрелки в каждой вершине должен производиться поворот влево.
Каждый раз, ко~па в цикле 1067 Глава 33. Вычислительная геометрия иЫ)е встречается вершина, в которой не производится поворот влево, такая вершина снимается со стека. (Выполняется именно проверка того, что поворот — не левый, а не проверка того, что поворот правый. Такая проверка исключает наличие развернутого угла в полученной в результате выпуклой оболочке. Развернутых углов быть не должно, посюльку ни одна из вершин выпуклого многоугольника не может быть выпуклой комбинацией других вершин этого многоугольника.) После снятия со стека всех вершин, в которых при переходе к точке р; не производится левый поворот, в стек заносится точка р,.
На рис. 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 (о).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
