Pull to refresh
0

Как мы делали картографические сервисы

Reading time 11 min
Views 14K
«Одной из самых перспективных технологий социальных коммуникаций представляются геолокационные сервисы (Location-based services – LBS), позволяющие определить местоположение пользователя/мобильного абонента.
CNews (Подробнее: www.cnews.ru/reviews/index.shtml?2012/06/06/492022»)

Команда Mediagates полностью разделяет эту точку зрения. Поэтому сегодня мы хотим рассказать Хабрасообществу, как мы разрабатывали геолокационные сервисы для нашего проекта — Mediagates.ru. Пост включает в себя выбор картографического сервиса, описание задач, трудностей и алгоритмов решения.

image

О проекте Mediagates.ru


Чтобы было понятно, о чем вообще речь, сначала пару слов о проекте. Основной задачей «Медиагейтс» является объединение профессионалов в области музыки: артистов, продюсеров, промоутеров, площадок и прочих. Более подробно о возможностях проекта, а также его архитектуре мы расскажем в ближайших постах здесь, на Хабре. Пока же можно прочитать пост о проекте у нас на сайте.

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


Основные задачи


Основным и самым важным нашим требованием было максимально возможное проникновение интерактивных и статичных карт на большинство страниц проекта. После изучения структуры нашего сайта мы пришли к тому, что необходимо иметь несколько основных модулей, которые мы сможем размещать в разных разделах проекта:

  1. Интерактивная карта с возможностью отображать на ней те или иные виды маркеров (мероприятия, артисты, промоутеры, площадки, магазины и т.п.) и фильтровать их по дате;
  2. Планировщик туров, который бы позволил на карте или на большом календаре планировать артистам свои выступления и перемещения, предлагать себя различным площадкам и получать предложения о совместных выступлениях от других пользователей;
  3. Форма редактирования местоположения какого-либо объекта, чтобы весь контент на сайте можно было привязать к карте (например, для юзера это некий аналог функции check-in);
  4. Статичные карты с маркерами на них для иллюстрации объектов в списках (иначе пришлось бы инициализировать десятки карт на каждой странице, что было бы накладно как с точки зрения производительности, так и лимитов картографических сервисов). Также статичные карты понадобились для экспорта планировщика туров в изображение в формате JPG.

Более подробно о возможностях карт на Mediagates.ru вы сможете прочитать в статье "Все на карту", размещенной в нашем блоге на сайте, а здесь мы хотели бы поговорить именно о технических моментах реализации сервисов.

Конечно, вы скажете, что каждый из этих пунктов по отдельности относительно прост и очевиден в реализации. Но мы предлагаем углубиться в каждый из них, понять, как их все можно объединить в одном проекте, и разобраться со всеми сложностями и подводными камнями, с которыми нам пришлось столкнуться во время реализации. Начнем с весьма важного решения: выбора картографического сервиса.

Выбор картографического сервиса


Думаю, не стоит углубляться в подробности, поскольку на Хабре немало статей и обзоров на эту тему. Основная проблема, с которой мы здесь столкнулись заключалась в том, что в процессе проектирования нашего сервиса Google Maps API стали платными. Мы, было, испугались, что это может попортить наши планы, но после повторных подробных расчетов, остались при своем решении использовать именно гугловский продукт.

Картографические сервисы, которые мы рассматривали:

  • Google Maps,
  • Яндекс Карты,
  • Cloud Made (или Open Street Map),
  • Bing,
  • API 2ГИС.

Конечный анализ проходил в начале февраля 2012, ситуация с тех пор могла измениться, но параметры отбора были следующие:

  • Качество прорисовки города Ейск (на начальном этапе развития проекта для нас важно, чтобы РФ была прорисована достаточно детально),
  • Прорисовка карт по всему миру (у нас грандиозные планы на будущее),
  • Готовность к кастомизации внешнего вида карт (в результате отказались от этого),
  • Ограничения юридические и по количеству инициализации карт или запросов к тому или иному API,
  • Качество геокодинга (в том числе и по РФ).

