== Построение BSP-дерева ==
При решении задач Прежде чем переходить к задаче отрисовки сцены в трехмерном пространстве бывает полезно сначала рассмотреть трёхмерном случае, рассмотрим для простоты аналогичную задачу на плоскости, что мы и сделаем.
Пусть <tex>S</tex> {{---}} множество из <tex>n</tex> непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.
Пусть <tex>l(s)</tex> {{---}} прямая, содержащая отрезок <tex>s</tex>.
На вход алгоритму подается <tex>S = \{s_1, \ s_2, ... \ \dots , \ s_n\}</tex> {{---}} множество отрезков.
<code> '''BSPTree ''' 2D_BSP_tree(<tex>S</tex>): if <tex>|S| <= \leqslant 1</tex> <tex>T \leftarrow</tex> new '''BSPTree'''(S) <font color="green">/* <tex>T</tex> будет листом, в котором хранится данное множество */</font> '''return ''' <tex>T</tex> '''else ''' <font color="green">/* используем <tex>l(s1s_1)</tex> как разбивающую прямую */</tex></font> <tex>S^+ \leftarrow \{s \cap l^+(s_1) : \mid s \in S\}</tex> <tex>T^+ \leftarrow</tex> 2D_BSP_tree(<tex>S^+</tex>) <tex>S^− - \leftarrow \{s \cap l^-(s_1) : \mid s \in S\}</tex> <tex>T^- \leftarrow</tex> 2D_BSP_tree(<tex>S^−-</tex>) <tex>S_v \leftarrow \{s \in S : \mid s \subset l(s_1)\}</tex> <tex>T \ leftarrow</tex> new '''BSPTree'''(S_v, T^-, T^+) <font color="green">// создаем BSP-дерево c корнем в вершине <tex>v</tex>, левым поддеревом <tex>T^−-</tex> и правым поддеревом <tex>T^+</tex> </font> <font color="green">// и множеством хранимых объектов <tex>S_v</tex></font> '''return ''' <tex>T</tex> </code>Данный алгоритм создает BSP-дерево для множества <tex>S</tex>, но как уже известно, оно не будет наименьшим в общем случае.
ПонятноНеобходимо придумать стратегию выбора прямой разбиения, а не просто брать <tex>l(s_1)</tex>. Возможным подходом является выбор отрезка <tex>s \in S</tex>, такого что алгоритм создает BSP-дерево для множества <tex>Sl(s)</tex>пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме того, но будет ли оно наименьшим?поиск такого отрезка {{---}} занятие затратное.
НаверноеКак и в других алгоритмах, стоит тщательней выбирать прямую разбиениякогда нужно сделать сложный выбор, а не просто брать <tex>l(s_1)</tex>сделаем рандомный выбор. Возможным подходом является выбор отрезка <tex>s \in S</tex>Это означает, такого что для разбиения мы будем использовать случайно выбранный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>l(s)S</tex> пересекает наименьшее число отрезков. Но такой жадный алгоритм работает не на всех конфигурациях отрезков. Кроме того, поиск такого отрезка {{---}} занятие затратноеслучайном порядке.
Как и в других алгоритмах, когда нужно сделать сложный выбор, просто выберем случайно. Это означает, что для разбиения мы будем использовать рандомный отрезок. Для этого перед тем, как начинать построение дерева, расположим отрезки в <tex>S</texcode> случайном порядке. '''void''' 2D_random_BSP_tree(<tex>S</tex>) : <tex>S \leftarrow </tex> random_permutation(<tex>S</tex>). <tex>T \leftarrow </tex> 2D_BSP_tree(<tex>S</tex>) '''return ''' <tex>T</tex></code>Перед тем, как анализировать рандомизированный алгоритм, отметим, что здесь возможна одна простая оптимизацияанализированием рандомизированного алгоритма рассмотрим одну простую оптимизацию.
Предположим, что мы выбрали несколько первых разбивающих прямых. Эти прямые порождают разбиение плоскости, грани которой соответствуют каким-то узлам BSP-дерева.
Рассмотрим одну из таких поверхностей граней <tex>f</tex>. В <tex>S</tex> могут быть отрезки, которые полностью пересекают <tex>f</tex>. Выбор одного из таких отрезков для разбиения <tex>f</tex> не вызовет фрагментации других отрезков внутри <tex>f</tex>, так как данный отрезок исключается из дальнейшего рассмотрения. Назовем такое свободным разбиением.
Нашей улучшенной стратегией будет использование свободных разбиений везде, где только можно, и использование случайных разбиений в противном случае. Для реализации данной оптимизации нужно уметь определять, вызывает ли отрезок свободное разбиение. Для этого сопоставим каждому отрезку две булевых переменных, которые покажут, лежат ли правый и левый концы отрезка на какой-то из уже добавленных разбивающих прямых. Обе переменных истинны, когда отрезок вызывает свободное разбиение.
Теперь оценим производительность алгоритма '''2D_random_BSP_tree'''. Для упрощения рассуждений будем анализировать версию без свободных разбиений (асимптотической разницы они не даютмежду ними нет). Начнем с анализа размера BSP-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие {{---}} большие.
В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) {{---}} то всего три фрагмента.
{{Лемма
| statement = Ожидаемое число фрагментов, сгенерированных алгоритмом 2D_random_BSP_tree есть <tex>\mathcal{O}(nlognn \log n)</tex>.
|proof =
Пусть <tex>s_i</tex> {{---}} фиксированный отрезок из <tex>S</tex>. Проанализируем ожидаемое количество отрезков, которые мы разрежем, когда <tex>l(s_i)</tex> будет добавлена алгоритмом как следующая разбивающая прямая.
