Пользователь
0,0
рейтинг
29 августа 2008 в 12:43

Гуглякартим по умному

В последнее время модно стало использовать гуглякарту.
Гугля карту суда, гугля карту туда.
И главное не забыть отобразить свои объектики на карте.
Но, почему-то, подавлявшее число сервисов используют неправильную реализацию процесса передачи маркеров с сервера на клиент.
Точнее они не правильно формируют запросы.
А если выразиться еще более точнее — они это делают

Итак как выглядит обычный запрос с клиента на сервер с пожеланием передать на клиент маркеры для известной области?
Вариант 1 — если у нас маркеров мало — грузим их все( в том числе изначально в код) а потом рисуем. Самые умные используют различные marker-managers для этого…
Но что будет если объектов много?

Вариант 2«слыш сервер, передай мне маркеры для BBOX=(один угол),(другой угол)».
И такой вариант — самый распространенный.
Его использует и «ГдеЭтотДом» и «ДомНаКарте» и «МирТесен» и даже новенький «ВокругМеня».
А еще этот вариант любит сам гугл, так как именно так подгружаются региональные данные из KML.
А еще этот вариант очень любит до момента загрузки «погасить» карту и написать «гружусь...»
А грузятся он долго.

А почему?
Представьте что у вас в БД 100 тыш объектов( в базе викимапии восемь миллионов)…
И надо сделать выборку по двойному ключику(x,y) ОТ и ДО.
И это может занимать(и занимает) секунду, а то и две. А то и более — БД не резиновая.
И малейшее изменение координат вызовет «пере-fetch».
Если бы Базы данных умели говорит — они ты Вас матом крыли :)
Можно конечно облегчить работу базе использую «spatial» форматы( точки и полигоны, в общем изначально данные на плоскости) — но в любом случае — каждый запрос будет уникальным, и эти запросы не кэшируются!
И выборка будет не совсем точная — на клиенте еще придется отсортировать маркеры чтобы в одной точке кучи не было…

Что ж — если вам это нравиться — продолжайте использовать сей подход и далее, а я расскажу про чуть более сложный(и сильно более длинный «по коду» вариант), без этих недостатков.
Сам подход придумал не я, и его реализацию тоже сделал не я.
Более того — раньше я сам использовал Вариант 2.
Но однажды я увидел «как должно быть» и меня посетила (чужая) мудрость.

Итак, предлагаемый мною подход, как не странно, предлагается( и используется) самим гуглем для адресации картинок гуглякарты.
Еще этот подход могли использовать на СЕРВЕРНОЙ части те умные программисты, что в детстве увлекались разным там геймдевов и знают что такое quad-tree.
Я даже знаю один сервис который на серверной стороне имеем маркеры как раз в квад-трии, но запрашивает данные с клиента все равно по Варианту 2.
Ну а как еще сформировать запрос к базе данных?
А тут все просто — надо просто запросить саму ноду :)

Обратимся к первоисточнику — гуглю.
Отрываем хелп по его апи, и идем в самый низ. До момента ручной адресации тайлов.
И видим интересную картинку…
For example, at zoom level 1, the map consists of 4 256x256 pixels tiles, resulting in a pixel space from 512x512
Tiles are indexed using x,y coordinates from that origin. For example, at zoom level 2, when the earth is divided up into 16 tiles, each tile can be referenced by a unique x,y pair:



Ну как, в мозгах ченить «щелкнуло»?
В общем наша задача — не просить выдать все данные по маркерам по сим координатам.
Наша задача — запросить ПЛИТКУ!
И плитку (вот тут собака и зарылась) далеко не одну.

Что нам требуется?
1.Узнать текущий viewport
2.Алгоритмически преобразовать этот viewport в массив плиток, которые нам в данном случае видимы.
3.ОСОЗНАТЬ что часть плиток может сильно уходить за пределы видимой области, что они будут в точности повторять расположение плитки изображений гугля карты, и что их размер будет 256 на 256 пикселей ВСЕГДА(ну это я конечно сильно сказал, можно запрашивать и 128х128 и 512х512, но лучше работать «параллельно» гуглякарте…
4.И после этого еще раз понять что выдача маркеров для одной плитки будет постоянна.
Нам будет известны координаты для которых надо выбрать объекты, нам будет известна пиксельная ширина выборки. Нам будет известен зум карты. Ну и все еще что потребуется для правильного отображения :)

