В контексте пространственного индекса сетка или ячейка — это регулярная [ требуется ссылка ] тесселяция многообразия или двумерной поверхности , которая делит ее на ряд смежных ячеек, которым затем можно присвоить уникальные идентификаторы и использовать для целей пространственной индексации. Было предложено или в настоящее время используется большое количество таких сеток, включая сетки, основанные на « квадратных » или «прямоугольных» ячейках, треугольные сетки или сетки, шестиугольные сетки и сетки, основанные на ромбовидных ячейках. « Глобальная сетка » — это вид сетки, которая покрывает всю поверхность земного шара .
_illustrated.png/1280px-Geodesic_Grid_(ISEA3H)_illustrated.png)
Квадратные или прямоугольные сетки часто используются для таких целей, как перевод пространственной информации, выраженной в декартовых координатах ( широта и долгота ), в систему координат и из нее. Такие сетки могут быть или не быть выровнены с линиями сетки широты и долготы; например, квадраты Марсдена , квадраты Всемирной метеорологической организации , c-квадраты и другие выровнены, в то время как универсальная поперечная система координат Меркатора и различные локальные системы на основе сеток, такие как британская национальная система координатных сеток, не выровнены. В целом, эти сетки делятся на два класса: « равноугольные » или « равноплощадные ». Сетки, которые являются « равноугольными », имеют размеры ячеек, которые постоянны в градусах широты и долготы, но не равны по площади (особенно при переменной широте). Сетки, которые являются « равноплощадными » ( статистические сетки ), имеют размеры ячеек, которые постоянны по расстоянию на местности (например, 100 км, 10 км), но не по градусам долготы, в частности.
Широко используемая треугольная сетка — это «Quaternary Triangular Mesh» (QTM), разработанная Джеффри Даттоном в начале 1980-х годов. В конечном итоге она привела к диссертации под названием «Иерархическая система координат для геообработки и картографии», опубликованной в 1999 году. [1] Эта сетка также использовалась в качестве основы вращающегося глобуса, который является частью продукта Microsoft Encarta .
Также могут использоваться шестиугольные сетки. В общем, треугольные и шестиугольные сетки строятся так, чтобы лучше приблизиться к целям равной площади (или почти равной) плюс более бесшовного покрытия полюсов, что, как правило, является проблемной областью для квадратных или прямоугольных сеток, поскольку в этих случаях ширина ячейки уменьшается до нуля на полюсе, а те ячейки, которые примыкают к полюсу, становятся 3-, а не 4-сторонними. Критерии оптимальной дискретной глобальной сетки были предложены как Гудчайлдом, так и Кимерлингом [2], в которых ячейки равной площади считаются первостепенно важными.
Quadtrees — это специализированная форма сетки, в которой разрешение сетки варьируется в зависимости от характера и сложности данных, которые необходимо подогнать, в двумерном пространстве. Полярные сетки используют полярную систему координат , используя окружности заданного радиуса, которые разделены на сектора определенного угла. Координаты задаются как радиус и угол от центра сетки.
На практике построение пространственных индексов на основе сетки подразумевает распределение соответствующих объектов по их положению или позициям в сетке, а затем создание индекса идентификаторов объектов по сравнению с идентификаторами ячеек сетки для быстрого доступа. Это пример «управляемого пространством» или независимого от данных метода, в отличие от «управляемого данными» или зависимого от данных метода, который обсуждается далее в Rigaux et al. (2002)). [3] Преимущество пространственного индекса на основе сетки заключается в том, что сначала можно создать структуру индекса, а затем добавлять данные на постоянной основе без необходимости внесения каких-либо изменений в структуру индекса; действительно, если общая сетка используется для разрозненных действий по сбору и индексированию данных, такие индексы можно легко объединить из различных источников. С другой стороны, структуры, управляемые данными, такие как R-деревья, могут быть более эффективными для хранения данных и скорости во время выполнения поиска, хотя они, как правило, привязаны к внутренней структуре заданной системы хранения данных.
Использование таких пространственных индексов не ограничивается цифровыми данными; раздел «индекс» любого глобального или уличного атласа обычно содержит список именованных объектов (городов, улиц и т. д.) с соответствующими идентификаторами ячеек сетки и может считаться вполне приемлемым примером пространственного индекса (в данном случае, как правило, организованного по названию объекта, хотя обратный порядок концептуально также возможен).
Отдельные ячейки сетки также могут быть полезны в качестве единиц агрегации, например, в качестве предшественников анализа данных, представления, картирования и т. д. Для некоторых приложений (например, статистического анализа) ячейки равной площади могут быть предпочтительными, хотя для других это может не иметь первостепенного значения.
В информатике часто требуется найти все ячейки сетки, через которые проходит луч (для трассировки лучей или обнаружения столкновений); это называется «обходом сетки».