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

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

Обзор

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

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

Использует

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что n-мерный Евклидово пространство разделен ${ displaystyle r}$ гиперплоскости которые ${ Displaystyle (п-1)}$-размерный. Какое количество компонентов в разделе? Наибольшее количество компонентов достигается, когда гиперплоскости находятся в общая позиция т. е. нет двух параллельных и нет трех одинаковых пересечений. Обозначим это максимальное количество компонентов как ${ Displaystyle Comp (п, г)}$. Тогда имеет место следующее рекуррентное соотношение:^[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 (п, г) = 2 ^ {г}}$ если ${ Displaystyle г Leq п}$

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

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

${ Displaystyle Comp (п, г) leq г ^ {п} +1}$

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

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

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