Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 219
Текст из файла (страница 219)
(Точное определение выпуклого многоугольника можно найти в упражнении 33.1-5.) Обозначим выпуклую оболочку множества Я как СН Я). Интуитивно можно представлять каждую точку множества ц в виде торчащего из доски гвоздя; тогда выпуклая оболочка будет иметь форму, полученную в результате наматывания на гвозди тугой резиновой нити. Пример множества точек и их выпуклой оболочки приведен на рис. 33.6. В этом разделе представлены два алгоритма, позволяющие построить выпуклую оболочку множества, состоящего из п точек. Оба алгоритма выводят верши- Рз Рп Рнс. 33.6. Множество точек Я = (ро, рп..., р1з) и нх выпуклая оболочка СН Я) 1064 Часть Ч!!.
Избранные темы ны выпуклой оболочки в порядке обхода против часовой стрелки. Время работы первого из них, известного как сканирование по Грэхему, равно 0 (и !яп). Второй алгоритм, который называется обходом по Джарвису, выполняется в течение времени О (пЬ), где Ь вЂ” юличество вершин выпуклой оболочки. Как видно из рис. 33.6, каждая вершина СН(Я) — это точка из множества Я. Это свойство используется в обоих алгоритмах. В них принимается решение, какие точки из множества Я выступают в роли вершин выпуклой оболочки, а какие следует отбросить.
Фактически имеется несюлью методов построения выпуклой оболочки в течение времени О (и !кп). И при сканировании по Грэхему, и при обходе по Джарвису используется метод, который называется "выметанием по кругу". Вершины обрабатываются в порядке возрастания их полярных углов, которые они образуют с некоторой базисной вершиной.
В число других методов входят те, что перечислены ниже. ° В методе лоследоватеяьиого счета (! псгешепш! ше!Ьоб) точки сортируются слева направо, в результате чего получается последовательность (ры рз, ..., р„). На г-м этапе выпуклая оболочка г — 1 самых левых точек СН((ры рз, ...,р; ~)) обновляется в соответствии с положением г'-й слева точки, после чего формируется оболочка СН ((ры рз,..., р!)). В упражнении 33.3-6 предлагается показать, что этот метод можно реализовать так, чтобы время его работы было равно 0 (и 1к и). ° В методе декомлозииии (бечЫе-апб-соп<ре ше!Ьоб) множество и точек за время 0 (и) разбивается на два подмножества, в одном из которых содержится !и/2~! самых левых точек, а во втором — 1и/21' самых правых точек. Затем рекурсивно строятся выпуклые оболочки этих подмножеств, которые затем объединяются с помощью одного остроумного метода в течение времени О (и).
Время работы этого метода описывается уже знакомым рекуррентным соотношением Т(п) = 2Т(п/2) + 0(п), решение которого равно О (п 1к и). ° Метод отсечения и лоиска (рпше-алб-зеагсЬ ше!Ьоб) подобен алгоритму, описанному в разделе 9.3, время работы юторого в наихудшем случае ведет себя линейно. В нем строится верхняя часть (или "верхняя цепь") выпуклой оболочки путем повторного отбрасывания фиксированной части оставшихся точек до тех пор, пока не останется толью верхняя цепь выпуклой оболочки. Затем то же самое выполняется с нижней цепью. В асимптотическом пределе этот метод самый быстрый: если выпуклая оболочка содержит Ь вершин, время его работы равно О (и!к Ь). Построение выпуклой оболочки множества точек — задача, интересная сама по себе. Кроме того, алгоритмы, предназначенные для решения неюторых других Глава 33.
Вычислительная геометрия 1065 задач вычислительной геометрии, начинают работу с построения выпуклой оболочки. Например, рассмотрим двумерную задачу о поиске пары самых дальних точек (Тагг)зезг-ра)г ргоЫеш): в заданном на плоскости множестве и точек требуется найти две, расстояние между которыми является максимальным.
В упражнении 33.3-3 предлагается доказать, что обе эти точки должны быть вершинами выпуклой оболочки. Пару самых дальних вершин выпуклого и-угольника можно найти в течение времени 0 (и), хотя здесь мы не станем доказывать это утверждение. Таким образом, путем построения выпуклой оболочки и входных точек за время 0 (и 1я и) и последующего поиска пары самых дальних точек среди вершин полученного в результате выпуклого многоугольника, можно найти пару самых дальних точек из произвольного множества и точек за время 0 (и 1я и). Сканирование по Грэхему В методе сканирования по Грэхему (Огалаш'з зсап) задача о выпуклой оболочке решается с помощью стека Я, сформированного из точек-кандидатов. Все точки входного множества Я заносятся в стек, а потом точки, не являющиеся вершинами СН Я), со временем удаляются из него.
По завершении работы алгоритма в стеке Я остаются только вершины оболочки СН Щ) в порядке их обхода против часовой стрелки. В качестве входных данных процедуры бкАнАм БсАн выступает множество точек Я, где (ф ) 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. Вычислительная геометрия иЫ)е встречается вершина, в которой не производится поворот влево, такая вершина снимается со стека. (Выполняется именно проверка того, что поворот — не левый, а не проверка того, что поворот правый. Такая проверка исключает наличие развернутого угла в полученной в результате выпуклой оболочке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
