Badoo corporate blog
Programming
Go
Geoinformation services
Comments 20
+1
оффтоп
Поэтому у нас расчерчены очень точные границы стран, городов


ну как вам сказать, вот эта штука: «люди рядом», сортирует странно, и часто в перемешку, где «из моего города» идут бывает после людей из соседних областей, тоже самое в «знакомсвта», свайпаешь — и не понятно почему, часто показывает в первую очередь тех кто за более 500км
+1
Здравствуйте! Дело в том, что близость — это только один из параметров, которые мы учитываем при показе людей. А что если именно этот человек в 500 км от вас идеально вам подходит? Как знать!
0
Привет! Записи пока нет, но будет в ближайшее время. Добавим как появится обязательно.
Слайды и код здесь: github.com/mkevac/gophercon-russia-2018
Эта ссылка есть в статье.

Или вы на что-то еще ссылку имели в виду?
+1
а где вы брали полигоны для своего Geoborder'а? полигоны в нем размечены cell'ами фиксированного уровня или все же есть какая-то иерархия?
+2
Частично из openstreetmap, частично сделали вручную.

Полигоны на уровне их построения — это по сути набор точек. Часть, как я сказал, взяты из openstreetmap, а часть созданы вручную в веб-редакторе. Т.е. на этом этапе никаких cell-ов нет.

Уже на этапе geoborder идет покрытие cell-ами. Используются разные уровни cell-ов.

В дополнение к этому geoborder имеет понятие z-индекса. Т.е. какие-то полигоны могут покрываться другими полигонами. Примером является город и университет в нем. Полигон университета находится внутри полигона города.
+1
стало быть есть некоторый индекс в памяти и во время lookup'а координаты транслируются в исходный cell, потом перебираются cell'ы на других уровнях пока не найдется вхождение в индекс?
кстати, а индекс большой выходит? вы его с диска при старте подгружаете?
+2
Да. Все примерно так, как вы описали.
По статистике вижу что у нас около 400к полигонов. Хранится все на диске в RocksDB. Занимает единицы гигабайт. При старте загружаем с диска в память полностью.
0
Оффтоп
Знакомство с гео-библиотекой.
Критичная латентность между «увидел» и «обработал».

Да, признаю, очень странный коммент. Простите.
0
Я не слышал раньше об этом мессенджере. Но не могу утверждать что обошлось без вдохновления этим проектом.
+1
Вопрос на 5 — что будет если кривую Гильберта заменить на Мортон, и как могут быть полезны Коды Грея?
Свойство Гильбертовой кривой, заключающееся в том, что точки, которые находятся рядом на ней, находятся рядом и в пространстве, и тот факт что CellID у нас — просто число, позволяют нам для поиска пользоваться обычным деревом типа B-дерева. В зависимости от того, что мы ищем (точку или область), мы будем пользоваться или get, или range scan, то есть поиском «от» и «до».

С этим можно ознакомиться немного подробнее в статье про Смерть Кащееву.
+1
Я могу быть неправ, но Вы рассказываете о S2 как о чем-то новом, но ведь есть геохэш с миллионом реализаций на гитхабе под любой язык без необходимости ограничиваться 1 реализацией под 1 язык. Все тоже самое — координату с небольшой погрешностью можно обозначить закодированным числом, точки (позиции юзера или др.) одного региона можно выбрать из субд обычной операцией над строками с разной точностью. В чем профит именно S2?
+1
Мало какие вещи в мире можно назвать абсолютно новыми.

Geohash использует похожие алгоритмы для превращения двумерной координаты в одномерную. В этом они похожи. В многих вещах отличаются.

S2 дает вам еще функции для работы с геометрией, например. Клетки S2 имеют похожий размер, в отличие от клеток Geohash. Скачки точности в geohash при переходе на другой уровень сильно больше, чем в S2 и т.д. Боюсь я не настолько хорошо знаю тонкости обеих «либ», чтобы тут все досконально рассказать.

Посмотрите вот тут, например, обсуждение разницы между S2 и Geohash: blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/#comment-40370

И чуть-чуть здесь, хотя на гораздо более обывательском уровне: blog.nobugware.com/post/2016/geo_db_s2_geohash_database
+1
Новом? Я тут посмотрел на репозиторий github, S2 Java. Последние коммиты были 7 лет назад. Т.е., во-первых, это все очень и очень старое (ну, относительно), а во-вторых, выглядит как заброшенное.

При том, что есть заведенные в 2016 issue, где народ спрашивает — а вы вообще планируете библиотеку обновлять, а то хочется того и сего — и ответ от авторов: «Да, конечно же, будем выпускать». Ну и? С 2016 уже прошло два года, а коммиты так и не появились.

Ничего не могу сказать про версию C++, а версии для Java я бы не доверял.
+1
У куба шесть граней. А 3 бита — это 8. Мб было бы лучше проецировать карту на октаэдр, а затем использовать одну из заполняющих кривых для треугольника? Тогда разбиение будет на четрветрь меньше, при той же ёмкости в битах. (С учётом того что используется кривая Гильберта, а не Лебега, время вычисления не важно, так что можно позволить себе и треугольное заполнение.)
Only those users with full accounts are able to leave comments., please.