Изменения
→Построение BSP-дерева
== Построение BSP-дерева ==
При решении задач в трехмерном пространстве бывает полезно сначала рассмотреть задачу на плоскости, что мы и сделаем.
Пусть S - множество из n непересекающихся отрезков на плоскости. Ограничимся авто-разбиением, рассматривая только прямые, содержащие один из отрезков.
Пусть l(s) - прямая, содержащая отрезок s.
На вход алгоритму подается S = {s1, s2, ... sn} - множество отрезков.
BSPTree 2D_BSP_tree(S)
if |S| <= 1
Create a tree T consisting of a single leaf node, where the set S is stored explicitly.
return T
else /* Use l(s1) as the splitting line */
S+ \leftarrow {s \пересечь l(s1)+ : s \in S};
T+ \leftarrow 2D_BSP_tree(S+);
S− \leftarrow {s \пересечь l(s1)− : s ∈ S};
T− \leftarrow 2D_BSP_tree(S−);
Create a BSP tree T with root node ν, left subtree T−, right subtree T+, and with S(ν) = {s \in S : s \subset l(s1)}.
return T
2D_random_BSP_tree(S) Generate a random permutation S' = s1, . . . , sn of the set \leftarrow random_permutation(S). T \leftarrow 2D_BSP_tree(S�S) return T
Перед тем, как анализировать рандомизированный алгоритм, отметим, что здесь возможна одна простая оптимизация.
Предположим, что мы выбрали несколько первых разбивающих прямых. Эти прямые порождают разбиение плоскости, фейсы грани которой соответствуют каким-то узлам BSP-дерева.
Рассмотрим одну из таких поверхностей f. В S могут быть отрезки, которые полностью пересекают f. Выбор одного из таких отрезков для разбиения f не вызовет фрагментации других отрезков внутри f, так как данный отрезок исключается из дальнейшего рассмотрения.
Назовем такое свободным разбиением.
Нашей улучшенной стратегией будет использование свободных разбиений везде, где только можно, и использование случайных разбиений в противном случае. Для реализации данной оптимизации нужно уметь определять, вызывает ли отрезок свободное разбиение. Для этого сопоставим каждому отрезку две булевых переменных, которые покажут, лежат ли правый и левый концы отрезка на какой-то из уже добавленных разбивающих прямых. Обе переменных истинны, когда отрезок вызывает свободное разбиение. Теперь оценим производительность алгоритма 2D_random_BSP_tree. Для упрощения рассуждений будем анализировать версию без свободных разбиений (асимптотической разницы они не дают).Начнем с анализа размера BSP-дерева, равного числу полученных фрагментов, которое зависит от сгенерированной перестановки отрезков. Некоторые перестановки могут породить маленькие деревья, а другие - большие.
В качестве примера рассмотрим три отрезка, изображенные на рисунке. Если они рассматриваются в порядке (a), то мы получаем пять фрагментов, если же в порядке (b) - то всего три фрагмента.
Так как размер BSP-дерева зависит от сгенерированной перестановки, будем анализировать ожидаемый размер BSP-дерева - средний размер для всех n! перестановок.
{{Лемма. | statement = Ожидаемое число фрагментов, сгенерированных алгоритмом 2D_random_BSP_tree есть O(nlogn).Доказательство.|proof =
Пусть s_i - фиксированный отрезок из S. Проанализируем ожидаемое количество отрезков, которые мы разрежем, когда l(s_i) будет добавлена алгоритмом как следующая разбивающая прямая.
Рассмотрим рисунок и постараемся понять разрезается ли отрезок s_j при добавлении прямой l(s_i), в зависимости от отрезков, которые разрезаны l(s_i), но находятся между s_i и s_j.
В частности, когда прямая, пересекающая такой отрезок, добавляется раньше l(s_i), она закрывает s_j от s_i. На рисунке (b) так происходит с отрезком s_3, который защищен отрезком s_1 от s_2.
Эти размышления приводят нас к определению расстояния от какого-то отрезка до фиксированного отрезка s_i.
dist_s_i(s_j) = {количество пересекаемых отрезков, если l(s_i) пересекает s_j; +inf, иначе}
Для всех конечных расстояний до отрезка s_i может быть только два отрезка с одинаковым расстоянием - те, что лежат по разные стороны от s_i.
Пусть k = dist_s_i(s_j) и s_j_1, s_j_2, ... s_j_k - отрезки между s_i и s_j. Какова вероятность того, что при добавлении l(s_i) разрежет s_j?Чтобы это произошло, s_i должен быть рассмотрен перед s_j и перед любым из отрезков между s_i и s_j, иначе они бы защили s_j от s_i. Другими словами, среди множества индексов {i, j, j_1, ... , j_k} i должен быть наименьшим.
Так как отрезки расположены в случайном порядке, получаем:
P(l(s_i) разрезает s_j) <= 1 / (k + 2)
Теперь мы можем ограничить ожидаемое число разрезов, происходящих при добавлении s_i:
E(число разрезов, происходящих при добавлении s_i) <= sum(i != j, 1 / (k + 2)) <= 2 * sum(k=0..n - 2, 1/ (k + 2)) <= 2 * ln n.
По линейности ожиданий мы можем заключить, что ожидаемое число разрезов, вызванных добавлением всех отрезков составляет не более 2nlogn.Так как изначально даны n отрезков, ожидаемое число фрагментов ограничено n + 2nlogn.}}
Мы показали, что ожидаемый размер BSP-дерева, построенного с помощью алгоритма 2D_random_BSP_tree, составляет n + 2nlogn. Следовательно, мы доказали, что BSP-дерево размера n + 2nlogn существует для любого множества n отрезков. Кроме того, хотя бы половина перестановок приводит к BSP-дереву размера n + 4nlogn.
Мы можем использовать этот факт, чтобы найти дерево такого размера: после запуска алгоритма сравним размер дерева с данной оценкой, если он превышает оценку, просто построим BSP-дерево еще раз, но для новой перестановки. Ожидаемое число запусков равняется двум.
Теперь проанализируем время работы алгоритма. Понятно, что оно зависит от используемой перестановки, так что опять рассмотрим ожидаемое время работы. Нахождение рандомной перестановки занимает O(n). Если проигнорировать время рекурсивных вызовов, то время работы алгоритма линейно от количества фрагментов в S. Это число не превышает n, так как становится меньше с каждым рекурсивным вызовом.Число рекурсивных вызовов ограничено количеством сгенерированных фрагментов, которое составляет O(nlogn). Таким образом, время построения дерева составляет O(n^2logn). {{Теорема| statement = BSP-дерево размера O(nlogn) может быть построено за ожидаемое время O(n^2logn).}} Описанный выше алгоритм легко распространяется с двухмерного пространства на трехмерное. Пусть S - множество непересекающихся треугольков в R^3.
Для треугольника t обозначим плоскость, содержащую его, как h(t).
На вход алгоритму подается множество треугольников S = {t1, t2, . . . ,tn}, заданных в трехмерном пространстве.
BSPTree 3DBSP(S) if |S| <= 1 then Create a tree T consisting of a single leaf node, where the set S is stored explicitly. return T else /* Use h(t1) as the splitting plane. */ S+ \leftarrow {t \пересечь h(t1)+ : t ∈ S} T+ \leftarrow 3DBSP(S+) S− \leftarrow{t \пересечь h(t1)− : t ∈ S} T− \leftarrow 3DBSP(S−) Create a BSP tree T with root node ν, left subtree T−, right subtree T+, and with S(ν) = {t ∈ S : t ⊂ h(t1)}. return T
Размер полученного BSP-дерева снова зависит от порядка треугольников. Как и в двухмерном случае, мы можем попытаться получить хороший ожидаемый размер дерева, переставив треугольники в случайном порядке. На практике это дает хорошие результаты.
