Изменения

В двумерном случае BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую l1<tex>l_1</tex>, затем разбиваем разбивая полуплоскость выше l1 <tex>l_1</tex> прямой l2<tex>l_2</tex>, а ниже {{---}} прямой l3 <tex>l_3</tex> и так далее.{{TODO | t = Картинка про прямые и про дерево}}Прямые разбивают на фрагменты части не только плоскость, но и объекты, расположенные на ней. Разбиение продолжается до тех пор, пока внутри каждого фрагмента каждой грани плоскости окажется не более одного фрагмента объекта.

Если сцене присутствуют 1D{{Определение| definition = '''BSP-объекты дерево''' (отрезкиангл. ''binary space partition tree''){{---}} дерево, то они могут лежать на прямой разбиения, в таком случае соответсвующий узел хранит их в листьяхотвечающее заданному двоичному разбиению пространства.}}Опишем подробней свойства BSP-дерева.

Рассмотрим гиперплоскость <tex>h: a_1*\cdot x_1 + a_2*\cdot x_2 + ... \ldots + a_d*\cdot x_d + a_{d + 1} = 0</tex>.

Пусть <tex>h^+</tex> {{---}} положительная полуплоскостьположительное полупространство, а <tex>h^-</tex> {{---}} отрицательнаяотрицательное:

<tex>h^+ = \{(x_1, \ x_2 ... ,\ \dots,\ x_d) : \mid a_1*\cdot x_1 + a_2*\cdot x_2 + ... \ldots + a_d*\cdot x_d + a_{d + 1} > 0\}</tex>

<tex>h^- = \{(x_1, \ x_2 ... ,\ \dots,\ x_d) : \mid a_1*\cdot x_1 + a_2*\cdot x_2 + ... \ldots + a_d*\cdot x_d + a_{d + 1} < 0\}</tex>

Пусть <tex>S</tex> {{---}} множество объектов, для которого мы строим забиение в <tex>d</tex>-мерном пространстве.

*Если <tex>|S| <= \leqslant 1</tex>, то <tex>T</tex> {{---}} лист. Фрагмент объекта в <tex>S</tex>, если он существует, хранится в этом листе.

**левый ребенок <tex>v</tex> является корнем BSP дерева <tex>T^-</tex> на множестве объектов <tex>S^- = \{h_v^- \cap s : \mid s \in S\}</tex>;**правый ребенок <tex>v</tex> является корнем BSP дерева <tex>T^+</tex> на множестве объектов <tex>S^+ = \{h_v^+ \cap s : \mid s \in S\}</tex>.

{{Определение| definition = '''Двоично разбивающее пространство дерево''' (англ. ''binary space partition tree'') или '''BSP-дерево''' {{---}} структура данных, хранящая множество объектов на плоскости, рекурсивно разбитой прямыми.}}Размер BSP-дерева равен суммарному размеру множеств во всех узлах. То естьДругими словами, размер BSP-дерева {{---}} это число фрагментов, на которые были разбиты объекты. Так как BSP-дерево не содержит бесполезные прямые (прямые, которые разбивают пустую грань), то количество узлов пропорционально размеру дерева.{{TODO | t = Рисунок про соответсвие нодов и регионов}}

В общем-то размер Листья BSP-дерева ни о чем не говоритсоответствуют граням, так как то есть мы не знаем ничего об объеме памяти, требуемой для его храненияможем каждой вершине <tex>v</tex> сопоставить полигональную область на плоскости, так которая определяется как оно ничего не говорит об объеме памятипересечение полуплоскостей <tex>h_{\mu}^{\Diamond}</tex>, требуемом для храния фрагмента объекта.Но размер BSP-дерева где <tex>\mu</tex> {{---}} неплохая мера для сравнения качества разных BSP-деревьев для данного множества объектов.предок <tex>v</tex>, и

И еще рисунок про соответсвие нодов и регионов<tex> \Diamond = \left\{\begin{array}{llcl}- & \mathrm{if}\ v\ - \ \mathrm{left}\ \mathrm{child} \\+ & \mathrm{if}\ v\ - \ \mathrm{right}\ \mathrm{child} \\\end{array}\right.</tex>

| definition = BSP-деревоВ двухмерном случае для множества отрезков разбиение, в котором используются разбивающие прямые, построенное с применением авто-разбиенияпроходящие через один из данных отрезков, называются называется '''авто-разбивающим'''(англ. ''auto-partition'').

АвтоОднако размер авто-разбивающие деревья деревья имеют минимальный разбивающего дерева может быть не минимальным. Возможен случай, когда размерBSP-дерева может составлять <tex>\mathcal{O}(n^2) </tex>, где <tex> n = |S| </tex>.{{TODO | t = Картинка, когда может быть n^2}}