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

Тимофеев Александр Евгеньевич, группа 403

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

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

Задача построения выпуклой оболочки является одной из важных проблем вычислительной геометрии. Выпуклую оболочку множества точек $X$ можно определить следующим образом: это пересечение всевозможных выпуклых множеств, содержащих $X$. В случае конечного числа $n$ точек из $X$:

$\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\}.$

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

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

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

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

Рассмотрим сам алгоритм:

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

Стартовый симплекс, который по ходу работы алгоритма будет расти до окончательной оболочки, можно создать из любых $d+1$ точек, исходя из условия на $X$. Но в реальности это условие общего положения (general position) можно заменить на требование возможности выбрать $d$-мерный симплекс. Имеет смысл выбрать его таким образом, чтобы как можно больше точек уже оказалось в нем, поэтому его вершинами следует сделать точки с минимальными и максимальными координатами. Если таких точек не будет хватать, произведем добор произвольными.

Дальнейшие шаги алгоритма позволяют добавлять к промежуточной выпуклой оболочке новые вершины. По сути выбирается оптимальная в каком-то смысле внешняя точка $p$, а затем определяется множество $V$ видимых из этой точки граней. Данные видимые грани отделены от невидимых множеством граничных ребер (horizon ridges). Далее граничные ребра и точка $p$ образуют новые грани, видимые грани удаляются. Тем самым совершен переход к новой промежуточной выпуклой оболочке. Такое описание является обобщенным и ему также соответствует randomized incremental algorithm, в котором точка $p$ выбирается случайным образом. В нашем случае точка $p$ будет наиболее отдаленной точкой от плоскости текущей рассматриваемой грани $F$, что гарантирует присутствие $p$ в итоговой выпуклой оболочке. Также можно выбрать $p$ как наиболее отдаленную точку среди всех пар (грань-"самая дальняя точка этой грани").

Как решается проблема определения граничных ребер, когда уже выбрана точка $p$? Множество внешних точек (outside set) грани $F$ представляет из себя множество точек (возможно не всех), из которых эта грань видна. Поэтому если $p$ из множества внешних точек грани $F$, то это означает, что $F$ будет видна из $p$, и следует начать поиск границы именно с соседей $F$. Пусть $H$ - соседняя к $F$ грань. Если $H$ видна, то следует проверить таким же образом и соседей $H$. Если $H$ не видна, то мы наткнулись на участок границы, и рассматривать соседей $H$ нет смысла.

Получив граничные ребра, строим новые грани. Требуется обновить списки соседей и понять, какие внешние точки были захвачены. Захватить мы могли только те точки, которые были внешними для уничтоженных на этом шаге граней. То есть множество таких точек - это объединение множеств внешних точек граней из $V$. Распределяем эти точки по множествам внешних точек для новых граней.

Алгоритм будет продолжать свою работу до тех пор, пока не останется ни одного пустого множества внешних точек.

3 Литература

• 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
• Clarkson , K. L., Mehlhorn , K., and Seidel , R. 1993. Four results on randomized incremental constructions. Comput. Geom. Theory Appl. 3, 185–211. Also in Lecture Notes in Computer Science. Vol. 577, pp. 463– 474.