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

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

Виды сеток

Квадратные или прямоугольные сетки часто используются для таких целей, как перевод пространственной информации, выраженной в декартовых координатах ( широта и долгота ), в сеточную систему и из нее. Такие сетки могут быть совмещены или не совмещены с линиями сетки широты и долготы; например, квадраты Марсдена , квадраты Всемирной метеорологической организации , 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]