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

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

Обзор

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

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

Использование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Comp(n,r)=Comp(n,r-1)+Comp(n-1,r-1)

Comp(0,r)=1

- когда нет размеров, есть одна точка.

Comp(n,0)=1

- когда нет гиперплоскостей, все пространство представляет собой единую составляющую.

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

Comp(n,r)=\sum _{k=0}^{n}{r \choose k}

если

r\geq n

Comp(n,r)=2^{r}

если

r\leq n

(рассмотрим, например,

r

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

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

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

См. также

Ссылки

^ Томас Никодим (2010). «Алгоритм трассировки лучей для интерактивных приложений» (PDF) . Чешский технический университет, ФЭУ .
^ Инго Уолд, Уильям Р. Марк; и др. (2007). «Современное состояние анимационных сцен с трассировкой лучей». Еврографика . CiteSeerX 10.1.1.108.8495 .
^ Трассировка лучей - вспомогательные структуры данных
^ Вапник В.Н.; Червоненкис, А.Я. (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 .
^ См. также подробные обсуждения и пояснения для случая n = 2. и общий случай . См. также Виндер, Р.О. (1966). «Разбиение N-пространства гиперплоскостями». SIAM Journal по прикладной математике . 14 (4): 811–818. дои : 10.1137/0114068 . .

[1] Томас Никодим (2010). «Алгоритм трассировки лучей для интерактивных приложений» (PDF) . Чешский технический университет, ФЭУ .

[2] Инго Уолд, Уильям Р. Марк; и др. (2007). «Современное состояние анимационных сцен с трассировкой лучей». Еврографика . CiteSeerX 10.1.1.108.8495 .

[3] Трассировка лучей - вспомогательные структуры данных

[vc-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 Journal по прикладной математике . 14 (4): 811–818. дои : 10.1137/0114068 . .

[1]

[2]

[3]

[4]

[5]