Общие впечатления от сравнения были такими:

  • OpenStreetMap оказались наиболее детализированными по всему миру, но имеют не лучший Geocoding API;
  • Уровень прорисовки Мадрида (столицы Испании) на Яндекс Картах оставляет желать лучшего;
  • Bing слабо подготовлен для РФ;
  • API 2ГИС имеют неплохой старт – надеюсь, в будущем ребята составят достойную конкуренцию основным игрокам этого рынка;
  • Google Maps дает обалденный Geocoding API, хотя детализация некоторых городов РФ страдает, чего нельзя сказать о Европе (сам много раз использовал их карты для навигации по городам с iPad вместо навигатора). Платность Google

В результате, мы поняли, что в данный момент нас больше всего устраивает Google Maps API, несмотря на его платность, но в будущем не исключено, что придется переходить на другой картографический сервис. В связи с этим было принято решение, организовывать наш код таким образом, чтобы можно было в любой момент дописать классы для работы с другим картографическим сервисом, без необходимости переписывать основную часть работы с картами. Иными словами, решили разделить задачу на две подзадачи: интерактив на сайте и общение с картографическим сервисом.

Google подкупил нас очень хорошим сервисом геокодирования (Google Geocoding API). Если честно, нашим разработчикам довелось на деле убедиться в бытующей в профессиональном сообществе шутке “Яндекс – Найдется все. Google – Ничего и не терялось.”: Google Geocoding API умудряется найти местоположение очень и очень многих адресов, не требуя от пользователя вводить его на языке оригинала.

Из недостатков гугловского сервиса стоит еще раз подчеркнуть слабое «знание» России и платность (в случае превышения лимита на обращение к API и инициализаций карт). От кастомизации карт пока пришлось отказаться из-за сокращения лимитов на инициализацию кастомизированных карт.

Итак, поставщик сервиса выбран – это Google. Так в нашем распоряжении оказались:

  • Google Maps API v3,
  • Google Geocoding API v3,
  • Google Static Maps API v2.

Теперь предлагаем разобраться с общей архитектурой front-end и back-end. Начнем с front-end.

Основные составляющие front-end


Как мы уже говорили, мы хотели иметь возможность в будущем быстро дописать возможность для работы с другим поставщиком карт. Поэтому мы разработали основополагающие классы, которые являются, по сути, расширением таких классов как:

  • google.maps.Map,
  • google.maps.Marker,
  • google.maps.Geocoder.

Для маркеров нам понадобилась дополнительная возможность отображать названия и всплывающие списки (например для групп маркеров). За основу решили взять класс MarkerWithLabel for V3 от Gary Little и модифицировать его для своих нужд.

Также мы подготовили основные классы для работы с модулями:

  1. интерактивная карта с фильтрами разных типов маркеров и маленьким календарем (в одну полосу),
  2. планировщик туров, который надстраивается на первый класс, заменяя маленький календарь большим (естественно, расширяя его функционал),
  3. указание местоположения объекта.

Основные составляющие back-end


Back-end должен был выполнять следующие основные задачи:

  • Выборку из базы данных большого количества маркеров, отвечающих условиям запроса из front-end и их группировку;
  • Генерацию статичных карт для отображения элементов в списках и экспорта текущего вида карты в планироващике туров в изображение формата jpg;
  • Объединение маркеров (или групп маркеров) мероприятий пользователя непрерывной кривой.

Здесь, в первую очередь, стоит обратить внимание на группировку маркеров, далее рассмотрим процесс объединения маркеров кривой, а в конце – экспорт карт.

Группировка маркеров


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

