Участник:RS42/Quickhull

Свойства и структура алгоритмов

Общее описание алгоритма

Задача построения выпуклой оболочки является одной из важных проблем вычислительной геометрии. Выпуклую оболочку множества точек [math]\displaystyle{ X }[/math] можно определить следующим образом: это пересечение всевозможных выпуклых множеств, содержащих [math]\displaystyle{ X }[/math]. В случае конечного числа [math]\displaystyle{ n }[/math] точек из [math]\displaystyle{ X }[/math]:

[math]\displaystyle{ \mathrm{Conv}(X)=\left\{\left.\sum_{i=1}^{n} \alpha_i x_i\ \right| (\forall i: \alpha_i\ge 0)\wedge \sum_{i=1}^{n} \alpha_i=1 \right\}. }[/math]

Алгоритм Quickhull позволяет провести построение в пространстве произвольной размерности [math]\displaystyle{ d }[/math]. Результатом работы является множество [math]\displaystyle{ d-1 }[/math]-мерных граней (facets) и вершин (vertices) полученной выпуклой оболочки.

Математическое описание алгоритма

Наложим на множество [math]\displaystyle{ X }[/math] следующее условие: любые [math]\displaystyle{ d+1 }[/math] точки аффинно независимы (что тождественно тому, что они не лежат в одной [math]\displaystyle{ d-1 }[/math] плоскости). Выпуклая оболочка будет задаваться списком вершин и граней. Для каждой грани известны ее вершины, ее соседние грани и уравнение гиперплоскости, в которой эта грань лежит. Ребро (ridge) определяется как пересечение двух соседних граней и имеет размерность [math]\displaystyle{ d-2 }[/math]. Граница грани состоит из ребер.

Нам понадобится вычисление ориентированного расстояния от некоей точки [math]\displaystyle{ x }[/math] до гиперплоскости (signed distance to hyperplane). Зададим начало координат в точке [math]\displaystyle{ O }[/math], плоскость определяется нормалью [math]\displaystyle{ \vec n }[/math] и смещением [math]\displaystyle{ h }[/math] относительно начала координат. Тогда ориентированное расстояние будет равно [math]\displaystyle{ (\vec x, \vec n) - h }[/math], где [math]\displaystyle{ \vec x = x - O }[/math]. Если ориентированное расстояние положительно, то можно сказать, что точка находится выше плоскости (или плоскость видна из точки). В нашем случае все грани выпуклой оболочки во время построения будут иметь такие нормали и смещения, что для точек внутри оболочки расстояния до каждой плоскости будут неположительными.

create a simplex of d+1 points
for each facet F
  for each unassigned point p
    if p is above F
      assign p to F's outside set
for each facet F with non-empty outside set
  select the furthest point p of F's outside set
  initialize the visible set V to F
  for all unvisited neighbors N of facets in V
    if p is above N
      add N to V
  the boundary of V is the set of horizon ridges H
  for each ridge R in H
    create a new facet from R and p
     link the new facet to its neighbors
  for each new facet G
    for each unassigned point q in an outside set of a facet in V
      if q is above G
        assign q to outside set of G
  delete the facets in V

Литература

• Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical Software, 22(4):469-483, Dec 1996, http://www.qhull.org