Интерфейс Geopoly к модулю SQLite R*Tree

1. Обзор

Модуль Geopoly — это альтернативный интерфейс к расширению R-Tree, который использует обозначение GeoJSON (RFC-7946) для описания двумерных многоугольников. Geopoly включает функции для определения, когда один многоугольник содержится в другом или перекрывается с ним, для вычисления площади, заключённой внутри многоугольника, для выполнения линейных преобразований многоугольников, для визуализации многоугольников в формате SVG и других аналогичных операций.

Исходный код Geopoly включён в amalgamation. Однако, в зависимости от параметров конфигурации и конкретной версии SQLite, расширение Geopoly может быть или не быть включено по умолчанию. Для обеспечения включения Geopoly в вашем сборке, добавьте параметр компиляции -DSQLITE_ENABLE_GEOPOLY=1.

Geopoly работает с «простыми» многоугольниками — то есть многоугольниками, у которых граница не пересекается сама с собой. Таким образом, Geopoly расширяет возможности расширения R-Tree, которое может обрабатывать только прямоугольные области. С другой стороны, расширение R-Tree может обрабатывать от 1 до 5 координатных измерений, тогда как Geopoly ограничен только 2-мерными фигурами.

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

1.1. GeoJSON

Стандарт GeoJSON — это синтаксис для обмена геопространственной информацией с использованием JSON. GeoJSON — это богатый стандарт, который может описывать практически любой вид геопространственного контента.

Модуль Geopoly понимает только небольшой, но критически важный подмножество GeoJSON. В частности, GeoJSON понимает массив JSON вершин, описывающих простой многоугольник.

Многоугольник определяется своими вершинами. Каждая вершина — это массив JSON из двух числовых значений, которые представляют координаты X и Y вершины. Многоугольник — это массив JSON из, по крайней мере, четырёх таких вершин и, следовательно, является массивом массивов. Первая и последняя вершина в массиве должны быть одинаковыми. Многоугольник следует правилу правой руки: при прослеживании линии от одной вершины к следующей, область справа от линии находится вне многоугольника, а область слева — внутри многоугольника. Другими словами, суммарное вращение вершин против часовой стрелки.

Например, следующий JSON описывает равнобедренный треугольник, лежащий на оси X и имеющий площадь 0,5:

[[0,0],[1,0],[0.5,1],[0,0]]

Треугольник имеет три вершины, но описание треугольника в формате GeoJSON имеет 4 вершины, потому что первая и последняя вершины дублируются.

1.2. Формат двоичного хранения

Внутренне Geopoly хранит многоугольники в двоичном формате — BLOB в SQL. Подробности двоичного формата приведены ниже. Все интерфейсы Geopoly могут принимать многоугольники как в формате GeoJSON, так и в двоичном формате.

2. Использование расширения Geopoly

Таблица geopoly создаётся следующим образом:

CREATE VIRTUAL TABLE newtab USING geopoly(a,b,c);

Приведённое выше утверждение создаёт новую таблицу geopoly с именем «newtab». Каждая таблица geopoly содержит встроенный целочисленный столбец «rowid» и столбец «_shape», который содержит многоугольник, связанный с этой строкой таблицы. Приведённый выше пример также определяет три столбца вспомогательных данных с именами «a», «b» и «c», которые могут хранить любую дополнительную информацию, необходимую приложению для связи с каждым многоугольником. Если нет необходимости хранить вспомогательную информацию, список вспомогательных столбцов можно опустить.

Сохранить новые многоугольники в таблицу можно с помощью обычных операторов INSERT:

INSERT INTO newtab(_shape) VALUES('[[0,0],[1,0],[0.5,1],[0,0]]');

Операторы UPDATE и DELETE работают аналогично.

2.1. Запросы

Для запроса таблицы geopoly с использованием индексированного геопространственного поиска используйте одну из функций geopoly_overlap() или geopoly_within() как булеву функцию в предложении WHERE с столбцом «_shape» в качестве первого аргумента функции. Например:

SELECT * FROM newtab WHERE geopoly_overlap(_shape, $query_polygon);

Предыдущий пример вернёт все строки, для которых _shape перекрывается многоугольником в параметре $query_polygon. Функция geopoly_within() работает аналогично, но возвращает только строки, для которых _shape полностью содержится в $query_polygon.

Запросы (а также операторы DELETE и UPDATE), в которых предложение WHERE содержит функцию geopoly_overlap() или geopoly_within(), используют внутренние структуры данных R*Tree для быстрого поиска, который должен просматривать только подмножество строк в таблице. Количество просматриваемых строк, разумеется, зависит от размера $query_polygon. Большие $query_polygon обычно требуют просмотра большего количества строк, чем маленькие.

Запросы к rowid таблицы geopoly также очень быстры, даже для таблиц с огромным количеством строк. Однако, ни один из столбцов вспомогательных данных не является индексом, и поэтому запросы к столбцам вспомогательных данных будут включать полный просмотр таблицы.

