Добрый день.

Меня интересует вопрос кластеризации геопространственных данных. Конкретно точек.
И у меня в голове сидит мысль по этому поводу.

В PostGIS существуют пространсвенные индексы, которые представляют собой R-деревья.

Вопрос: Можно ли создать такое R-дерево у которого в каждом узле будут хранится данные, близкие друг от друга по расстоянию (расстояние можно будет задавать). Степень дерева будет равна максимально возможному числу зума карты ( у гугла например 20). Таким образом такое дерево будет автоматом кластеризовано, то есть когда я захочу взять маркеры при зуме 10, то мне будут передаваться словари такого вида [номер кластера(узла), кол-во элементов, координаты центра кластера(узла)].

Возможно уже существует такое решение, если да, то подскажите пожалуйста? Либо может есть более продвинутые реализации кластеризации на уровне БД?

Я так понимаю это получается cR-дерево. Есть ли его реализации в PostGIS?

Warstone,

Нету там такого. Там есть классические B и R деревья и GiST. Правда там есть команда CLUSTER, но это что-то другое.

Sergunka,

Да! Квадро дерево еще лучше.

bochkov,

Кластеризация геоданных на стороне сервера.

Допустим у меня сто миллионов точек по всему миру. На клиенте (мобильное приложение) пользователь хочет посмотреть где находятся эти точки и он делает самый большой зум (на весь мир). При этом по классическому варианту (кластеризация на клиенте) пользователю надо выслать все маркеры. Это очень затратно.
Вариант два: кластеризация по запросу на сервере. При этом каждый запрос должен сопровождаться кластеризацией, хоть и на сервере. То есть фактически надо формировать cR или Kd дерево.
Вариант третий, мой: Мы держим такое дерево на уровне БД. Обновление такого дерева (добавление/удаление точек) происходит например раз в 10 минут в фоне. То есть клиенту приходит примерная информация, что в таком то месте есть примерно столько то маркеров.

При приближении идет кластеризация на клиенте.

vyegorov,

Не совсем понял. Это реализация поиска ближайшего соседа?

bochkov,

Не совсем понял..
а как при этом осуществляются операции добавления и удаления точек?

bochkov,

Я не понимаю вашего подхода. Как будет происходить выдача кластеризованных маркеров?
Допустим у меня кучка маркеров, мне надо выдать не эту кучку, а один марке в центре этой кучки + кол-во маркеров в этом кластере.
При этом еще могут быть маркеры не в кучке, их надо выдать отдельно. Либо может быть много кучек...

Я сейчас смотрю в сторону SP-GiST индексов. У них есть реализация Quadtree. Только вот чето они не создаются...

bochkov,

Кажется понял вас, интересная мысль, спасибо! То есть мне надо весь мир разбить на квадраты для каждого зума? Или есть возможность делать запись в опорную таблицу, например я добавил маркер и он автоматом добавился на все уровни зума (пересекся с некоторыми квадартами). А эти квадраты должны физически существовать, чтобы сделать операцию пересечения или как?

bochkov,

Спасибо!

Таблица с квадратами будет просто гигантских размеров на мелких зумах... На сколько я знаю весь мир итак покрыт квадратами ( http://gis-lab.info/qa/gentle-intro-gis-7.html http://gpsmapsearch.com/osm/nom.htm ) и PostGIS скорее всего умеет их определять.. Попробую покопаю в этом направлении...

Closius,

И всеравно.. Тут запрос будет тяжелый.. С деревом было бы на много легче. Хотя тут фактически тоже будет дерево. Но блин не получается построить sp-gist индекс, а он какраз для этих целей..

bochkov,

Хотя.. площадь земли 510072 км^2. Если брать минимальный уровень кластеризации на сервере 10х10 км, то 510072/100 = 5100.72 квадратов. В принципе это не много элементов. Думаю поиск по ним (при индексации) будет не сильно много времени занимать. Как вы думаете?

bochkov,

К тому же северный и южный полюс я кластеризовать не буду)

Блин ошибся.. 510072000 км^2... А это уже очень много 5100720 квадратов.... И что делать?

bochkov,

Все уже придумал) Есть такая вещь как MGRS ( https://en.wikipedia.org/wiki/Military_grid_reference_system). Это некий стандарт, который делит весь мир на зоны с минимальным разрешением 1 м.
Есть конверторы ( для питона например https://github.com/hobu/mgrs ).

То есть я просто в маркер записываю значения его MGRS кода. И когда мне надо выдать какой-то зум я делаю выборку в зависимости от обстоятельств. То есть если уровень самый большой то делаю запрос всех маркеров по UTM (первые 3 знака), подсчитываю в каждом UTM кол-во и выдаю кластеры с центрами по UTM. Пока еще это конкретно не продумал..

Вопрос такой: Есть код '37UDB1366973707'. Мне его как лучше хранить, целиком в одном поле или в разных полях: L1=37D; L2=DB; L3=1,7; ... ?

Просто я относительно новичек в БД и не очень представляю как быстрее сделать выборку будет.

bochkov,

http://www.mappingsupport.com/p/recreation/coordinates_mgrs_topo_map.html более наглядно