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

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

Обзор

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

Большинство систем разделения пространства используют самолеты (или, в более высоких измерениях, гиперплоскости) для разделения пространства: точки на одной стороне плоскости образуют одну область, а точки на другой стороне - другую. Точки точно на плоскости обычно произвольно назначаются той или другой стороне. Рекурсивное разделение пространства с помощью плоскостей таким образом дает 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}$

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

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

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