Группировка бывает двух типов: front-end и back-end. Первая реализовывается на Java Script, вторая – на серверном языке. Для Java Script группировки, существует немало готовых движков, которыми можно было бы воспользоваться, но, передавать такое большое количество данных с сервера в браузер, занятие тоже неблагодарное – чем больше данных, тем медленнее будет соображать браузер, что, в итоге, выльется в понижение скорости работы с сайтом и ухудшение восприятия информации.

Server-side группировка маркеров


После того, как мы остановились на server-side группировке маркеров, стали интересоваться, какие алгоритмы уже придуманы в этой области. Принято говорить о двух наиболее распространенных видах кластеризации: grid-based и distance-based. Первый вариант проще, второй круче с точки зрения алгоритма и реализации. Мы пошли по первому пути для быстрого запуска, но уже работаем над distance-based кластеризацией, которую планируем внедрить в ближайшем будущем.

Суть же grid-based группировки проста: для каждого приближения (зума) земной шар делится на фигуры (условно говоря, прямоугольники), которые и являются группами. Иными словами, если в какую-либо из этих фигур попадает сразу более одного объекта, они группируются в один маркер, символизирующий группу.

image

Объединение маркеров кривой


Изначально мы думали сделать просто ломаную, которая будет объединять в хронологическом порядке определенные маркеры или группы маркеров на карте. Понятно, что делать это удобнее всего при помощи классов google.maps.Polyline и google.maps.PolylineOptions. Но сначала наши GUI дизайнеры, а потом и программисты решили, что намного красивее будет иметь не ломаную линию, а гладкую (на сколько это позволяет построение по точкам) кривую, которая и будет объединять маркеры наших пользователей.

image

Как и в случае с группировкой, решили проектировать эту кривую на стороне сервера, чтобы не перегружать компьютер пользователя. После непродолжительных тестов остановились на методе интерполяции кубическими сплайнами, результат которого передается с сервера в JavaScript, который уже и отрисовывает его по точкам при помощи google.maps.Polyline.

Остановимся подробнее на алгоритме. С точки зрения математики, он не представляет из себя ничего сложного. На PHP мы сделали следующие классы:

  1. Point — просто наглядное хранение координат точки
  2. Cubic — класс для получения значения функции (вида f(x) = d*x^3 + c*x^2 + b*x + a) и ее производной для определенного x и коэфицентов a, b, c, d
  3. Poly – собственно сама интерполяция

Далее представлены минимизированные для понимания исходные коды каждого из этих классов.

Point.inc
<?php

class Point {

	public $x;
	public $y;

	function __construct($x, $y){
		$this->x = $x;
		$this->y = $y;
	}

}

?>


Cubic.inc
<?php

class Cubic {

	private $a;
	private $b;
	private $c;
	private $d;

	function __construct($a, $b, $c, $d){
		$this->a = $a;
		$this->b = $b;
		$this->c = $c;
		$this->d = $d;
	}

	public function eval_($u){
		return (($this->d * $u + $this->c) * $u + $this->b) * $u + $this->a;
	}
	
	public function eval_derivative($u){
		return $this->b + $u * (2 * $this->c + 3 * $this->d * $u);
	}

}

?>


Poly.inc

<?php

class Poly {
	
	public $points;
	
	function __construct(){
		$this->points = array();
	}
	
	public function push($x, $y){
		array_push($this->points, new Point($x, $y));
	}
	
