Алгоритм быстрой оболочки

Алгоритм быстрой оболочки — алгоритм построения выпуклой оболочки на плоскости. Использует идею быстрой сортировки Хоара

Описание

Множество точек разбивается на два подмножества, каждое из которых будет содержать одну из ломаных, соединение которых дает многоугольник выпуклой оболочки.

1. Возьмем две крайние точки множества S — левую Л и правую П. Проведем прямую через них. Обозначим через S1 подмножество точек, расположенных выше или на прямой, проходящей через точки Л и П, а через S2 — подмножество точек, расположенных ниже или на той же прямой.
2. Рассмотрим верхнее подмножество S1. Выберем точку Pi, имеющую наибольшее расстояние от прямой ЛП (треугольник ЛPiП имеет наибольшую площадь). Если таких точек несколько, выбираем ту, у которой угол PiЛП наибольший. Точка Pi является вершиной выпуклой оболочки множества. В самом деле, если через точку Pi провести прямую, параллельную прямой ЛП, то выше этой прямой не окажется ни одной точки множества S. Возможно, на построенной прямой окажутся другие точки, но, согласно сделанному выбору, Pi из них самая левая. Т. о. Точка Pi не может быть представлена выпуклой комбинацией двух других точек множества S.Построим прямые ЛPi и PiП. Точки, расположенные справа от обеих прямых, могут быть исключены из дальнейшего рассмотрения, поскольку они являются внутренними точками треугольника ЛPiП, то есть не принадлежат CH(S) — границе выпуклой оболочки.
3. Теперь рассмотрим подмножество точек S11, расположенных слева от прямой ЛPi или на ней, и подмножество точек S12, расположенных справа от прямой PiП или на ней. Для каждого из подмножеств строим выпуклую оболочку. Выпуклая оболочка множества S1 образуется склейкой упорядоченных списков вершин CH(S11) и CH(S12).
4. Решаем задачу для S2.

• Quickhull example3.svg
• Quickhull example6.svg
• Quickhull example7.svg

Сложность алгоритма

Сложность алгоритма состоит из сложности построения двух подмножеств рассматриваемого множества O(N) и сложностей решения подзадач для каждого из подмножеств: T(N) = T(a) + T(b) + O(N).

В лучшем случае, когда задача разбивается на две равномощные подзадачи, сложность алгоритма является решением рекурсивного уравнения:

(1) T(N) = 2 T(N/2) + O(N) =>

(2) T(N) = O(N log N).

В худшем случае:

(3) T(N) = T(1) + T(N 1) + O(N) =>

(4) T(N) = O(N2).

Лемма Решением уравнения (1) является функция (2) Пусть N = 2k. Тогда T(2k) = 2 T(2k 1) + C 2k ; T(2k 1) = 2 T(2k 2) + C 2k 1 => T(2k) = 4 T(2k 2) + 2 °C 2k 1 + С 2k = 4 T(2k 2) + 2 °C 2k => T(2k) = 2m T(2k m) + m С 2k При m = k (= logN) алгоритм заканчивает работу: T(N) = N T(1) + C logN N = O(N logN)

См. также

• Алгоритм Грэхема
• Алгоритм Джарвиса
• Алгоритм Чана

Ссылки

• [github.com/Ingener74/polypuch/blob/master/src/libs/Polygon/Convex/convex_hoare.cpp Реализация на c++]
• [www.cs.princeton.edu/courses/archive/spr09/cos226/demo/ah/QuickHull.html] (англ.)

Отрывок, характеризующий Алгоритм быстрой оболочки

– В такую минуту, – повторил князь Андрей, – для них это только такая минута, в которую можно подкопаться под врага и получить лишний крестик или ленточку. Для меня на завтра вот что: стотысячное русское и стотысячное французское войска сошлись драться, и факт в том, что эти двести тысяч дерутся, и кто будет злей драться и себя меньше жалеть, тот победит. И хочешь, я тебе скажу, что, что бы там ни было, что бы ни путали там вверху, мы выиграем сражение завтра. Завтра, что бы там ни было, мы выиграем сражение!
– Вот, ваше сиятельство, правда, правда истинная, – проговорил Тимохин. – Что себя жалеть теперь! Солдаты в моем батальоне, поверите ли, не стали водку, пить: не такой день, говорят. – Все помолчали.
Офицеры поднялись. Князь Андрей вышел с ними за сарай, отдавая последние приказания адъютанту. Когда офицеры ушли, Пьер подошел к князю Андрею и только что хотел начать разговор, как по дороге недалеко от сарая застучали копыта трех лошадей, и, взглянув по этому направлению, князь Андрей узнал Вольцогена с Клаузевицем, сопутствуемых казаком. Они близко проехали, продолжая разговаривать, и Пьер с Андреем невольно услыхали следующие фразы:
– Der Krieg muss im Raum verlegt werden. Der Ansicht kann ich nicht genug Preis geben, [Война должна быть перенесена в пространство. Это воззрение я не могу достаточно восхвалить (нем.) ] – говорил один.
– O ja, – сказал другой голос, – da der Zweck ist nur den Feind zu schwachen, so kann man gewiss nicht den Verlust der Privatpersonen in Achtung nehmen. [О да, так как цель состоит в том, чтобы ослабить неприятеля, то нельзя принимать во внимание потери частных лиц (нем.) ]
– O ja, [О да (нем.) ] – подтвердил первый голос.
– Да, im Raum verlegen, [перенести в пространство (нем.) ] – повторил, злобно фыркая носом, князь Андрей, когда они проехали. – Im Raum то [В пространстве (нем.) ] у меня остался отец, и сын, и сестра в Лысых Горах. Ему это все равно. Вот оно то, что я тебе говорил, – эти господа немцы завтра не выиграют сражение, а только нагадят, сколько их сил будет, потому что в его немецкой голове только рассуждения, не стоящие выеденного яйца, а в сердце нет того, что одно только и нужно на завтра, – то, что есть в Тимохине. Они всю Европу отдали ему и приехали нас учить – славные учители! – опять взвизгнул его голос.
– Так вы думаете, что завтрашнее сражение будет выиграно? – сказал Пьер.
– Да, да, – рассеянно сказал князь Андрей. – Одно, что бы я сделал, ежели бы имел власть, – начал он опять, – я не брал бы пленных. Что такое пленные? Это рыцарство. Французы разорили мой дом и идут разорить Москву, и оскорбили и оскорбляют меня всякую секунду. Они враги мои, они преступники все, по моим понятиям. И так же думает Тимохин и вся армия. Надо их казнить. Ежели они враги мои, то не могут быть друзьями, как бы они там ни разговаривали в Тильзите.