Изменения
→Определение
== Определение ==
BSP строится с помощью рекурсивного разбиения плоскости прямыми. В данном примере это происходит так: сначала проводим прямую l1, затем разбиваем полуплоскость выше l1 прямой l2, а ниже {{---}} прямой l3 и так далее.
**правый ребенок <tex>v</tex> является корнем BSP дерева <tex>T^+</tex> на множестве объектов <tex>S^+ = \{h_v^+ \cap s : s \in S\}</tex>.
{{Определение
| definition = '''Двоично разбивающее пространство дерево''' (англ. ''binary space partition tree'') или '''BSP-дерево''' {{---}} структура данных, хранящая множество объектов на плоскости, рекурсивно разбитой прямыми.
}}
Размер BSP-дерева равен суммарному размеру множеств во всех узлах. То есть, размер BSP-дерева {{---}} это число фрагментов, на которые были разбиты объекты. Так как BSP-дерево не содержит бесполезные прямые (прямые, которые разбивают пустую грань), то количество узлов пропорционально размеру дерева.