3. Специальные функции

Модуль geopoly определяет несколько новых функций SQL, которые полезны для работы с многоугольниками. Все аргументы многоугольников в этих функциях могут быть в формате GeoJSON или во внутреннем двоичном формате.

3.1. Функция geopoly_overlap(P1,P2)

Если P1 и P2 — оба многоугольника, то функция geopoly_overlap(P1,P2) возвращает ненулевое целое число, если между P1 и P2 есть какие-либо перекрытия, или возвращает ноль, если P1 и P2 полностью не пересекаются. Если P1 или P2 не является многоугольником, эта процедура возвращает NULL.

Функция geopoly_overlap(P1,P2) особенная тем, что виртуальная таблица geopoly знает, как использовать индексы R*Tree для оптимизации запросов, в которых предложение WHERE использует geopoly_overlap() как булеву функцию. Только функции geopoly_overlap(P1,P2) и geopoly_within(P1,P2) обладают такой возможностью.

3.2. Функция geopoly_within(P1,P2)

Если P1 и P2 — оба многоугольника, то функция geopoly_within(P1,P2) возвращает ненулевое целое число, если P1 полностью содержится в P2, или возвращает ноль, если любая часть P1 находится вне P2. Если P1 и P2 — один и тот же многоугольник, эта процедура возвращает ненулевое значение. Если P1 или P2 не является многоугольником, эта процедура возвращает NULL.

Функция geopoly_within(P1,P2) особенная тем, что виртуальная таблица geopoly знает, как использовать индексы R*Tree для оптимизации запросов, в которых предложение WHERE использует geopoly_within() как булеву функцию. Только функции geopoly_within(P1,P2) и geopoly_overlap(P1,P2) обладают такой возможностью.

3.3. Функция geopoly_area(P)

Если P — многоугольник, то geopoly_area(P) возвращает площадь, заключённую внутри этого многоугольника. Если P не является многоугольником, geopoly_area(P) возвращает NULL.

3.4. Функция geopoly_blob(P)

Если P — многоугольник, то geopoly_blob(P) возвращает двоичное кодирование этого многоугольника в виде BLOB. Если P не является многоугольником, geopoly_blob(P) возвращает NULL.

3.5. Функция geopoly_json(P)

Если P — многоугольник, то geopoly_json(P) возвращает представление многоугольника в формате GeoJSON в виде текстовой строки. Если P не является многоугольником, geopoly_json(P) возвращает NULL.

3.6. Функция geopoly_svg(P,...)

Если P — многоугольник, то geopoly_svg(P,...) возвращает текстовую строку, которая представляет собой представление этого многоугольника в формате Scalable Vector Graphics (SVG). Если есть более одного аргумента, то второй и последующие аргументы добавляются как атрибуты к каждому графическому элементу SVG. Например:

SELECT geopoly_svg($polygon,'class="poly"','style="fill:blue;"');

Если P не является многоугольником, geopoly_svg(P,...) возвращает NULL.

Обратите внимание, что geopoly использует традиционную декартову систему координат с правой ориентацией с началом в левом нижнем углу, тогда как SVG использует левую систему координат с началом в верхнем левом углу. Процедура geopoly_svg() не пытается преобразовать систему координат, поэтому отображаемые изображения показаны в зеркальном отображении и поворачиваются. Если это нежелательно, процедура geopoly_xform() может использоваться для преобразования вывода из декартовых координат в SVG-координаты перед передачей многоугольников в geopoly_svg().

3.7. Функции geopoly_bbox(P) и geopoly_group_bbox(P)

Если P — многоугольник, то geopoly_bbox(P) возвращает новый многоугольник, который является наименьшим (выровненным по осям) прямоугольником, полностью охватывающим P. Если P не является многоугольником, geopoly_bbox(P) возвращает NULL.

Функция geopoly_group_bbox(P) — это агрегированная версия geopoly_bbox(P). Функция geopoly_group_bbox(P) возвращает наименьший прямоугольник, который будет охватывать все значения P, увиденные во время агрегации.

3.8. Функция geopoly_contains_point(P,X,Y)

Если P — это многоугольник, то geopoly_contains_point(P,X,Y) возвращает ненулевое целое число тогда и только тогда, когда координаты X,Y находятся внутри или на границе многоугольника P. Если P не является многоугольником, geopoly_contains_point(P,X,Y) возвращает NULL.

3.9. Функция geopoly_xform(P,A,B,C,D,E,F)

Функция geopoly_xform(P,A,B,C,D,E,F) возвращает новый многоугольник, являющийся аффинной трансформацией многоугольника P, где преобразование определяется значениями A,B,C,D,E,F. Если P не является допустимым многоугольником, эта процедура возвращает NULL.

Преобразование преобразует каждую вершину многоугольника в соответствии со следующей формулой:

x1 = A*x0 + B*y0 + E
y1 = C*x0 + D*y0 + F

