July 7, 2008 at 13:25What if your card looks like this?
Greetings, my name is Vlad. I am a leading developer of the Ezem.ru project . In the picture above you see all the sites posted by our users in the Moscow region (8000+ sites). I want to tell you how we solved this problem and what pitfalls were on our way.
The main problem is that when we have more than 500 objects on the map - the average office computer starts to slow down terribly and it becomes difficult to use the map. In addition to the main problem, if you display all the sections, it is impossible to click on a specific marker, and in Moscow there was just some kind of black hole :) We climbed to watch how other users of the Google Maps API solved this problem. GPS-Club: POI: Speed cameras , Where is this house ,MirTesen , Pushkino.org (the first thing that came to mind), either did not solve the problem with the "brakes", or simply limit the number of objects on the screen. And the problem here is more likely not in the google maps api, but in the DOM model itself, which in the Internet killer (IE 6) is already very slow.
Crutches 1. Use standard products.
The view fell on GMarkerManager . The principle of its work is simple. To load in the DOM only those markers that we now see on the screen, thereby reducing the number of DOM objects and making life easier for the browser ...
But looking at the documentation in more detail was a bit confused:
This class is deprecated; developers are recommended to use the open sourced MarkerManager instead.
Crutches 2. Use third-party tools.
After wandering around the Internet and asking around passers-by, I came across a wonderful library with the no less wonderful name " MarkerManager". The principle of its operation is the same as that of GMarkerManager, but with a slight difference. There are functions to delete all markers on the screen and delete a specific marker. This crutch worked sanely, but only until the number of markers exceeded 3 000. Another stone was that the markers were loaded the first time they entered the page, and it took quite a lot of time to process them (200kb XML) on the client side.In general, it was decided to juggle AJAX requests and pull ONLY the visible markers areas and ONLY the zoom on which we are We are now in. This option, with minor corrections, works on our website.
Crutches 3. Grouping markers.
As I said above, the more markers we have concentrated at one point, the more difficult it is to use a map. Indeed, to get on a particular marker, sometimes, it was simply impossible. It was decided to reduce the number of markers on the screen and introduce a group of markers on the server side. The solution is quite simple, but not too correct. For each map zoom, the correct sizes of the rectangles were selected (see the picture on the right) and markers falling into this area were marked as children and only 1 of them was shown on this zoom. And so for each ungrouped marker and for each zoom. The advantages of this approach is that it is now possible to use the map. But this approach has major drawbacks: the calculation took about 12 minutes and was done ONCE a day. We overcame the slowness of the card, but we had another problem: since the counting of markers was done once a day, we could not implement the grouping in our filters. And the browser could easily be brought to its knees by choosing the type: "Individual housing construction (red markers only)" and the size of the plot from 0 to 50 acres.
Crutch 4. Dynamic grouping of markers.
The idea that the browser can be put on our knees with 2 clicks of the mouse did not allow us to sleep peacefully and we decided to make a more advanced version of the grouping:
Option 1. Static squares Oleg Volchkov
gave the idea. Calculate ALL possible squares of the map in advance on ALL possible zooms in advance. Immediately make a reservation that the coefficient of the rectangle for each of the zooms is different and we considered ONLY Russia. We got more than 23 million records and the database “recovered” by 200 MB. The advantage of this approach is that the grouping of markers was carried out more accurately than in the second option. The downside is that the data had to be calculated (it took about one night on a development car) and the already calculated data had to be separated into a separate database, and this would have led to some kind of refactoring.
Option 2. Grouping only by visible area.
Author of this idea Sergey Kolchin. Each time we move the map, we send the coordinates of the area visible to us to the server - so why not just divide this rectangle and group markers in real time? The downside in this case is that when shifted over small distances, the markers will shift slightly. We considered this an uncritical problem because, firstly: the markers do not shift so much, and secondly: the user usually immediately zooms in on the area of interest, rather than traveling on the map. This option, due to the fact that it is simpler and faster than the 1st one, is still used on our website.
A bit of conceptual code:
Example request: http://ezem.ru/gmap/getmarkers/?appoi .. The
tagged-up markermanager
/ * Copyright (c) 2007 Google Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * * Version: 1.0 * Author: Doug Ricket, others * * Marker manager is an interface between the map and the user, designed * to manage adding and removing many points when the viewport changes. * * * Algorithm: The MM places its markers onto a grid, similar to the map tiles. * When the user moves the viewport, the MM computes which grid cells have * entered or left the viewport, and shows or hides all the markers in those * cells. * (If the users scrolls the viewport beyond the markers that are loaded, * no markers will be visible until the EVENT_moveend triggers an update.) * * In practical consequences, this allows 10,000 markers to be distributed over * a large area, and as long as only 100-200 are visible in any given viewport, * the user will see good performance corresponding to the 100 visible markers, * rather than poor performance corresponding to the total 10,000 markers. * * Note that some code is optimized for speed over space, * with the goal of accommodating thousands of markers. * * / The file is large, and I did not upload it. You can see it at the link http://ezem.ru/js/gmap/markermanager.js
Function handler
public function getmarkersAction ()
{
$ params = array ();
foreach (array ('zoom', 'area_min', 'area_max', 'units') as $ k) {
$ params [$ k] = (int) $ this -> _ getParam ($ k, 0);
}
foreach (array ('lat1', 'lat2', 'lng1', 'lng2') as $ k) {
$ params [$ k] = round ((float) $ this -> _ getParam ($ k, 0.0), 4);
}
$ params ['no_groups'] = ('true' == $ this -> _ getParam ('no_groups', null));
$ params ['deal_type'] = ('sell' == $ this -> _ getParam ('deal_type', null))? 'sell': 'buy';
$ params ['appointment'] = explode (',', trim ($ this -> _ getParam ('appointment', '')));
$ params ['except_objects'] = explode (',', trim ($ this -> _ getParam ('except_objects', '')));
$ dbWhere = Medialab_Items :: getActiveItemsLimits ();
if (@ $ this-> user-> id) {
$ dbWhere = array ('(('. implode ('AND', $ dbWhere). ') OR o.uid ='. $ this-> user-> id. ')');
}
$ dbWhere [] = "` deal`.`type` = '". $ params [' deal_type ']."' ";
$ dbWhere [] = '`marker`.`is_polygon` = 0';
$ markers = Medialab_Gmap_Marker :: getMarkersDynamic ($ params, $ dbWhere);
$ qty = 0;
$ s = "\ n ";
foreach ($ markers as $ marker) {
$ isGroup = (1 <$ marker ['qty']);
$ s. = '
.'t = "'. $ marker [' lat '].'" '
.'g = "'. $ marker [' lng '].'" '
.'q = "'. $ marker [' qty '].'" '
.'a = "'. ($ isGroup?' group ': $ marker [' appointment_type ']).'" /> '. "\ n";
$ qty + = $ marker ['qty'];
}
$ s. = '\ n ";
$ s. = ' ';
header ('Content-Type: text / xml; charset = windows-1251');
exit ($ s);
}
REMOVE BR from the code. I had to insert it, otherwise the habraparser is buggy. I don’t know why, but without it, he pulls a piece of code into one line and scrolling appears.
A class that does everything dirty :)
class Medialab_Gmap_Marker
{
/ * *
* Block size in degrees for scale 0.
* 72x128 sets 6x6 blocks in the visible area
* 64x96 - 8x8
* * * /
public static $ blockSize = array (
'lat' => 64.0,
'lng' => 96.0
);
/ **
* Calculates map block dimensions for the provided zoom
*
* @param int $ zoom Map zoom
* @return array Block dimensions in lat / lng
* /
public static function getBlockSize ($ zoom = 10)
{
$ rect = array ();
foreach (array ('lat', 'lng') as $ k) {
$ rect [$ k] = round (self :: $ blockSize [$ k] / (1 << $ zoom), 4);
$ rect [$ k .'_ half '] = round ($ rect [$ k] / 2, 4);
}
return $ rect;
}
/ **
* Fetches markers for visible map area, dynamically grouping them if needed
*
* @param array $ params Array of search params, provide at least (lat, lng) pairs
* for top left / bottom right corners, and current zoom.
* @param array $ dbWhere Additional SQL query conditions (optional)
* @return array Found items
*
* TODO: SW / NE corners instead of top left / bottom right for better consistence w / Google Maps API
* /
public static function getMarkersDynamic (array $ params, array $ dbWhere = array ())
{
$ block = self :: getBlockSize ($ params ['zoom']);
$ dbWhere [] = '(`marker`.`lat` BETWEEN'. $ params ['lat1']. 'AND'. $ params ['lat2']. ')';
// Longitude 180 -> -180 degrees wrap workaround
if ($ params ['lng2'] <$ params ['lng1']) {
$ dbWhere [] = '((`marker`.`lng` BETWEEN'. $ params ['lng1']. 'AND 180.0) OR (` marker`.`lng` BETWEEN -180.0 AND'. $ params ['lng2 '].')) ';
} else {
$ dbWhere [] = '(`marker`.`lng` BETWEEN'. $ params ['lng1']. 'AND'. $ params ['lng2']. ')';
}
if (($ params ['area_min'] || $ params ['area_max']) && $ params ['units']) {
$ unit = DB :: FindFirst ('ezem_units', array ('rate'), array ('id' => $ params ['units']));
if ($ params ['area_min']) {
$ dbWhere [] = '`o`.`area`> ='. ($ params ['area_min'] * $ unit ['rate']);
}
if ($ params ['area_max']) {
$ dbWhere [] = '`o`.`area` <='. ($ params ['area_max'] * $ unit ['rate']);
}
}
$ a = $ params ['appointment'];
if (count ($ a) && $ a [0]) {
$ dbWhere [] = "` appointment`.`type` IN ('".implode ("', '", $ a)."') ";
}
$ a = $ params ['except_objects'];
if (count ($ a) && $ a [0]) {
$ dbWhere [] = '' o`.`id` NOT IN ('.implode (', ', $ a).') ';
}
$ dbGroupBy = '`marker`.`id``;
if (($ params ['zoom'] <13) &&! $ params ['no_groups']) {
// Group only for zooms <= 12 and with no 'no_groups' flag set
$ dbGroupBy = '' grp_lat`, `grp_lng``;
}
$ query = '
SELECT
`marker`.`id`,
`marker`.`object_id`,
`appointment`.`type` AS` appointment_type`,
AVG (`marker`.`lat`) AS` lat`,
AVG (`marker`.`lng`) AS` lng`,
FLOOR ((`` marker`.`lat` - '. $ Params [' lat1 '].') / '. $ Block [' lat '].') AS `grp_lat`,
FLOOR ((`marker`.`lng` - '. $ Params [' lng1 '].') / '. $ Block [' lng '].') AS` grp_lng`,
COUNT (`marker`.`id`) AS` qty`
FROM
`ezem_gmap` AS` marker`
JOIN `ezem_object` AS` o` ON (` o`.`id` = `marker`.`object_id`)
JOIN `ezem_appointment` AS` appointment` ON (` appointment`.`id` = `o`.`appointment_id`)
JOIN `ezem_deal` AS` deal` ON (` deal`.`id` = `o`.`deal_id`)
WHERE
'.implode (' AND ', $ dbWhere).'
GROUP BY
'. $ dbGroupBy;
return DB :: Query ($ query);
}
}
The portal is implemented on Zend Framework , Smarty , Yandex Server and Jquery . A working example of what I spoke about can be viewed on our website .
ps Plans for the near future: add support for polygons and replace Yandex search with sphinx , but more on that in the following articles.
pps We are still looking for sensible programmers .