	public function getInterpolatedPoly($stepsNum = 12, $type = 'poly'){
		$i = 0;
		$j = 0;
		$u = 0;
		
		$ret = new Poly();
		
		$sizeofPoints = sizeof($this->points);
		
		if($sizeofPoints >= 2){
			$xpts = $this->xpoints();
			$ypts = $this->ypoints();

			$xc = $this->calcNaturalCubic($sizeofPoints - 1, $xpts);
			$yc = $this->calcNaturalCubic($sizeofPoints - 1, $ypts);
			
			$ret->push($xc[0]->eval_(0), $yc[0]->eval_(0));

			$stepsNum = 100;

			for($i = 0; $i < sizeof($xc); $i++){
				for($j = 1; $j <= $stepsNum; $j++){
					$u = $j / $stepsNum;
					$nx = $xc[$i]->eval_($u);
					$ny = $yc[$i]->eval_($u);
					$ret->push($nx, $ny);
				}
			}
		}
		
		if($type == 'array'){
			$ret_ = array();
			for($i = 0; $i < sizeof($ret->points); $i++){
				array_push($ret_, array(
					'x' => $ret->points[$i]->x,
					'y' => $ret->points[$i]->y
				));
			}
			return $ret_;
		}
		
		return $ret;
	}
	
	private function xpoints(){
		return $this->getPointsArray('x');
	}
	private function ypoints(){
		return $this->getPointsArray('y');
	}
	
	private function getPointsArray($type){
		$r = array();
		$sizeofPoints = sizeof($this->points);
		switch($type){
			case 'y':
				for($i = 0; $i < $sizeofPoints; $i++)
					array_push($r, $this->points[$i]->y);
				break;
			case 'x':
			default:
				for($i = 0; $i < $sizeofPoints; $i++)
					array_push($r, $this->points[$i]->x);
		}
		return $r;
	}
	
	private function calcNaturalCubic($n, &$x){
		$gamma = array();
		$delta = array();
		$D = array();
		$i = 0;

		$gamma[0] = 1.0 / 2.0;
		for($i = 1; $i < $n; $i++)
			$gamma[$i] = 1 / (4 - $gamma[$i-1]);
		$gamma[$n] = 1 / (2 - $gamma[$n-1]);
		
		$delta[0] = 3 * ($x[1] - $x[0]) * $gamma[0];
		for($i = 1; $i < $n; $i++)
			$delta[$i] = (3 * ($x[$i + 1] - $x[$i - 1]) - $delta[$i - 1]) * $gamma[$i];
		$delta[$n] = (3 * ($x[$n] - $x[$n - 1]) - $delta[$n - 1]) * $gamma[$n];
		
		$D[$n] = $delta[$n];
		for($i = $n - 1; $i >= 0; $i--)
			$D[$i] = $delta[$i] - $gamma[$i] * $D[$i + 1];

		$C = array();
		for($i = 0; $i < $n; $i++)
			$C[$i] = new Cubic($x[$i], $D[$i], 3 * ($x[$i + 1] - $x[$i]) - 2 * $D[$i] - $D[$i + 1], 2 * ($x[$i] - $x[$i + 1]) + $D[$i] + $D[$i + 1]);

		return $C;
	}

}

?>



А вот и сам процесс построения наших кривых для произвольных точек. На входе имеем именнованный масив $points с парами значений x и y каждой точки.


<?php

// подключаем необходимые классы
require_once('Point.inc');
require_once('Cubic.inc');
require_once('Poly.inc');

// создаем массив со случайными точками
$points = array();
for($i = 0; $i < 10; $i++)
	$points[$i] = array('x' => rand(100, 500), 'y' => rand(100, 500));

// создаем класс дл€ работы с кривой
$_poly = new Poly();
// заносим координаты точек в этот класс
foreach($points as &$point)
	$_poly->push($point['x'], $point['y']);
// получаем массив точек дл€ построени€ кривой
$lines = $_poly->getInterpolatedPoly(40, 'array');

// создаем изображение
$img = imagecreatetruecolor(600, 600);

// создаем цвета дл€ фона, точек и самой кривой
$whiteC = imagecolorallocate($img, 255, 255, 255);
$greyC = imagecolorallocate($img, 127, 127, 127);
$redC = imagecolorallocate($img, 255, 0, 0);

// заливаем фон картинки
imagefill($img, 0, 0, $whiteC);

