Квикхалл

Quickhull — это метод вычисления выпуклой оболочки конечного набора точек в n -мерном пространстве. Он использует подход «разделяй и властвуй» , аналогичный подходу быстрой сортировки , от которого и произошло его название. Его временная сложность в худшем случае для 2-мерного и 3-мерного пространства равна $O(n^{2})$, но когда точность ввода ограничена $O(\log n)$ бит, предполагается, что его временная сложность в худшем случае составит $O(n\log r)$, где $n$ количество входных точек и $r$ – количество обработанных точек (до $n$).

N-мерный Quickhull был изобретен в 1996 году К. Брэдфордом Барбером, Дэвидом П. Добкиным и Ханну Хухданпаа. Это было расширение планарного алгоритма Quickhull Джонатана Скотта Гринфилда 1990 года, хотя авторы 1996 года не знали о его методах. Вместо этого Барбер и др. описывают его как детерминированный вариант алгоритма Кларксона и Шора 1989 года.

Эта анимация изображает алгоритм Quickhull в двух измерениях.

Алгоритм

Шаги 1-2: Разделите точки на два подмножества.

Двумерный алгоритм можно разбить на следующие этапы:

1. Найдите точки с минимальными и максимальными координатами x, поскольку они всегда будут частью выпуклой оболочки. Если существует много точек с одинаковым минимумом/максимумом x, используйте точки с минимумом/максимумом y соответственно.
2. Используйте линию, образованную двумя точками, чтобы разделить набор на два подмножества точек, которые будут обрабатываться рекурсивно. Далее мы опишем, как определить часть корпуса над линией; часть корпуса ниже линии можно определить аналогично.
3. Определите точку над линией с максимальным расстоянием от линии. Эта точка образует треугольник с двумя точками на линии.
4. Точки, лежащие внутри этого треугольника, не могут быть частью выпуклой оболочки и поэтому их можно игнорировать на следующих шагах.
5. Рекурсивно повторите два предыдущих шага на двух линиях, образованных двумя новыми сторонами треугольника.
6. Продолжайте до тех пор, пока не останется точек, рекурсия не завершится и выбранные точки не составят выпуклую оболочку.

Шаги 3–5: Найдите точку с максимальным расстоянием, игнорируйте точки внутри треугольника и выполните рекурсию.

Шаг 6: Повторяйте, пока не останется точек.

Проблема более сложна в случае более высокой размерности, поскольку корпус состоит из многих граней; структура данных должна учитывать это и записывать линию/плоскость/гиперплоскость (гребень), общую для соседних граней. Для размеров d :

1. Выберите d + 1 точку из набора, не имеющую общей плоскости или гиперплоскости. Это формирует начальную оболочку с гранями Fs[] .
2. Для каждого F в Fs[] найдите все неназначенные точки, находящиеся «над» ним; т. е. указывая от центра корпуса, и присваивать их «внешнему» набору FO, связанному с F . Алгоритм сохраняет инвариант, согласно которому каждая точка, которая не была добавлена ​​в оболочку, но потенциально могла бы быть ее вершиной, присваивается ровно одному внешнему множеству.
3. Для каждого F с непустым FO :
   1. Найдите точку p в FO, находящуюся на максимальном расстоянии от F, и добавьте ее к оболочке. Обратите внимание, что p не обязательно будет вершиной конечной оболочки, поскольку позже ее можно будет удалить.
   2. Создайте видимый набор V и инициализируйте его F. значением Расширьте V во всех направлениях для соседних фасетов Fv не перестанут быть видимыми фасеты до тех пор, пока из p . То, что Fv видно из p, означает, что p выше Fv.
   3. Тогда граница V образует набор гребней горизонта H .
   4. Пусть Fnew[] будет набором фасетов, созданных из p и всех гребней в H .
   5. Отмените назначение всех точек во внешних наборах фасетов в V. Для каждого нового фасета в Fnew[] выполните шаг (2), рассматривая только эти недавно неназначенные точки, чтобы инициализировать его внешний набор. Обратите внимание, что каждая точка, которая остается неназначенной в конце этого процесса, находится внутри текущей оболочки.
   6. Удалите теперь внутренние фасеты в V из Fs[] . Добавьте новые фасеты из Fnew[] в Fs[] и продолжите итерацию.

Псевдокод для 2D набора точек

Input = a set S of n points 
Assume that there are at least 2 points in the input set S of points

function QuickHull(S) is
    // Find convex hull from the set S of n points
    Convex Hull := {} 
    Find left and right most points, say A & B, and add A & B to convex hull 
    Segment AB divides the remaining (n − 2) points into 2 groups S1 and S2 
        where S1 are points in S that are on the right side of the oriented line from A to B, 
        and S2 are points in S that are on the right side of the oriented line from B to A 
    FindHull(S1, A, B) 
    FindHull(S2, B, A) 
    Output := Convex Hull
end function

function FindHull(Sk, P, Q) is
    // Find points on convex hull from the set Sk of points 
    // that are on the right side of the oriented line from P to Q
    if Sk has no point then
        return
    From the given set of points in Sk, find farthest point, say C, from segment PQ 
    Add point C to convex hull at the location between P and Q 
    Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2 
        where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented 
        line from P to C, and S2 are points on the right side of the oriented line from C to Q. 
    FindHull(S1, P, C) 
    FindHull(S2, C, Q) 
end function

Псевдокод, специализированный для 3D-случая, можно получить у Джордана Смита. Он включает в себя аналогичную стратегию «максимальной точки» для выбора стартового корпуса. Если эти максимальные точки вырождены, то и все облако точек тоже.

См. также

• Алгоритмы выпуклой оболочки

Ссылки

• Дэйв Маунт. «Лекция 3: Дополнительные алгоритмы выпуклой оболочки» . Архивировано из оригинала 11 апреля 2001 года.

Внешние ссылки

• Реализация QuickHull (GDC 2014) — презентация алгоритма с подробностями реализации в 3D.