Сетка (пространственный индекс)

В контексте пространственного индекса сетка сетка или обычный представляет собой ^{[ нужна ссылка ]} тесселяция многообразия . или двумерной поверхности , которая делит его на ряд смежных ячеек, которым затем можно присвоить уникальные идентификаторы и использовать их для целей пространственной индексации Было предложено или используется в настоящее время большое разнообразие таких сеток, включая сетки на основе « квадратных » или «прямоугольных» ячеек, треугольные сетки или сетки, шестиугольные сетки и сетки на основе ромбовидных ячеек. « Глобальная сетка » — это своего рода сетка, покрывающая всю поверхность земного шара .

Виды сеток

Квадратные или прямоугольные сетки часто используются для таких целей, как перевод пространственной информации, выраженной в декартовых координатах ( широта и долгота ), в сеточную систему и из нее. Такие сетки могут быть совмещены или не совмещены с линиями сетки широты и долготы; например, квадраты Марсдена , квадраты Всемирной метеорологической организации , c-квадраты и другие выровнены, в то время как Универсальная поперечная система координат Меркатора и различные системы на основе локальной сетки, такие как британская национальная система координат сетки, не выровнены. В общем, эти сетки делятся на два класса: « равный угол » и « равная площадь ». Сетки с « равными углами » имеют размеры ячеек, постоянные по широте и долготе, но неравные по площади (особенно при изменении широты). Сетки « равной площади » ( статистические сетки ), размеры ячеек которых постоянны по расстоянию на земле (например, 100 км, 10 км), но не в градусах долготы, в частности.

Обычно используемая треугольная сетка — это «Четвертичная треугольная сетка» (QTM), разработанная Джеффри Даттоном в начале 1980-х годов. В конечном итоге результатом стала диссертация под названием «Иерархическая система координат для геообработки и картографии», которая была опубликована в 1999 году. ^[1]Эта сетка также была использована в качестве основы вращающегося глобуса, который является частью продукта Microsoft Encarta .

Также можно использовать шестиугольные сетки. В общем, треугольные и шестиугольные сетки строятся так, чтобы лучше достичь цели равной площади (или почти равной) плюс более плавное покрытие полюсов, что, как правило, является проблемной областью для квадратных или прямоугольных сеток, поскольку в этих случаях ширина ячейки уменьшается до нуля на полюсе, и ячейки, прилегающие к полюсу, становятся трех-, а не четырехсторонними. Критерии оптимальной дискретной глобальной сетки были предложены Гудчайлдом и Кимерлингом. ^[2] в которых ячейки равной площади имеют первостепенное значение.

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

Пространственная индексация на основе сетки

На практике построение пространственных индексов на основе сетки влечет за собой присвоение соответствующих объектов их положению или позициям в сетке, а затем создание индекса идентификаторов объектов и идентификаторов ячеек сетки для быстрого доступа. Это пример «космического» или независимого от данных метода, в отличие от «управляемого данными» или метода, зависящего от данных, как обсуждается далее в Rigaux et al. (2002)). ^[3] Преимущество пространственного индекса на основе сетки заключается в том, что сначала можно создать структуру индекса, а данные добавлять на постоянной основе, не требуя каких-либо изменений в структуре индекса; действительно, если общая сетка используется для разрозненных действий по сбору и индексированию данных, такие индексы можно легко объединить из различных источников. С другой стороны, структуры, управляемые данными, такие как R-деревья, могут быть более эффективными для хранения данных и более быстрыми во время выполнения поиска, хотя они обычно привязаны к внутренней структуре данной системы хранения данных.

Использование таких пространственных индексов не ограничивается цифровыми данными; раздел «индекс» любого глобального атласа или атласа улиц обычно содержит список названных объектов (городов, улиц и т. д.) с соответствующими идентификаторами квадратов сетки и может считаться вполне приемлемым примером пространственного индекса (в этом случае обычно организованы по имени функции, хотя концептуально возможно и обратное).

Другое использование

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

В информатике часто необходимо выяснить все ячейки сетки, через которые проходит луч (для трассировки лучей или обнаружения столкновений); это называется «обходом сетки».

См. также

Ссылки

^ Джеффри Даттон. «Пространственные эффекты: исследовательские работы и данные». Архивировано 19 февраля 2007 г. в Wayback Machine .
^ Критерии и меры для сравнения глобальных систем геокодирования, Кейт К. Кларк, Калифорнийский университет. Архивировано 23 июня 2010 г. в Wayback Machine.
^ Риго П., Шолль М. и Войсар А. 2002. Пространственные базы данных - с применением к ГИС. Морган Кауфманн, Сан-Франциско, 410 стр.

Индексирование неба - Клайв Пейдж - Индексы сетки для астрономии

Внешние ссылки

[1] Джеффри Даттон. «Пространственные эффекты: исследовательские работы и данные». Архивировано 19 февраля 2007 г. в Wayback Machine .

[2] Критерии и меры для сравнения глобальных систем геокодирования, Кейт К. Кларк, Калифорнийский университет. Архивировано 23 июня 2010 г. в Wayback Machine.

[3] Риго П., Шолль М. и Войсар А. 2002. Пространственные базы данных - с применением к ГИС. Морган Кауфманн, Сан-Франциско, 410 стр.

[1]

[2]

[3]