234
правки
Изменения
→Алгоритм QuickHull
Таким образом, наша оболочка совпадает с истинной, а значит алгоритм корректен.
== Реализация ==
Заметим, что длина высоты, опущенная из точки <tex>t</tex> на отрезок <tex>ab</tex>, пропорциональна векторному произведению <tex>[bt \cdot ba]</tex>, поэтому для сравнения можно использовать именно это.
== Псевдокод ==
Inplace-реализация алгоритма. <tex>S[1..n]</tex> - исходное множество. <tex>quick_hullquick\_hull()</tex> - рекурсивная функция, находящая оболочку подмножества <tex>S</tex>. В реализации в конце каждого подмножества находятся эл-ты, точно не принадлежащие оболочке.
QuickHull(S)
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)
