Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2017-12-11 | 222 |
5.00
из
|
Заказать работу |
|
|
Постановка задачи
Для точек a1, …, an, где n≥1, ai=(ai,1, ai,2)ÎR2 при i=1, …, n, указать вершины b1, …, bm выпуклой оболочки Conv(a1, …, an) в порядке их встречи при движении по ее границе. Заметим, что в общем случае Conv(a1, …, an) будет многоугольником, а в вырожденных случаях может получиться отрезок или точка. В случае отрезка выходом решающего поставленную задачу алгоритма должны быть две являющиеся его концами точки, а в случае точки - сама эта точка.
Построение выпуклой оболочки с помощью сортировки
Для решения задачи (см. [3]) построения Conv(a1, …, an) мы из точек a1, …, an выберем точки с минимальной первой координатой, среди которых затем найдем точку c, имеющую минимальную вторую координату. Таким образом, точка c = lexmin(a1, …,an) является лексикографическим минимумом точек a1, …,an и поэтому представляет собой вершину выпуклой оболочки Conv(a1, …, an). Именно с нее мы и начнем обход границы против часовой стрелки, положив b1=c и осуществив перед этим для удобства промежуточных вычислений параллельный перенос системы координат так, чтобы ее начало совпало с точкой c. После такого переноса на точках a1, …, an удается определить такой линейный порядок (≤), что для c1,c2 Î{a1-c, …,an–c} имеет место c1 ≤ c2, если либо det(c1,c2)>0, либо (det(c1,c2)=0)&((c1,1)2+(c1,2)2) < (c2,1)2+(c2,2)2).
Геометрический смысл такого упорядочения можно проиллюстрировать, если ввести полярную систему координат φ, r (-p<φ ≤p, r³0) с центром в точке c и далее положить, что c1 ≤ c2, если (φ1,r1) лексикографически не превосходит (φ2,r2), где числа φi, ri являются полярными координатами точки ci, i = 1,2.
Таким образом, c1 ≤ c2, если либо φ1 < φ2, либо (φ1 = φ2)&(r1 ≤ r2). Как только линейный порядок на элементах (точках) a1, …, an определен, немедленно можно воспользоваться сортировкой, для того чтобы отсортировать эти элементы по неубыванию в соответствии с введенным линейным порядком. После этого мы произведем за время O(n) просмотр отсортированного массива с целью получения итоговых точек b1, …, bm исходя из того условия, что точка bi+1 располагается строго слева от вектора, идущего из точки bi-1 в точку bi, что эквивалентно требованию того, чтобы det(bi-bi-1,bi+1-bi)>0.
|
Описанные действия конкретизируются алгоритмом, представляемым процедурой CONV_SORT (a, n), на вход которой подается массив точек a[1], …, a[n]. Итоговые точки b1, …, bm, являющиеся решением задачи, будут представлены в той же последовательности в первых m элементах a[1], …, a[m] массива a. Отметим также, что в процедуре CONV_SORT используется подпрограмма сортировки СОРТИРОВКА (a, n), выдающая отсортированный по неубыванию массив a.
procedure CONV_SORT (var a, n);
begin
c:= a[1]; m:= 1;
for i:= 2 to n do if a[i][1]<c[1] then begin
c:= a[i]; m:= i;
end else if a[i][1]=c[1] then if a[i][2]<c[2] then begin
c:= a[i]; m:= i;
end;
a[1]Ûa[m]; m:= 1;
for i:= 1 to n do a[i]:= a[i]-c;
СОРТИРОВКА(a, n);
for i:= 2 to n do if a[i] ¹ a[m] then begin
if m ³ 2 then while (m ³ 2)&(det(a[m]-a[m-1],a[i]-a[m]) £0) do m:= m-1;
m:= m+1; a[m]Ûa[i];
end;
for i:= 1 to m do a[i]:= a[i]+c;
end;
Временная сложность алгоритма построения выпуклой оболочки точек в случае, если используется СОРТИРОВКА с помощью d–кучи, где d³2, есть величина O(n×log n), если же используется быстрая СОРТИРОВКА, то временная сложность алгоритма оценивается сверху величиной O(n2), а в среднем алгоритм выполняется за время O(n×log n).
Задания для лабораторной работы № 6
Предлагается попарное сравнение различных использующих сортировку алгоритмов построения выпуклой оболочки n точек на плоскости с целочисленными координатами.
Варианты выбора пары алгоритмов A и B для сравнения:
Вариант d=2, …, 101
· А - используется сортировка d-кучей,
· В - используется сортировка (d+1)-кучей;
Вариант d=102, …., 200
· А - используется сортировка (d-100)-кучей,
· В - используется быстрая сортировка.
|
Задание.
1. Написать программу, реализующую алгоритм А и алгоритм В.
2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:
· количество n точек в исходном массиве a,
· натуральные числа q и w для псевдослучайного размещения всех n точек в двух режимах:
(1) в прямоугольнике со сторонами длиныq и w,
(2) на границе (на сторонах) этого прямоугольника.
Выходом данной программы должно быть время работы ТА алгоритма А и время работы ТВ алгоритма В в секундах.
3. Провести эксперименты на основе следующих данных:
3.1. q = 106, w = 106, n = 1, …, 106+1 с шагом 104, размещение точек псевдослучайное:
· в режиме (1),
· в режиме (2)
(нарисовать графики функций TА(n) и ТВ(n) для обоих случаев),
3.2. q = w = 0, …, 106 с шагом 104, n = 106, размещение точек псевдослучайное:
· в режиме (1),
· в режиме (2)
(нарисовать графики функций TА(n) и ТВ(n) для обоих случаев),
4. Сформулировать и обосновать вывод (на основе практических данных, для получения которых можно провести дополнительные эксперименты) о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.
|
|
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!