В геометрии , пространство разбиения является процесс деления пространства (обычно евклидово пространство ) в двух или более непересекающихся подмножеств (смотри также разбиение множества ). Другими словами, разделение пространства делит пространство на неперекрывающиеся области. Тогда можно определить любую точку в пространстве, которая лежит ровно в одной из областей.
Обзор
Системы разделения пространства часто являются иерархическими , что означает, что пространство (или область пространства) делится на несколько областей, а затем одна и та же система разделения пространства рекурсивно применяется к каждой из созданных таким образом областей. Регионы могут быть организованы в дерево , называемое деревом разделения пространства .
Большинство систем разделения пространства используют плоскости (или, в более высоких измерениях, гиперплоскости ) для разделения пространства: точки на одной стороне плоскости образуют одну область, а точки на другой стороне - другую. Точки точно на плоскости обычно произвольно назначаются той или другой стороне. Рекурсивное разделение пространства с помощью плоскостей таким образом дает BSP-дерево , одну из наиболее распространенных форм разделения пространства.
Использует
В компьютерной графике
Разделение пространства особенно важно в компьютерной графике , особенно активно используется при трассировке лучей , где оно часто используется для организации объектов в виртуальной сцене. Типичная сцена может содержать миллионы полигонов. Выполнение теста на пересечение луча / полигона с каждым из них было бы очень затратной задачей с точки зрения вычислений.
Хранение объектов в структуре данных с разделением по пространству (например, дерево k -d или дерево BSP ) позволяет легко и быстро выполнять определенные виды геометрических запросов - например, при определении того, пересекает ли луч объект, разделение пространства может уменьшить количество проверки пересечения до нескольких на первичный луч, что дает логарифмическую временную сложность по отношению к количеству многоугольников. [1] [2] [3]
Пространство разбиение также часто используется в алгоритмах ScanLine для устранения многоугольников выхода из камеры просмотра усеченного , ограничивая количество полигонов , обрабатываемых по трубопроводу. Существует также использование в обнаружении столкновений : определение того, находятся ли два объекта близко друг к другу, может быть намного быстрее с использованием разделения пространства.
В конструкции интегральной схемы
При проектировании интегральных схем важным этапом является проверка правил проектирования . Этот шаг гарантирует, что готовый дизайн можно будет изготовить. Проверка включает правила, определяющие ширину и интервалы, а также другие геометрические шаблоны. Современный дизайн может состоять из миллиардов многоугольников, представляющих провода и транзисторы. Эффективная проверка во многом зависит от геометрического запроса. Например, правило может указывать, что любой многоугольник должен находиться на расстоянии не менее n нанометров от любого другого многоугольника. Он преобразуется в геометрический запрос путем увеличения многоугольника на n / 2 со всех сторон и запроса для поиска всех пересекающихся многоугольников.
В теории вероятностей и статистического обучения
Количество компонентов в пространственном разбиении играет центральную роль в некоторых результатах теории вероятностей. Смотрите функцию роста для более подробной информации.
В географии и ГИС
Существует множество исследований и приложений, в которых географическая пространственная реальность разделяется по гидрологическим критериям , административным критериям , математическим критериям или многим другим.
В контексте Картографии и ГИС - Географической информационной системы , есть возможность идентифицировать ячейки раздела по стандартным кодам . Например, для кода HUC, идентифицирующего гидрографические бассейны и суб-бассейны, коды ISO 3166-2, идентифицирующие страны и их подразделения, или произвольные DGGs - дискретные глобальные сетки, идентифицирующие квадранты или местоположения.
Структуры данных
Общие системы разделения пространства включают:
Количество компонентов
Предположим, что n-мерное евклидово пространство разделено на гиперплоскости , которые-размерный. Какое количество компонентов в перегородке? Наибольшее количество компонентов достигается, когда гиперплоскости находятся в общем положении , т. Е. Никакие две не параллельны и никакие три не имеют одинакового пересечения. Обозначим это максимальное количество компонентов как. Тогда имеет место следующее рекуррентное соотношение: [4] [5]
- - когда нет размеров, есть одна точка.
- - когда нет гиперплоскостей, все пространство представляет собой единый компонент.
И его решение:
- если
- если
- (рассмотрим, например, перпендикулярные гиперплоскости; каждая дополнительная гиперплоскость делит каждый существующий компонент на 2).
который ограничен сверху как:
Смотрите также
- Разделение двоичного пространства
- Дискретная глобальная сетка
- Разбиение многоугольника
- Мозаика
Рекомендации
- ^ Томас Никодим (2010). «Алгоритм трассировки лучей для интерактивных приложений» (PDF) . Чешский технический университет, FEE .
- ^ Инго Вальд, Уильям Р. Марк; и другие. (2007). «Современное состояние в анимационных сценах с трассировкой лучей». Еврография . CiteSeerX 10.1.1.108.8495 .
- ^ Трассировка лучей - Вспомогательные структуры данных
- ^ Вапник, ВН; Червоненкис, А.Я. (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.
- ^ См. Также подробные обсуждения и пояснения для случая n = 2 и общего случая . Смотрите также Уиндер, РО (1966). «Разбиение N-пространства гиперплоскостями». Журнал СИАМ по прикладной математике . 14 (4): 811–818. DOI : 10.1137 / 0114068 ..