// рисуем точки
$halfOfPointWidth = 3;
for($i = 0; $i < sizeof($points); $i++)
	imagefilledrectangle($img, $points[$i]['x'] - $halfOfPointWidth, $points[$i]['y'] - $halfOfPointWidth, $points[$i]['x'] + $halfOfPointWidth, $points[$i]['y'] + $halfOfPointWidth, $redC);

// рисуем кривую по точкам
for($i = 0; $i < sizeof($lines) - 1; $i++)
	imageline($img, $lines[$i]['x'], $lines[$i]['y'], $lines[$i+1]['x'], $lines[$i+1]['y'], $greyC);

// выводим результат на экран в виде png изображени€
header('Content-Type:image/png');
imagepng($img);

// удал€ем изображение
imagedestroy($img);

?>



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

image

А поменяв несколько настроек, можно создать импровизацию на тему «Логотип ХабраХабр»:

image

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

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

Статичные карты и экспорт в JPG


После того, как пользователь распланирует на карте и календаре свой тур, ему наверняка захочется оповестить об этом своих друзей в социальных сетях или опубликовать эту информацию в своем блоге. Для этого мы сделали возможность сохранить текущий вид карты со всеми маркерами на компьютере пользователя в формате JPG.
Реализовали мы это так: при нажатии на кнопку “Сохранить как JPG”, Java Script отправляет всю информацию о текущем view карты и маркерах на ней на сервер, которые подгружает при помощи Google Static Maps API нужный кусок карты, размещает на ней маркеры и сохраняет во временное хранилище файл, ссылка на который и возвращается пользователю в браузер.

Казалось бы, ничего сложного: главное, чего не стоит делать, так это пытаться разместить маркеры на карте самостоятельно после подгрузки изображения из Google Static Maps API – из этого вряд ли выйдет что-нибудь хорошее. Решение намного проще: API позволяет размещать внешние изображения при указании их координат на карте.

Здесь для нас остался открытым один вопрос: как бы покруче запостить карту на стену пользователя на fb.com или vk.com? Не можем сказать, что изучили проблему подробно, но ничего лучше чем экспортировать карту в jpg изображение, а потом вручную публиковать ее на стене, мы не придумали. Буду рад, если подскажете какой-либо способ, позволяющий публиковать изображение большого размера в фоновом режиме. При этом, надо понимать, что это изображение не подходит под понятие user-generated, которое позволяет постить большой размер на фейсбук.

Поиск на карте


В заключение хотели бы добавить пару слов про поиск объектов на карте. Когда мы продумывали эту функцию, мы старались совместить в ней удобство графического интерфейса и получение максимально релевантных результатов. С точки зрения UI всегда очень нравился поиск на afisha.ru – вводишь все, что тебе вздумается, а он тебе сам подсказывает, что есть на сайте по этому запросу да еще и сортирует по типам контента.

В результате мы воспользовались поисковой системой (или сервером, как его иногда называют) sphinx, на которой основывается основной поиск по нашему сайту. С его помощью мы получаем наиболее релевантные данные по запросу пользователя из базы данных. Также на случай, если юзер хочет найти какой-либо адрес, мы делаем запрос к Google Geocoding API.

Результаты поиска по базе и адресам выводятся отсортированные по типам уже после трех первых введенных пользователем символов и дают возможность нажав на них быстро переместиться в то место на карте, где находится этот объект.

Заключение


В целом, пожалуй, и все, что мы хотели бы рассказать по данному вопросу. Нам, конечно, очень интересно, как хабраюзеры отнесутся к проекту, к картам, в частности, и переживем ли мы хабрэффект. Так что welcome, регистрируйтесь, чекиньтесь, тестируйте. Тем, кто поможет советами по экспорту карты в фейсбук и вконтакте, будем премного благодарны.
Tags:
Hubs:
+22
Comments 11
Comments Comments 11

Articles

Information

Website
www.mediagates.ru
Registered
Founded
2011
Employees
2–10 employees
Location
Россия