Выпуклая оболочка в n-мерном пространстве — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Выберем любые две точки <tex>p_1</tex> и <tex>p_2</tex>. Далее из оставшихся выберем точку <tex>p_3</tex>, которая не лежит на прямой, образованной точками <tex>p_1</tex> и <tex>p_2</tex>. После этого выберем точку <tex>p_4</tex>, которая не лежит на плоскости, образованной точками <tex>p_1, p_2</tex> и <tex>p_3</tex>. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.
 
Выберем любые две точки <tex>p_1</tex> и <tex>p_2</tex>. Далее из оставшихся выберем точку <tex>p_3</tex>, которая не лежит на прямой, образованной точками <tex>p_1</tex> и <tex>p_2</tex>. После этого выберем точку <tex>p_4</tex>, которая не лежит на плоскости, образованной точками <tex>p_1, p_2</tex> и <tex>p_3</tex>. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.
  
Так мы получили тетраэдр <tex>p_1 p_2 p_3 p_4</tex>, который является выпуклой оболочкой этих четырёх точек. Сделаем random shuffle оставшихся точек <tex>p_5, ..., p_n</tex> и будем добавлять их по одной в выпуклую оболочку. Если <tex>p_i</tex> внутри или на границах выпуклой оболочки, то выпуклая оболочка не меняется на этом шаге. Иначе из имеющейся выпуклой оболочки надо удалить все видимые из данной точки грани и добавить новые — из точки до каждого ребра, образующего horizon (см. картинки). После этого нужно смержить соседние грани, которые получились копланарными.
+
Так мы получили тетраэдр <tex>p_1 p_2 p_3 p_4</tex>, который является выпуклой оболочкой этих четырёх точек. Сделаем random shuffle оставшихся точек <tex>p_5, ..., p_n</tex> и будем добавлять их по одной в выпуклую оболочку. Если <tex>p_i</tex> внутри или на границах выпуклой оболочки, то выпуклая оболочка не меняется на этом шаге. Иначе из имеющейся выпуклой оболочки надо удалить все видимые из данной точки грани и добавить новые — из точки до каждого ребра, образующего horizon (см. картинки; на них белые грани видны из точки <tex>p_r</tex>). После этого нужно смержить соседние грани, которые получились копланарными.
  
 
[[Файл:3dconvexhullhorizon.png]] [[Файл:3dconvexhulladd.png]]
 
[[Файл:3dconvexhullhorizon.png]] [[Файл:3dconvexhulladd.png]]
 +
 +
==Детали реализации==
 +
Будем хранить выпуклую оболочку в виде DCEL.
 +
 +
Для выяснения, какие грани видны из точки, будем хранить двудольный граф <tex>G</tex>, называемый conflict graph, в одной доле которого будут точки, которые ещё не добавлены в выпуклую оболочку, а в другой — имеющиеся на данный момент грани выпуклой оболочки. Ребро между точкой <tex>p</tex> и гранью <tex>f</tex> в этом графе означает, что из <tex>p</tex> видна <tex>f</tex>, то есть они находятся в конфликте (in conflict): они не могут сосуществовать в выпуклой оболочке.
 +
 +
Инициализация графа для тетраэдра тривиальна: для каждой точки определяем, какие грани видны из неё. Далее на каждом шаге после добавления точки <tex>p_r</tex> удалим из графа соответствующие удаляемым из выпуклой оболочки граням вершины и инцидентные им рёбра: просто удаляем все достижимые из <tex>p_r</tex> вершины. Также удалим вершину, соответствующую <tex>p_r</tex>. Далее добавляем новые грани выпуклой оболочки. Необходимо найти их конфликты. Сами грани представляют из себя треугольники, если, конечно, они не были смержены с уже имеющимися гранями. Во втором случае новая грань находится в конфликте с теми же точками, что и старая грань, т.к. смерженные грани копланарны.
 +
 +
Перейдём к первому случаю. Пусть мы добавили точку <tex>p_r</tex> и рассматриваем грань <tex>f</tex>. <tex>e</tex> — ребро, принадлежащее horizon, <tex>f_1, f_2</tex> — грани, пересечение которых образовывало <tex>e</tex> в старой оболочке.

Версия 11:55, 17 января 2014

Конспект написан не до конца, но основные вещи уже есть.

Рассмотрим трёхмерный случай. [math]n[/math]-мерный сводится к трёхмерному.

Суть алгоритма

Выберем любые две точки [math]p_1[/math] и [math]p_2[/math]. Далее из оставшихся выберем точку [math]p_3[/math], которая не лежит на прямой, образованной точками [math]p_1[/math] и [math]p_2[/math]. После этого выберем точку [math]p_4[/math], которая не лежит на плоскости, образованной точками [math]p_1, p_2[/math] и [math]p_3[/math]. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.

Так мы получили тетраэдр [math]p_1 p_2 p_3 p_4[/math], который является выпуклой оболочкой этих четырёх точек. Сделаем random shuffle оставшихся точек [math]p_5, ..., p_n[/math] и будем добавлять их по одной в выпуклую оболочку. Если [math]p_i[/math] внутри или на границах выпуклой оболочки, то выпуклая оболочка не меняется на этом шаге. Иначе из имеющейся выпуклой оболочки надо удалить все видимые из данной точки грани и добавить новые — из точки до каждого ребра, образующего horizon (см. картинки; на них белые грани видны из точки [math]p_r[/math]). После этого нужно смержить соседние грани, которые получились копланарными.

3dconvexhullhorizon.png 3dconvexhulladd.png

Детали реализации

Будем хранить выпуклую оболочку в виде DCEL.

Для выяснения, какие грани видны из точки, будем хранить двудольный граф [math]G[/math], называемый conflict graph, в одной доле которого будут точки, которые ещё не добавлены в выпуклую оболочку, а в другой — имеющиеся на данный момент грани выпуклой оболочки. Ребро между точкой [math]p[/math] и гранью [math]f[/math] в этом графе означает, что из [math]p[/math] видна [math]f[/math], то есть они находятся в конфликте (in conflict): они не могут сосуществовать в выпуклой оболочке.

Инициализация графа для тетраэдра тривиальна: для каждой точки определяем, какие грани видны из неё. Далее на каждом шаге после добавления точки [math]p_r[/math] удалим из графа соответствующие удаляемым из выпуклой оболочки граням вершины и инцидентные им рёбра: просто удаляем все достижимые из [math]p_r[/math] вершины. Также удалим вершину, соответствующую [math]p_r[/math]. Далее добавляем новые грани выпуклой оболочки. Необходимо найти их конфликты. Сами грани представляют из себя треугольники, если, конечно, они не были смержены с уже имеющимися гранями. Во втором случае новая грань находится в конфликте с теми же точками, что и старая грань, т.к. смерженные грани копланарны.

Перейдём к первому случаю. Пусть мы добавили точку [math]p_r[/math] и рассматриваем грань [math]f[/math]. [math]e[/math] — ребро, принадлежащее horizon, [math]f_1, f_2[/math] — грани, пересечение которых образовывало [math]e[/math] в старой оболочке.