Разделение пространства

Разделение всего пространства на ≥2 непересекающихся подмножества

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

Обзор

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

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

Использует

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

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

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

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

В проектировании интегральных схем

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

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

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

В географии и ГИС

Существует множество исследований и приложений, в которых географическая пространственная реальность подразделяется по гидрологическим , административным , математическим или многим другим критериям.

В контексте картографии и ГИС - географической информационной системы , ячейки раздела обычно идентифицируются стандартными кодами . Например, для кода HUC, идентифицирующего гидрографические бассейны и суббассейны, кодов ISO 3166-2, идентифицирующих страны и их подразделения, или произвольных DGG - дискретных глобальных сеток, идентифицирующих квадранты или местоположения.

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

К распространенным системам разделения пространства относятся:

• Деревья BSP
• Квадродеревья
• Октодеревья
• деревья k -d
• Контейнеры
• R-деревья

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

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

${\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}$

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

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

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

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

• Двоичное разбиение пространства
• Дискретная глобальная сетка
• Полигональное разбиение
• Тесселяция

Ссылки

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