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

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

Обзор

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

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

Использует

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

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

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

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

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

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

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

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

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

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

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

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

- когда нет размеров, есть одна точка.
- когда нет гиперплоскостей, все пространство представляет собой единый компонент.

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

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

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

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

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

  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..