RussianLDP Рейтинг@Mail.ru
WebMoney: 
WMZ Z294115950220 
WMR R409981405661 
WME E134003968233 		 Visa 
4274 3200 2453 6495 

Small. Fast. Reliable.
Choose any three.
Интерфейс Geopoly к модулю SQLite R*Tree
►Оглавление

1. Обзор

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

Исходный код для Geopoly включен в объединение. Однако, в зависимости от параметров конфигурации и конкретной версии 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 хранит многоугольники в двоичном формате SQL BLOB. Детали двоичного формата даны ниже. Все интерфейсы Geopoly в состоянии принять многоугольники в формате GeoJSON или в двоичном формате.

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

geopoly-таблица составлена следующим образом:

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

Запрос выше составляет новую geopoly-таблицу, названную "newtab". Каждая geopoly-таблица содержит встроенный столбец integer "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() как boolean-функцию в 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_polygons должен будет обычно смотреть на большее количество строк, чем маленький.

Запросы 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() как функцию boolean. Только у 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 тот же самый многоугольник, это вернет не 0. Если P1 или P2 не многоугольник, это возвращает NULL.

geopoly_within(P1,P2) особенная в том, что виртуальная таблица geopoly знает, как использовать индексы R*Tree, чтобы оптимизировать запросы, в которых оператор Where использует geopoly_overlap() как функцию boolean. Только у geopoly_overlap(P1,P2) и geopoly_within(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.

Как пример, следующая диаграмма:

3 4 5 6 7 8 10 12 16 20

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

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 требует, чтобы многоугольники использовали вращение CCW. Но спецификация также замечает, что многие старые файлы GeoJSON содержат многоугольники с вращением по часовой стрелке (CW). geopoly_ccw() полезна для запросов, которые читают старые скрипты GeoJSON. Если вход geopoly_ccw() является правильно форматированным многоугольником, то никакие изменения не внесены. Однако, если обращение входного многоугольника обратное, то geopoly_ccw() полностью изменяет порядок вершин, чтобы это соответствовало спецификации и работало правильно с модулем Geopoly.

4. Детали реализации

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

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

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

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

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

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

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

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

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