И самое главное — так как выборка идет по постоянным координатам и пиксельному разрешению — обкэшироваться можно :)
И заместо секунды-двух-трех получить выборку объектов хоть за 30мсек на карту
(уточнение: в случае хорошо ускоренной выборки можно получать в один момент до 4хплиток(либо патчить ФФокс, но не он самый популярный броузер), а потом еще 4 плитки, а потом еще…
Считая что обычно отображается от 6ти до 8ми плиток — за 100-200 мсек данные будут на клиенте)
Еще один бонус плиток — если одной маленькой плитке «недостает» объектов чтобы предоставить данные в нужном объеме — она может «уйти» на уровень вверх и передать данные того региона который имеет более количество маркеров.
Тоесть для москвы будет высокое разрешение. А для тундры можно и поменьше

Задача клиентской части — просто следить что и где уже было запрошено.
А если вы сдвинете карту — просто еще пара плиток подгрузиться за очень короткий промежуток.
Только новая часть. Рефреша экрана не будет.

Итак, жил я поживал, добра Вариантом 2 наживал, а потом посетил замечательный проект Wikimapia
Покопался в их формате экпорта и адресации. Принял для себя такойже и понеслась:)
(Что получилось после полугодовалого сиденья на викимапии читайте в топике о моих Соседях)

Потом была расшифровка скриптов викимапии, их осознание и имплантация на себя.

Далее я предоставлю код с живого сервиса.
Код представлен как есть и на 90% сохранен в оригинале, комментариев там нет
Код серверной стороны писался уже самостоятельно.
Используемая адресация, сохраненная с викимапии выглядит как
{SERVERBASE}/z/12/23/34… .xy
где z — говорит что мы запрашиваем объекты(u будет пользовалями, i картинками и так далее)
Если присмотреться то можно понять что «держать» данные можно даже на файловой системе, при добавлении новых объектов просто обновляя часть файлов.
Каждая цифра( 0-3 ) говорит в какой кусок следующего разбиения квад три нам надо перейти.
Лично я не рекомендую использовать диапазон 0-3 а использовать 1-4, тогда адресацию можно будет хранить в BIGINT( например Канада имеем начало 00(левая верхняя часть карты, левая верхняя часть карты) и, в случае хранения в бигинте, это начало «скушается»)

Итак код на клиент — задача по заданому viewport получить массив плиток

Немного кода


//используется для нормирования Y коодинаты
var consar=new Array(-85051128,-83979259,-82676284,-81093213,-79171334,-76840816,-74019543,-70612614,-66513260,-61606396,-55776579,-48922499,-40979898,-31952162,-21943045,-11178401,0,11178401,21943045,31952162,40979898,48922499,55776579,61606396,66513260,70612614,74019543,76840816,79171334,81093213,82676284,83979259,85051128);
//первая часть — само преобразовании координат в деление, название функций и их содержимое взято с викимапии

function getdatakvname(x,y,curzoomkv)
{
  var xdel=0;
  var ydel=0;
  var xline=0;
  var yline=0;
  var x1=-180000000;
  var x2=180000000;
  var y1=-85051128;
  var y2=85051128;
  var y1cons=0;
  var y2cons=32;
  var yconsdel=0;
  var n=0;
  var z=curzoomkv-1;
  while(z>=0)
  {
     xdel=Math.round((x1+x2)/2);
     if(n<4){yconsdel=(y1cons+y2cons)/2;ydel=consar[yconsdel];}
     else  {ydel=Math.round((y1+y2)/2);}
     if(x<=xdel){x2=xdel;xline=xline*2;}
     else    {x1=xdel+1;xline=xline*2+1;}
     if(y<=ydel){y2=ydel;y2cons=yconsdel;yline=yline*2;}
     else   {y1=ydel+1;y1cons=yconsdel;yline=yline*2+1;}
     z--;
     n++
  }
  var out=new Array();
  out.xline=xline;
  out.yline=yline;
  return out;
}