Таким образом, например, чтобы переместить многоугольник на некоторое расстояние DX, DY без изменения его формы, используйте:

geopoly_xform($polygon, 1, 0, 0, 1, $DX, $DY)

Чтобы повернуть многоугольник на R радиан вокруг точки 0, 0:

geopoly_xform($polygon, cos($R), sin($R), -sin($R), cos($R), 0, 0)

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

3.10. Функция geopoly_regular(X,Y,R,N)

Функция geopoly_regular(X,Y,R,N) возвращает выпуклый, простой, правильный, равносторонний, равноугольный многоугольник с N сторонами, центрированный в точке X,Y и с радиусом описанной окружности R. Или, если R отрицательное или если N меньше 3, функция возвращает NULL. Значение N ограничено значением 1000, поэтому процедура никогда не будет отображать многоугольник с более чем 1000 сторонами, даже если значение N больше 1000.

Например, следующий график:

Были сгенерированы этим скриптом:

SELECT '<svg width="600" height="300">';
WITH t1(x,y,n,color) AS (VALUES
   (100,100,3,'red'),
   (200,100,4,'orange'),
   (300,100,5,'green'),
   (400,100,6,'blue'),
   (500,100,7,'purple'),
   (100,200,8,'red'),
   (200,200,10,'orange'),
   (300,200,12,'green'),
   (400,200,16,'blue'),
   (500,200,20,'purple')
)
SELECT
   geopoly_svg(geopoly_regular(x,y,40,n),
        printf('style="fill:none;stroke:%s;stroke-width:2"',color))
   || printf(' <text x="%d" y="%d" alignment-baseline="central" text-anchor="middle">%d</text>',x,y+6,n)
  FROM t1;
SELECT '</svg>';

3.11. Функция geopoly_ccw(J)

Функция geopoly_ccw(J) возвращает многоугольник J с вращением против часовой стрелки (CCW).

RFC-7946 требует, чтобы многоугольники использовали вращение против часовой стрелки. Но спецификация также отмечает, что многие устаревшие файлы GeoJSON не следуют спецификации и содержат многоугольники с вращением по часовой стрелке (CW). Функция geopoly_ccw() полезна для приложений, которые считывают устаревшие скрипты GeoJSON. Если вход в geopoly_ccw() — это правильно отформатированный многоугольник, то изменений не происходит. Однако, если циркуляция входного многоугольника обратная, geopoly_ccw() меняет порядок циркуляции, чтобы он соответствовал спецификации и чтобы он правильно работал с модулем Geopoly.

4. Подробности реализации

Модуль geopoly является расширением расширения R-Tree. Geopoly использует ту же основную логику и таблицы-тени, что и расширение R-Tree. Geopoly просто предоставляет другой интерфейс и предоставляет дополнительную логику для вычисления декодирования многоугольников, перекрытия и содержания.

4.1. Бинарное кодирование многоугольников

Geopoly хранит все многоугольники во внутренней двоичной форме. Двоичный многоугольник состоит из 4-байтового заголовка, за которым следует массив пар координат, в которых каждая размерность каждой координаты представляет собой 32-битное число с плавающей запятой.

Первый байт заголовка — это флаг-байт. Наименее значимый бит флага определяет, хранятся ли пары координат, следующие за заголовком, в формате big-endian или little-endian. Значение 0 для наименее значимого бита означает big-endian, а значение 1 — little-endian. Другие биты первого байта заголовка зарезервированы для будущих расширений.

Следующие три байта в заголовке записывают число вершин в многоугольнике как целое число big-endian. Таким образом, существует верхний предел примерно в 16 миллионов вершин на многоугольник.

После заголовка следует массив пар координат. Каждая координата — это 32-битное число с плавающей запятой. Использование 32-битных чисел с плавающей запятой для координат означает, что любую точку на поверхности Земли можно отобразить с разрешением примерно 2,5 метра. Более высокие разрешения, конечно, возможны, если карта ограничена одной континентальной частью или страной. Обратите внимание, что разрешение координат в модуле geopoly аналогично величине суточного перемещения точек на поверхности Земли из-за приливных сил.

Список координат в двоичном формате не содержит избыточности. Последняя координата не является повторением первой, как это бывает с GeoJSON. Следовательно, в двоичном представлении многоугольника всегда на одну пару координат меньше, чем в представлении GeoJSON.

4.2. Таблицы-тени

Модуль geopoly построен поверх расширения R-Tree и использует те же основополагающие таблицы-тени и алгоритмы. Для целей индексирования каждый многоугольник представляется в таблицах-тенях как прямоугольная ограничивающая рамка. Основополагающая реализация R-Tree использует ограничивающие рамки для ограничения области поиска. Затем процедуры geoploy_overlap() и/или geopoly_within() далее уточняют поиск до точного ответа.

Эта страница была в последний раз изменена 05.12.2023 14:43:20 UTC