Изменения

Перейти к: навигация, поиск
Ссылки
 
{{ready}}
{{Определение
|definition=Выпуклой оболочкой множества точек называется пересечение всех выпуклых множеств, содержащих все заданные точки.}}
 
Еще одно определение:
{{Определение
|definition=Выпуклой оболочкой множества точек называется линейная комбинация минимального набора точек, дающая все остальные точки.}}
Ниже приводятся основные алгоритмы построения выпуклых оболочек статического множества. Используются обозначения: <tex>n</tex> - размер входных данных, <tex>k</tex> - размер оболочки.
== Описание Алгоритма ==
[[File:Graham1.png|thumb|250px|Промежуточный шаг алгоритма. Для точки <tex>p_i</tex> ищем следующую перебором.]] <br/><br/>
1) # Возьмем самую правую нижнюю точку <tex>p_0</tex> нашего множествас самой маленькой у-координатой (если таких несколько, берем самую правую из них). Добавляем ее в ответ. 2) # На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> среди всех недобавленных точек и <tex>p_0</tex> {{Acronym|с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию)|Считать углы не нужно, можно просто подставить в функцию сравнения предикат поворота}}. Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.
== Сложность ==
Добавление каждой точки в ответ занимает <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>-ой]]
1)# Находим самую правую нижнюю точку множества <tex>p_0</tex>нашего множества с самой маленькой у-координатой (если таких несколько, берем самую правую из них), добавляем в ответ. 2)# Сортируем все остальные точки {{Acronym|по полярному углу относительно <tex>p_0</tex>|Сортировка с компаратором 'Предикат поворота'}}3)# Добавляем в ответ <tex>p_1</tex> - самую первую из отсортированных точек. 4)# Берем следующую по счету точку <tex>t</tex>. Пока <tex>t</tex> и две последних точки в текущей оболочке <tex>p_i</tex> и <tex>p_{i-1}</tex> образуют неправый поворот (вектора <tex>p_i t</tex> и <tex>p_{i-1} p_i</tex>), удаляем из оболочки <tex>p_i</tex>. 5)# Добавляем в оболочку <tex>t</tex>. 6)# Делаем п.5, пока не закончатся точки.
== Корректность ==
Докажем, что на каждом шаге множество <tex>p_i</tex>-тых является выпуклой оболочкой всех уже рассмотренных точек. Доказательство проведем по индукции.
1)* База. Для трех первых точек утверждение, очевидно, выполняется.
2)* Переход. Пусть для <tex>i-1</tex> точек оболочки совпадают. Докажем, что и для <tex>i</tex> точек они совпадут.
Рассмотрим истинную оболочку <tex>ch(S \cup {i}) = ch(S) \cup i \setminus P</tex>, где <tex>P</tex> - множество всех точек из <tex>ch(S)</tex>, видимых из <tex>i</tex>. Так как мы добавляли точки в нашу оболочку против часовой стрелки и так как <tex>i</tex>-тая точка лежит в <tex>ch(S \cup i)</tex>, то <tex>P</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>.
== Ссылки ==
= Алгоритм Эндрю =
Алгоритм, очень похожий на алгоритм Грехема. Он заключается в том, что мы находим самую левую и самую правую точки, ищем для точек над и под этой прямой выпуклую оболочку Грехемом - {{Acronym|для них начальные точки будут лежать на <tex>\pm inf</tex>, а сортировка по углу относительно далекой точки аналогична сортировке по координате|в этом легко убедиться, подставив в предикат поворота точку с 'бесконечно' координатой}}; после этого объединяем две оболочки в одну.
== Описание Алгоритма ==
[[File:andrew1.png|thumb|400px|Промежуточный шаг алгоритма. Зелеными линиями обозначена текущая выпуклая оболочка, синими - промежуточные соединения точек, красными - те отрезки, которые раньше входили в оболочку, а сейчас нет. На текущем шаге при добавлении точки <tex>p</tex> последовательно убираем из оболочки точки с <tex>i+3</tex>-ей до <tex>i+1</tex>-ой]]
1)# Находим самую левую и самую правую точки множества - <tex>p_0</tex> и <tex>p_1</tex>. 2)# Делим множество на две части: точки над и под прямой. 3)# Для каждой половины ищем выпуклую оболочку Грехемом с условием, что сортируем не по полярному углу, а по координате. 4)# Сливаем получившиеся оболочки.
<br/>
== Сложность ==
Сортировка точек занимает <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/Graham_scan#Notes Одно предложение о нем]
* [https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain Имплементация на 13 языках]
= Алгоритм Чена =
== Описание Алгоритма ==
1)# Разобьем все множество на произвольные группы по <tex>m</tex> штук в каждой. Будем считать, что <tex>m</tex> нам известно. Тогда всего групп окажется <tex>r = n / m</tex>. 2)# Для каждой группы запускаем Грехема.  3)# Начиная с самой нижней точки ищем саму выпуклую оболочку Джарвисом, но перебираем не все точки, а по одной из каждой группы.
== Сложность ==
[[File:hull.png|thumb|250px|Промежуточный шаг алгоритма. Для прямой <tex>p_i p_1</tex> нашли точку <tex>p</tex>. Над прямыми <tex>p_i p</tex> и <tex>p p_1</tex> точек нет, поэтому переходим к следующей прямой <tex>p_0 p_i</tex>.]]
1)# Найдем самую левую нижнюю точку <tex>p_0</tex> и самую правую нижнюю точку <tex>p_1</tex>(Если таких несколько, выберем среди таких нижнюю и верхнюю соответственно)2)# Возьмем все точки выше прямой <tex>p_0 p_1</tex>. 3)# Найдем среди этого множества точку <tex>p_i</tex>, наиболее отдаленную от прямой (если таких несколько, взять самую правую). 4)# Рекурсивно повторить шаги 2-3 для прямых <tex>p_0 p_i</tex> и <tex>p_i p_1</tex>, пока есть точки. 5)# Добавить в ответ точки <tex>p_0 .. p_i .. p_1</tex>, полученные в п. 3. 6)# Повторить пункты 2-5 для <tex>p_1 p_0</tex> (то есть для "нижней" половины). 7)# Ответ - объединение списков из п. 5 для верхней и нижней половины.
<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>, поэтому для сравнения можно использовать именно это. Векторное произведение эквивалентно предикату поворота, поэтому можно так же использовать и его.
== Псевдокод ==
Анонимный участник

Навигация