function cheakpoint(x,y,xline,yline,curzoomkv)
{
  var xdel=0;
  var ydel=0;
  var x1=-180000000;
  var x2=180000000;
  var y1=-85051128;
  var y2=85051128;
  var y1cons=0;
  var y2cons=32;
  var yconsdel=0;
  var n=0;
  var xlinetest=0;
  var ylinetest=0;
  var test=0;
  var z=curzoomkv-1;
  while(z>=0)
  {
   xdel=Math.round((x1+x2)/2);
   if(n<4){yconsdel=(y1cons+y2cons)/2;ydel=consar[yconsdel]}
   else  {ydel=Math.round((y1+y2)/2)}
   test=Math.pow(2,z);
   xlinetest=xline&test;
   ylinetest=yline&test;
   if(xlinetest>0){x1=xdel+1}
   else      {x2=xdel}
   if(ylinetest>0){y1=ydel+1;y1cons=yconsdel}
   else      {y2=ydel;y2cons=yconsdel}
   z--;
   n++
  }
  var out=new Array();
  if((x>=x1)&&(x<=x2)&&(y>=y1)&&(y<=y2)){out.res=1}
  else                 {out.res=0}
  return out;
}

function retcode(xline,yline,curzoomkv)
{
var xparam=0;
var yparam=0;
var test=0;
var xlinetest=0;
var ylinetest=0;
var line='';
var z=curzoomkv-1;
while(z>=0)
{
 test=Math.pow(2,z);
 xlinetest=xline&test;
 ylinetest=yline&test;
 if(xlinetest>0){xparam=1}
 else      {xparam=0}
 if(ylinetest>0){yparam=2}
 else      {yparam=0}
 linepart=xparam+yparam;
 line=line+linepart;
 z--;
}
return line;
}

/// и сама функция реквеста

function request_geo_objectsin()  
{
  if(!allow_geo_requests)return;
  require_block={};
  map=GetMap();  
  curzoomkv=map.getZoom()-1;
  bounds  =map.getBounds();
  bounds_sw=bounds.getSouthWest();
  bounds_ne=bounds.getNorthEast();
  var x1point=Math.round(bounds_sw.lng()*1000000);
  var y1point=Math.round(bounds_sw.lat()*1000000);
  var x2point=Math.round(bounds_ne.lng()*1000000);
  var y2point=Math.round(bounds_ne.lat()*1000000);  
  if(x1point<-180000000){x1point=-180000000}if(x2point<-180000000){x2point=-180000000}if(x1point>180000000) {x1point=180000000}if(x2point>180000000) {x2point=180000000}if(y1point<-85051128) {y1point=-85051128}if(y2point<-85051128) {y2point=-85051128}if(y1point>85051128) {y1point=85051128}if(y2point>85051128) {y2point=85051128}
  
  outar=[];
  outar=getdatakvname(x1point,y1point,curzoomkv);
  var xline=outar.xline;
  var yline=outar.yline;
  var maks=Math.pow(2,curzoomkv)-1;
  var vlez=0;
  var xsdvig=0;
  var xlinet=xline;
  var ylinet=yline;
  while(vlez!=1)
  {
   outar=cheakpoint(x2point,y1point,xlinet,ylinet,curzoomkv);
   vlez=outar.res;
   xsdvig++;
   xlinet=xlinet+1;
   if(xlinet>maks){xlinet=0}
  }
  vlez=0;
  var ysdvig=0;
  var xlinet=xline;
  var ylinet=yline;
  while(vlez!=1)
  {
   outar=cheakpoint(x1point,y2point,xlinet,ylinet,curzoomkv);
   vlez=outar.res;
   ysdvig++;
   ylinet=ylinet+1;
   if(ylinet>maks){ylinet=0}
  }
  var temp='';
  var newtemp='';
  var ylinesave=yline;
  var ysdvigsave=ysdvig;
  while(xsdvig>0)
  {
   while(ysdvig>0)
   {
   temp='0'+retcode(xline,yline,curzoomkv);
   var lineleng=0;
   var newtemp='';
   while(lineleng<temp.length)
   {
    newtemp=newtemp+"/"+temp.substring(lineleng,lineleng+3);
    lineleng=lineleng+3;
   }
   var letbe=«z»;
   {
    newtemp='z'+newtemp+gzipext;
    xml_url=newtemp;
    require_block[temp]=xml_url;//+"?x="+x1point+"&y="+y1point+"&x2="+x2point+"&y2="+y2point;
   }
    ysdvig--;yline++;
   if(yline>maks){yline=0}
   }
   yline=ylinesave;
   ysdvig=ysdvigsave;
   xsdvig--;
   xline++;
   if(xline>maks){xline=0}
  
  }
  var i=0;
  clearNavRequestTimeouts();
  for(gotarrn in require_block)
    // ПОЕХАЛИ ЗАПРАШИВАТЬ ПЛИТКИ!


вот и все :)
Осталось получить запрос на стороне сервера и преобразовать его обратно в координаты
$x1=-180000000;
$x2=180000000;
$y1=-85051128;
$y2=85051128;

