1632
правки
Изменения
м
rollbackEdits.php mass rollback
Чтобы использовать этот алгоритм в реальной жизни, например, в симуляторе полета, мы должны предпосчитать сцену так, чтобы можно было быстро найти корректный порядок отображения объектов для любой точки обзора.
Данную задачу можно элегантно решить при помощи техники '''двоичного разбиения пространства''' (англ. ''binary space partionpartitioning, BSP'').
== Структура BSP-дерева ==
При построении BSP-дерева могут использоваться любые разбивающие гиперплоскости. В целях упрощения вычислений может быть удобно ограничить множество доступных разбивающих гиперплоскостей. Обычно используют авто-разбиения.
{{Определение
| definition = В двухмерном двумерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, проходящие через один из данных отрезков, называется '''авто-разбивающим''' (англ. ''auto-partition'').
}}
'''BSPTree''' 2D_BSP_tree(<tex>S</tex>):
'''if''' <tex>|S| \leqslant 1</tex>
<tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font>
'''return''' <tex>T</tex>
'''else''' <font color="green">/* используем <tex>l(s_1)</tex> как разбивающую прямую */</tex></font>
| statement = Ожидаемое число фрагментов, сгенерированных алгоритмом '''2D_random_BSP_tree''' есть <tex>\mathcal{O}(n \log n)</tex>.
|proof =
Пусть <tex>s_i</tex> {{---}} фиксированный отрезок из <tex>S</tex>. Проанализируем [[Математическое ожидание случайной величины | ожидаемое ]] количество отрезков, которые мы разрежем, когда <tex>l(s_i)</tex> будет добавлена алгоритмом как следующая разбивающая прямая.
Рассмотрим рисунок и постараемся понять, разрезается ли отрезок <tex>s_j</tex> при добавлении прямой <tex>l(s_i)</tex>, в зависимости от отрезков, которые разрезаны <tex>l(s_i)</tex>, но находятся между <tex>s_i</tex> и <tex>s_j</tex>.
<tex>
\mathrm{dist}(s_i,\ s_j) = \left\{\begin{array}{llcl}
|\{s\ \mathrm{between}\ s_i\ \mathrm{and}\ s_j \mid l(s_i) \cap s \ne \varnothing \}| & \mathrm{if}\ l(s_i) \cap s_j \ne \varnothing \\
\infty & \mathrm{otherwise} \\
Для всех конечных расстояний до отрезка <tex>s_i</tex> может быть только два отрезка с одинаковым расстоянием {{---}} те, что лежат по разные стороны от <tex>s_i</tex>.
Пусть <tex>k = \mathrm{dist}(s_i,\ s_j)</tex> и <tex>s_{j_1},\ s_{j_2},\ \ldots ,\ s_{j_k}</tex> {{---}} отрезки между <tex>s_i</tex> и <tex>s_j</tex>.
Найдём вероятность того, что при добавлении <tex>l(s_i)</tex> разрежет <tex>s_j</tex>. Чтобы это произошло, <tex>s_i</tex> должен быть рассмотрен перед <tex>s_j</tex> и перед любым из отрезков между <tex>s_i</tex> и <tex>s_j</tex>, иначе они бы защитили <tex>s_j</tex> от <tex>s_i</tex>. Другими словами, среди множества индексов <tex>\{i, \ j, \ j_1, ... \ \ldots , \ j_k\}</tex> индекс <tex>i</tex> должен быть наименьшим.
Так как отрезки расположены в случайном порядке, получаем:
Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении <tex>s_i</tex>:
<tex>E(</tex>число разрезов, происходящих при добавлении <tex>s_i) \leqslant \sum\limits_{i j \ne ji} \genfrac{}{}{}{0}{1}{k \mathrm{dist}(s_i, s_j) + 2} \leqslant 2 \cdot \sum\limits_{k=0}^{n - 2} \genfrac{}{}{}{0}{1}{k + 2} \leqslant 2 \ln n</tex>.
По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более <tex>2n\log n</tex>. Так как изначально даны <tex>n</tex> отрезков, ожидаемое число фрагментов ограничено <tex>n + 2n\log n</tex>.
{{Теорема
| statement = В двумерном пространстве BSP-дерево размера <tex>\mathcal{O}(n\log n)</tex> может быть построено за ожидаемое время <tex>\mathcal{O}(n^2\log n)</tex>.
}}
'''BSPTree''' 3D_BSP_tree(<tex>S</tex>):
'''if''' <tex>|S| \leqslant 1</tex>
<tex>T \leftarrow</tex> '''BSPTree'''(<tex>S</tex>) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font>
'''return''' <tex>T</tex>
'''else''' <font color="green">/* используем <tex>h(t_1)</tex> как разбивающую плоскость */</font>
'''return''' <tex>T</tex>
Размер полученного BSP-дерева снова зависит от порядка треугольников. Как и в двухмерном двумерном случае, мы можем попытаться получить хороший ожидаемый размер дерева, переставив треугольники в случайном порядке. На практике это дает хорошие результаты.
== См. также ==
