Изменения
→Ссылки
{{notreadyready}}{{Определение|definition=Выпуклой оболочкой множества точек называется пересечение всех выпуклых множеств, содержащих все заданные точки.}}
Ниже приводятся основные алгоритмы построения выпуклых оболочек статического множества. Используются обозначения: <tex>n</tex> - размер входных данных, <tex>k</tex> - размер оболочки.
По-другому "Gift wrapping algorithm" (Заворачивание подарка).
Он заключается в том, что мы ищем выпуклую оболочку последовательно, против часовой стрелки, начиная с определенной точки.
== Описание Алгоритма ==
[[File:Graham1.png|thumb|250px|Промежуточный шаг алгоритма. Для точки <tex>p_i</tex> ищем следующую перебором.]] <br/><br/>
== Сложность ==
Добавление каждой точки в ответ занимает <tex>O(n)</tex> времени, всего точек будет <tex>k</tex>, поэтому итоговая сложность <tex>O(nk)</tex>. В худшем случае, когда оболочка состоит из всех точек сложность <tex>O(n^2)</tex>.
== Ссылки ==
= Алгоритм Грэхема =
Алгоритм заключается в том, что мы ищем точки оболочки последовательно, используя стек.
== Описание Алгоритма ==
[[File:Graham2.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
== Корректность ==
* Переход. Пусть для <tex>i-1)База</tex> точек оболочки совпадают. Для трех первых Докажем, что и для <tex>i</tex> точек утверждение, очевидно, выполняетсяони совпадут.
== Псевдокод ==
k = 2
for p = 3..n
while S[k - 1], S[k], S[p] has non-right orientationand k > 1
k--
swap(S[p], S[k + 1]) k++ return k+ 1
== Сложность ==
Сортировка точек занимает <tex>O(n \log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность этой части - <tex>O(n)</tex>. Суммарное время - — <tex>O(n \log n)</tex>.
== Ссылки ==
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%93%D1%80%D1%8D%D1%85%D0%B5%D0%BC%D0%B0 Русская статья — Wikipedia]
= Алгоритм Эндрю = Алгоритм, очень похожий на алгоритм Грехема. Он заключается в том, что мы находим самую левую и самую правую точки, ищем для точек над и под этой прямой выпуклую оболочку Грехемом - {{Acronym|для них начальные точки будут лежать на <tex>\pm inf</tex>, а сортировка по углу относительно далекой точки аналогична сортировке по координате|в этом легко убедиться, подставив в предикат поворота точку с 'бесконечно' координатой}}; после этого объединяем две оболочки в одну.
== Описание Алгоритма ==
[[File:andrew1.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
# Находим самую левую и самую правую точки множества - <tex>p_0</tex> и <tex>p_1</tex>.
# Делим множество на две части: точки над и под прямой.
# Для каждой половины ищем выпуклую оболочку Грехемом с условием, что сортируем не по полярному углу, а по координате.
# Сливаем получившиеся оболочки.
<br/>
== Корректность ==
<br/>
См. доказательство алгоритма Грехема.
<br/>
== Псевдокод ==
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество, <tex>n > 2</tex>
Andrew(S)
sort S[1..n] by x-coordinate backward(than by y backward)
k = 2
for p = 3..n
while S[k - 1], S[k], S[p] has non-right orientation
k--
swap(S[p], S[k + 1])
k++
sort S[k + 1..n] by x-coordinate (than by y)
for p = k + 1..n
while S[k - 1], S[k], S[p] has non-right orientation
k--
swap(S[p], S[k + 1])
return k + 1
== Сложность ==
Сортировка точек занимает <tex>O(n \log n)</tex> времени. При обходе каждая точка добавляется в ответ не более одного раза, поэтому сложность двух обходов - <tex> 2 \cdot O(n)</tex>. Суммарное время - <tex>O(n \log n)</tex>. Также можно отметить тот факт, что Эндрю в целом работает быстрее чем Грэхем, так как использует всего <tex>O(n)</tex> поворотов, в то время как Грэхем использует <tex>O(n \log n)</tex> поворотов.
== Ссылки ==
* [http://en.wikipedia.org/wiki/Gift_wrapping_algorithm Английская статья — WikipediaGraham_scan#Notes Одно предложение о нем]* [httphttps://ruen.wikipediawikibooks.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0 Русская статья — WikipediaAlgorithm_Implementation/Geometry/Convex_hull/Monotone_chain Имплементация на 13 языках]
= Алгоритм Чена =
== Описание Алгоритма ==
# Разобьем все множество на произвольные группы по <tex>m</tex> штук в каждой. Будем считать, что <tex>m</tex> нам известно. Тогда всего групп окажется <tex>r = n / m</tex>.# Для каждой группы запускаем Грехема.# Начиная с самой нижней точки ищем саму выпуклую оболочку Джарвисом, но перебираем не все точки, а по одной из каждой группы. == Сложность == На втором шаге алгоритма в каждой группе оболочка ищется за <tex>O(m \log m)</tex>, общее время - <tex>O(r m \log m) = O(n \log m)</tex>. На третьем шаге поиск каждой следующей точки в каждой группе занимает <tex>O(\log m)</tex>, так как точки уже отсортированы, и мы можем найти нужную бинпоиском. Тогда поиск по всем группам займет <tex dpi="130">O(r \log m) = O(\frac{n}{m} \log m)</tex>. Всего таких шагов будет <tex>k</tex>, значит общее время - <tex dpi="130">O(\frac{kn}{m} \log m)</tex>.Итоговое время - <tex>O(n (1+ \frac{k}{m})Найдем самую левую нижнюю точку \log m)</tex>. Несложно видеть, что минимум достигается при <tex>p_0m = k</tex> и самую правую нижнюю точку . В таком случае сложность равна <tex>p_1O(n \log k)</tex>.
<br/><br/>
[[File:hull1.png|thumb|200px|]]
Очевидно, что выпуклая оболочка всего множества является объединением выпуклых оболочек для верхнего и нижнего множества. Докажем, что алгоритм верно строит оболочку для верхнего множества, для правого нижнего рассуждения аналогичны.
Точки <tex>p_0</tex> и <tex>p_1</tex> принадлежат оболочке.
* Наоборот, пусть какой-то точки <tex>t</tex> в нашей оболочке нет, а должна быть.
Пойдем вниз рекурсии в те ветки, где есть <tex>t</tex>. В какой-то момент <tex>t</tex> окажется внутри некоторого треугольника. Но тогда возникает противоречие с тем, что <tex>t</tex> принадлежит выпуклой оболочке - противоречие.
Таким образом, наша оболочка совпадает с истинной, а значит алгоритм корректен.
== Реализация ==
Заметим, что длина высоты, опущенная из точки <tex>t</tex> на отрезок <tex>ab</tex>, пропорциональна векторному произведению <tex>[bt \cdot ba]</tex>, поэтому для сравнения можно использовать именно это. Векторное произведение эквивалентно предикату поворота, поэтому можно так же использовать и его.
== Псевдокод ==
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество. <tex>quick\_hull()</tex> - рекурсивная функция, находящая оболочку подмножества <tex>S</tex>. В реализации в конце каждого подмножества находятся эл-ты, точно не принадлежащие оболочке.
QuickHull(S)
find i such that S[i] has the highest x-coordinate and lowest y-coordinate
swap(S[1], S[i])
find i such that S[i] has the lowest x-coordinate and lowest y-coordinate
swap(S[n], S[i])
k = partition1(S) // разбиваем на те эл-ты, которые лежат над прямой и на остальные
a = quick_hull(S, 1, k)
b = quick_hull(S, k + 1, n);
swap(S[a..k], S[k + 1, b])
return start + (a - 1) + (b - k - 1) <br/>
quick_hull(S, start, end)
find i such that S[i], S[start], S[end] has maximum value
(a, b) = partition2(S, start, end, S[i]) //свапаем эл-ты S так, чтобы сначала были все эл-ты над прямой S[start]S[i], потом S[i]S[end], потом все остальное
c = quick_hull(S, start, a)
d = quick_hull(S, a + 1, b)
swap(S[c..a], S[a + 1..d])
return start + (a - c) + (d - b)
== Сложность ==