$y1cons=0;
$y2cons=32;
$yconsdel=0;

$consar=Array(-85051128,-83979259,-82676284,-81093213,-79171334,-76840816,-74019543,-70612614,-66513260,-61606396,-55776579,-48922499,-40979898,-31952162,-21943045,-11178401,0,11178401,21943045,31952162,40979898,48922499,55776579,61606396,66513260,70612614,74019543,76840816,79171334,81093213,82676284,83979259,85051128);


$z=1; 
//RQ это цифры запроса, как не странно длинна запроса равна getZoom()+1
$L=strlen($RQ);
$ZM=$L;
for($i=0;$i<$L;++$i)
{
 
 $test=intval($RQ[$i]); 
 $xdel=round(($x1+$x2)/2);
 if($i<4){$yconsdel=($y1cons+$y2cons)/2;$ydel=$consar[$yconsdel];} 
 else  {$ydel=round(($y1+$y2)/2);}
 
 switch($test)
 {
   case 0:$p1=0;$p2=1;break;
   case 1:$p1=1;$p2=1;break;
   case 2:$p1=0;$p2=0;break;
   case 3:$p1=1;$p2=0;break;
 }
 if($p1){$x1=$xdel+1;}
 else  {$x2=$xdel;}
 if($p2){$y2=$ydel;$y2cons=$yconsdel;}
 else  {$y1=$ydel+1;$y1cons=$yconsdel;}
}

$x1=$x1/1000000;
$x2=$x2/1000000;
$y1=$y1/1000000;
$y2=$y2/1000000;

//BOT И КООРДИНАТЫ НАШЕГО ЗАПРАШИВАЕМОГО БОКСА!
* This source code was highlighted with Source Code Highlighter.


Надеюсь описанный прием найдет своих читателей, и, самое главное, поможет кому-то сделать свой проект( а за ним весь мир ) чуть чуть лучше.

