Разделение пространства - Space partitioning - Wikipedia

В геометрия, разделение пространства это процесс разделения Космос (обычно Евклидово пространство ) на два или более непересекающийся подмножества (смотрите также раздел набора ). Другими словами, разделение пространства делит пространство на неперекрывающиеся области. Тогда можно определить любую точку пространства, которая лежит точно в одной из областей.

Обзор

Системы разделения пространства часто иерархический, что означает, что пространство (или область пространства) делится на несколько областей, и тогда одна и та же система разделения пространства рекурсивно применяется к каждому из созданных таким образом регионов. Регионы можно объединить в дерево, называется дерево разделения пространства.

Большинство систем разделения пространства используют самолеты (или, в более высоких измерениях, гиперплоскости ) для разделения пространства: точки на одной стороне плоскости образуют одну область, а точки на другой стороне - другую. Точки точно на плоскости обычно произвольно назначаются той или другой стороне. Рекурсивное разделение пространства с помощью плоскостей таким образом дает BSP дерево, одна из самых распространенных форм разделения пространства.

Использует

В компьютерной графике

Разделение пространства особенно важно в компьютерная графика, особенно активно используется в трассировка лучей, где он часто используется для организации объектов в виртуальной сцене. Типичная сцена может содержать миллионы полигонов. Выполнение луча / полигона проверка пересечения с каждым из них будет очень затратной в вычислительном отношении задачей.

Хранение объектов в пространстве-разбиении структура данных (k-d дерево или же BSP дерево например) позволяет легко и быстро выполнять определенные виды геометрических запросов - например, при определении того, пересекает ли луч объект, разделение пространства может уменьшить количество проверок пересечений до нескольких на первичный луч, что дает логарифмическую временная сложность по количеству многоугольников.^[1][2][3]

Разделение пространства также часто используется в алгоритмах сканирования строк для удаления полигонов за пределы камеры. просмотр усеченной пирамиды, ограничивающее количество полигонов, обрабатываемых конвейером. Есть также использование в обнаружение столкновения: определение того, находятся ли два объекта близко друг к другу, может быть намного быстрее, используя разделение пространства.

В конструкции интегральной схемы

В конструкция интегральной схемы, важным шагом является проверка правил проектирования. Этот шаг обеспечивает возможность изготовления готовой конструкции. Проверка включает правила, которые определяют ширину и интервалы, а также другие геометрические шаблоны. В современном дизайне могут быть миллиарды многоугольников, представляющих провода и транзисторы. Эффективная проверка во многом зависит от геометрического запроса. Например, правило может указывать, что любой многоугольник должен быть не менее п нанометров от любого другого многоугольника. Он преобразуется в геометрический запрос путем увеличения многоугольника на п / 2 со всех сторон и запросите, чтобы найти все пересекающиеся многоугольники.

В теории вероятностей и статистического обучения

Число компонентов в пространственном разбиении играет центральную роль в некоторых результатах теории вероятностей. Видеть Функция роста Больше подробностей.

Структуры данных

Общие системы разделения пространства включают:

• BSP деревья;
• Quadtrees;
• Octrees;
• k-d деревья;
• Бункеры;
• R-деревья;
• Иерархии ограничивающих объемов.

Количество компонентов

Предположим, что n-мерный Евклидово пространство разделен ${\displaystyle r}$ гиперплоскости которые ${\displaystyle (n-1)}$-размерный. Какое количество компонентов в разделе? Наибольшее количество компонентов достигается, когда гиперплоскости находятся в общая позиция т. е. нет двух параллельных и нет трех одинаковых пересечений. Обозначим это максимальное количество компонентов как ${\displaystyle Comp(n,r)}$. Тогда имеет место следующее рекуррентное соотношение:^[4][5]

${\displaystyle Comp(n,r)=Comp(n,r-1)+Comp(n-1,r-1)}$

${\displaystyle Comp(0,r)=1}$ - когда нет размеров, есть одна точка.

${\displaystyle Comp(n,0)=1}$ - когда нет гиперплоскостей, все пространство представляет собой единый компонент.

И его решение:

${\displaystyle Comp(n,r)=\sum _{k=0}^{n}{r \choose k}}$ если ${\displaystyle r\geq n}$

${\displaystyle Comp(n,r)=2^{r}}$ если ${\displaystyle r\leq n}$

(рассмотрим, например, ${\displaystyle r}$ перпендикулярные гиперплоскости; каждая дополнительная гиперплоскость делит каждый существующий компонент на 2).

который ограничен сверху как:

${\displaystyle Comp(n,r)\leq r^{n}+1}$

Смотрите также

• Разделение двоичного пространства
• Дискретная глобальная сетка
• Разделение многоугольника
• Мозаика

Рекомендации

1. Томас Никодим (2010). «Алгоритм трассировки лучей для интерактивных приложений» (PDF). Чешский технический университет, FEE.
2. Инго Вальд, Уильям Р. Марк; и другие. (2007). «Современное состояние в анимированных сценах с трассировкой лучей». Еврография. CiteSeerX  10.1.1.108.8495.
3. Трассировка лучей - вспомогательные структуры данных
4. Вапник, В. Н .; Червоненкис, А.Я. (1971). «О равномерной сходимости относительных частот событий к их вероятностям». Теория вероятностей и ее приложения. 16 (2): 266. Дои:10.1137/1116025.Это английский перевод русской газеты Б. Секлера: «О равномерной сходимости относительных частот событий к их вероятностям». Докл. Акад. Наук. 181 (4): 781. 1968.Перевод был воспроизведен как:Вапник, В. Н .; Червоненкис, А.Я. (2015). «О равномерной сходимости относительных частот событий к их вероятностям». Меры сложности. п. 11. Дои:10.1007/978-3-319-21852-6_3. ISBN  978-3-319-21851-9.
5. См. Также подробные обсуждения и пояснения по случай n = 2 и общий случай.Смотрите также Уиндер, Р. О. (1966). «Разбиение N-пространства гиперплоскостями». Журнал SIAM по прикладной математике. 14 (4): 811–818. Дои:10.1137/0114068..