В действии посмотреть на это дело можно либо на «источнике» данного подхода Викимапии, либо на «реципиенте» — моих Соседях
Корзунов Антон @kashey
карма
11,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (29)

  • НЛО прилетело и опубликовало эту надпись здесь
    • +14
      К сожалению этим страдает не статья
      Этим страдаю я.
      Если вы видите ошибки орфографии и семантики — ткните пальцем(в приват)
      по другому не умею, к сожалению.
      • НЛО прилетело и опубликовало эту надпись здесь
      • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        Отсюда вывод — чем больше хороших постов, тем выше поднимется грамотность ;)
  • +2
    Один из бонусов предложеной системы — она может обрабатывать очень много запросов.
    На системе с 3000 человеками в день и НЕДЕЛЬНЫМ! кешем каждый день обрабатывалось более 56378(данные на 26.08) плиток которые были в не кеше.
    Колличесво запрашиваемых плиток я сказать не могу — для скорости просто не учитывал
  • +1
    Благодарю за нужный материал!
  • 0
    отличная статья. Открываются новые(старые) возможности. Спасибо!

    Надо будет разобраться подробнее…
  • –2
    Наверное было бы полезно еще рассказать как ИМХО лучше организовать сам процесс передачи данных с клиента на сервер.
    JSON и XML я сам сразу советую выбросить и забыть.
    Я не понимаю и не признаю людей для которых использование модных инструментов является самоцелью, посему хочу вам напомнить, что маркер это табличный элемент.
    Передача 100 маркеров — это передача 100 строк некой таблицы
    А для передачи таблиц есть очень хороший формат csv.
    Ну и на самой передачи данных можно экономить, например передавать координаты относительно начала того блока котором сидит обьект
    Или примерно также экономить полигональные данные, или для передачи чисел кодировать все в HEX- если задаться целью можно сильно уменьшить трафик между клиентом и вашим сервером.
    Но судя по всему — никому тут это не надо.
    Все прутся от официальных переводов хреновых туториалов по гуглямапам :(
    Эх ребят — у вас все еще впереди
    • +2
      парсинг формата цсв будет быстрее функции eval?
      • +1
        csv будет весить в 10 раз меньше.
        А временем парсинга на самом деле можно пренебречь — оно сильно меньше времени передачи данных
      • 0
        Запросто. eval должен сначала сделать лексический и семантический разбор, а потом обработать результат разбора. Для csv нужен фактически только лексический разбор, да и тот будет быстрее, т.к. регекспы проще.
        • 0
          Технически верно, но ведь эвал он то встроенная функция, а парсинг это джс код, который парсится джс движком.
          Кто-то сверял скорость?
          • 0
            повторяю еще раз.
            Скоростью парсинга в данном случае можно пренебречь.
            Особенно в данном, когда мы качаем данные маленькими блоками.
            В принципе большинство сервисов всеже используют JSON — это их право.
            Использовать его или не использовать должен каждый решить для себя сам.
            Я вообще сейчас частично перехожу на передачу информации картинками, с последующим раздиранием картинки в байтовый поток.
            Типа можно с разных хостов данные грузить и не париться
          • 0
            Код скрипта парсится при загрузке. Парсинг выполняется с помощью регекспов, которые тоже встроенные.

            2kashey: Да, скорость не критична, но не мешайте нам общаться :)
  • +1
    выделите код в тег <pre>
    или пропустите через специальный сервис
    а то совсем читать неудобно
  • 0
    Может быть вопрос не совсем в тему.
    Можно ли как нибудь использовать гуглокарты без инета, а еще лучше с gps'ом?
    Потому что после гуглокарт всякие системы навигации совсем не впечатляют.
    • 0
      Нунасколько я в курсе платная версия гуглямапсплус как раз может это делать.
      А еще есть www.ruslapland.ru/gps.htm может цеплять карты гугля совершенно безвозмездно
  • +3
    я бы это продал. =)
    • 0
      Надо быть добрее и не перенимать западную манеру мыслить деньгами :)
      Раз уж это придумал не я: то будем считать что «я просто разместить обьяву!»
  • 0
    Спасибо, отлично!
    На мою карту кроме меня никто ещё не ходит, но лучше сразу сделать правильно.

    Только вот почему «плитки» — дословный перевод tiles?
    Ещё где-нибудь такой термин применяется?
    Может проще и понятнее — «квадрат»?
    • 0
      квады, а лучше — тайлы (геймдев-термин)
      • 0
        Тайлы они и есть :)
        Только вот первый человек которому я это объяснял что такое тайлы не знал, так как геймдевом не увлекалась.
        Вот решили называть плитками :)
  • +1
    По-умному, по-другому и так далее.

    www.gramota.ru/slovari/dic/? word=%EF%EE-%F3%EC%ED%EE%EC%F3&all=x
  • 0
    Как-то «правильный» вариант сразу пришел в голову после прочтения постановки задачи. Хотя я как раз тем самым Quad-деревом не так давно сталкивался, похоже это и натолкнуло…
  • 0
    Как и обещал, задаю вопрос по алгоритму:

    При вычислении границ тайлов используется вот такая формула:
    if(n<4){yconsdel=(y1cons+y2cons)/2; ydel=consar[yconsdel];}
    else {ydel=Math.round((y1+y2)/2);}

    Долго думал, так и не понял, почему после 4-ой итерации мы больше не пользуемся массивом для нормирования Y-коодинаты.
    Понимаю, что алгоритм не ваш, но всё же любопытно )

    Более очевидным кажется алгоритм из LatLon2Tile с mapki.com, хотя пока не сравнивал результаты.

    • 0
      вообще данную операцию можно и не производить, лично я от нее в последствии отказался
      ее цель малек оквадратить тайл.
      Вообще самая красивая реализация — через сами тайлы карты( такая методика была описана на яндекс-конфе), а как привести Я-тайлы в координатную сетку гугла(для единообразия адресации) я описывал в блоге я-карт

      Лично я в данный момент использую как базис реальное Quad-tree из нод которой беру как адреса тайлов, так и координаты обьектов.
      Без таких хитростей при наличие на карте пары тысяч маркеров начинаются тормоза
      • 0
        вот ссылочка про то что говорит kashey
        как привести Я-тайлы в координатную сетку гугла

        Если ссылка перестанет работать, юзайте поиск в клубе яндекс карт: «Итак — Google тайлы на яндекс картах — SOLVED»
        • 0
          следует также указать что описаный в блоге способ не до конца «солвед»
          Иногда бывают случае когда тайл сдвигается вверх чуть больше чем надо.
          Скажем так.
          вверху получается один ряд не видимых тайлов, а в низу — дырка.
          Красивого решения через яндекс карты — я не обнаружил.
          Сильно легче эмулировать тайлы ручками самостоятельно

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.