Google Maps Server-Side Clustering with Ruby on Rails (RoR)
While working on google maps in the past I have always ran into the same problems time and time again. One of those problems is the issue of clustering. Maps with simple markers and GManagers work great until you start working with a lot more information (10′s of thousands of markers). One could wonder “How is it possible to accurately show thousands of points while maintaining a quick application?”. The answer is simple… use Server-Side Clustering! If you are new to Server-Side clustering I will quickly explain what it is and why it is beneficial when working with lots of points.
Server-Side clustering is a technique of gathering all the points you want to display on the map with a server database call, and then clustering those points while still on the server. Other cluster methods get the points from the server and will cluster the objects on the client side with Javascript. This works okay, but when you are dealing with a lot of objects Javascript can get slow and even time out your user! Clustering the points on the server allows you to decrease the number of objects being sent to the Javascript and gives you more control on maximizing your clustering algorithms speed and efficiency!
I’d like to start by saying that there are many great tutorials and blog posts on Server-Side Clustering out there, however I have yet to find one that is implemented with Ruby on Rails. One of the best tutorials, in my opinion, that I have found was a blog post by Tristen where he describes in pseudo-code how to do Server-Side Clustering and posts some of his source code in Python, which he used for the website www.mapaplace.com. His tutorial is found here and I suggest you go read it as well. Okay! Let’s get into the code now and see how it works in Ruby on Rails!
Step 1: Creating the Controller Action
Let’s start by creating our rails controller which will handle the server side clustering. I created mine in my application’s Maps Controller. Inside my Maps Controller I created a new controller action “server_side_clustering”. For the clustering algorithm to work there are a few key items which we need to have: map height, map width, top left lat and lng, bottom right lat and lng, marker height and marker width. The way you gather this information can either be hard coded in the controller (if the information will not change) or sent in via parameters. For the sake of being safe I send all of my important items as parameters. My controller looks something like this:
def server_side_clustering
@map_height = params[:map_height] # int
@map_width = params[:map_width] # int
@topLeftLat = params[:topLeftLat].to_f # make sure they are floats
@topLeftLng = params[:topLeftLng].to_f
@botRightLat = params[:botRightLat].to_f
@botRightLng = params[:botRightLng].to_f
@lngDelta = (@botRightLng - @topLeftLng).abs.to_f # important
@latDelta = (@topLeftLat - @botRightLat).abs.to_f # important
@marker_height = params[:marker_height].to_f
@marker_width = params[:marker_width].to_f
@listings = [] # this is the array where we keep our objects
end
Step 2: Creating Our Database Call
Next we need to make our database call to retrieve our points. Depending on how you have set up your application you may need to change your database call. Let’s say our map is showing users of our application on the map, that means that we must save each users latitude and longitude to them in some way. I will assume we saved each user’s latitude and longitude to the user table. If it it saved on another table but is connected to the user you will have to do an includes => “desired_table” and JOIN the two tables. The most IMPORTANT part of your database call is that the call must return the objects in a sorted fashion. They must be sorted by longitude. If they are not sorted the clustering will not work correctly and may look a little funky. In our case latitude and longitude is saved to the user table as “lat” and “lng”.
@users = User.find(:all, :order => “lng”)
Now, this call will fetch EVERY user whether they have a lat and lng or not. It also does not take into account distance from your searching point. Let’s set our call so that it will not select users who do not have a lat or lng and will only grab the users within a certain distance which we can specify. I find this very useful if you are clustering your map on different zoom change levels. The method I use for generating the distance (in miles) between two latitude and longitude points is used directly from chapter 11 of RailsSpace. This code was released under the MIT license and is acceptable to be used by anyone. You can find the source code for this on RailsSpace’s web page in Chapter 11, found here. In Javascript you can dynamically find out the general distance in miles that the user is currently looking at and then use that to make the cluster call. This is useful in speeding up the server by not loading unnecessary information the user is not looking at. Here is our distance code and new database call:
# TAKE NOTE: you must send a params[:lat], params[:lng] (Map Center) and params[:distance]
where_clause = []
miles = params[:distance].blank? ? 24860 : params[:distance].to_f
h = %Q{POWER(SIN((RADIANS(users.lat - #{params[:lat]}))/2.0),2) + COS(RADIANS(#{params[:lat]})) * COS(RADIANS(users.lat)) * POWER(SIN((RADIANS(users.lng - #{params[:lng]}))/2.0),2)}
r = 3956 # Earth's radius in miles
distance = "2 * #{r} * ASIN(SQRT(#{h}))"
where_clause << "#{distance} <= #{miles.to_i}"
where_clause << "(users.lat != 0 AND users.lng != 0)"
@users= User.find(:all, :conditions => where_clause.join(" AND "), :order => "lng")
And there we have it. This will collect every user within a certain distance and not include users who do not have a lat or lng. Everything here is fine except one thing. This call will become extremeley slow if you are collecting LOTS of users. Let me show you what I mean. When I ran this application I tested the speed of the query for collecting 9741 objects and it took 3.097 seconds. That is WAY too long. How can we avoid this? The root of this speed issue is not in the database call, but rather in creating 9741 Ruby objects that are put into the @users array. One way to increase this speed is by a nice little trick that my Sensei George Deglin taught me. We can avoid creating the ruby objects and make a straight database call that only returns the information we desire in an array. its called User.send(:construct_finder_sql, …). Be warned that the send(:construct_finder_sql method is a private method of the rails ActiveRecord and that this use of it is more of a “hack” then a good coding technique option. Here’s how we will set it up.
sql = User.send(:construct_finder_sql, :conditions => where_clause.join(" AND "), :order => "lng", :select => "users.id, users.lat, users.lng"))
@users = User.connection.select_rows(sql)
This will put into @users an array of arrays. @users will look like this [[1,"21.98","-100.79],[id, lat, lng], [etc, etc, etc]]. If you do a simple t0 = Time.now before the call and a p "this query got #{@user.size} objects in #{Time.now - t0} seconds!" after the @users object has been created, you will see the speed difference. My 9741 call that took 3.097 seconds before now takes me 0.229 seconds. Simply amazing… I suggest you try it yourself. We are trading of the use-ability of an active record object for the speed of a simple array!
Step 3: Converting Lat/Lng to Map Space
Next we need to convert the the latitudes and longitudes to image/map space. Since we are using Google Maps in this case it is linear and is fairly simple to convert. Once we are done, we will be left with an array of hashed objects, which we will use in the server-side clustering algorithm.
@users.each do |user|
x = (user[2].to_f - @topLeftLng.to_f).abs.to_f / @lngDelta.to_f * @map_width.to_f
y = (user[1].to_f - @topLeftLat.to_f).abs.to_f / @latDelta.to_f * @map_height.to_f
@listings << {:lat => user[1], :lng => user[2], :user_id => user[0], :x => x, :y => y, :left => (x - @marker_width/2), :top => (y + @marker_height/2), :right => (x + @marker_width/2), :bottom => (y - @marker_height/2), :isInCluster => false}
end
Step 4: Server-Side Clustering the Information
Now that we have converted our arrays of id, lat and lng’s into usable objects we can now start performing the Server-Side Clustering! This algorithm was taken from Tristen’s blog’s pseudo-code (mentioned above) and written in Ruby for you to use!
@clusterList = []
@singleList = []
# travel from length of listings to 0
(@listings.size - 1).downto(0) do |ii|
# if listing is in a cluster, skip it
if @listings[ii][:isInCluster] == false
@cluster = { :lat => nil, :lng => nil, :size => 0 }
# travel from ii-1 to 0
(ii-1).downto(0) do |jj|
# if that listing is in a cluster, skip it
if @listings[jj][:isInCluster] == false
# if two listings intersect add them to cluster
if intersects(@listings[ii], @listings[jj]) # this is another action is Maps Controller
# if it's a new cluster, add the ii listing too
if @cluster[:size] == 0
@listings[ii][:isInCluster] = true
@cluster[:lat] = @listings[ii][:lat]
@cluster[:lng] = @listings[ii][:lng]
@cluster[:size] = @cluster[:size] + 1
end
# add jj listing to cluster
@listings[jj][:isInCluster] = true
@cluster[:size] = @cluster[:size] + 1
else
# if the listings are more than the marker width apart, then no more will intersect
if (@listings[ii][:left] - @listings[jj][:left]).abs > @marker_width
break
end
end
end
end
end
# if cluster size is greater than 0, cluster exists
if @cluster[:size] > 0
@clusterList << @cluster
@cluster = { :lat => nil, :lng => nil, :size => 0 }
end
if @listings[ii][:isInCluster] == false
@singleList << @listings[ii]
end
end
# sort clusters by largest
@clusterList.sort!{ |x,y| y[:size] <=> x[:size] }
Inside MapsController but NOT in the server_side_clustering action!
def intersects(this, other)
return !(
other[:left] > this[:right] or
other[:right] < this[:left] or
other[:top] < this[:bottom] or
other[:bottom] > this[:top]
)
end
And there you have it. That is the bulk of our Server-Side Clustering routine! This will iterate through all of our listings and cluster them correctly. It then leaves us with two arrays: @clusterList which contains a lat, lng, and size AND @singleList which contains our listing objects. We then sorted our clusters by size, making the larger ones more prominent in the array and therefore will not be thrown out if we do decided to put some limitations.
Step 5: Adding Clustering Limitations
Some browsers such as Internet Explorer can not handle much more then 100 – 150 points before they get incredibly slow. With Server-Side Clustering, each Cluster will be its own marker and each Single Listing will be its own marker as well. So, there is a possibility that there could be more then 100 – 150 objects. Let’s add a maximum to that so that our app never gets bogged down.
# sort clusters by largest
@clusterList.sort!{ |x,y| y[:size] <=> x[:size] }
# this will maintain the result to a maximum of 100 items sent to the javascript
if @clusterList.size > 100
@clusterList = @clusterList[0..99]
elsif
@clusterList.size + @singleList.size > 100
@singleList = @singleList.sort_by{rand}[0...(100-@clusterList.size)]
end
@return_obj = [@clusterList, @singleList].to_json
render :text => @return_obj
And Voila! There is our Server-Side Clustering action in ruby on rails. Let’s see how it looks all put together!
Step 6: The Finished Result
def server_side_clustering
@map_height = params[:map_height] # int
@map_width = params[:map_width] # int
@topLeftLat = params[:topLeftLat].to_f # my lat and lng from Javascript come as strings, so we must convert them to floats
@topLeftLng = params[:topLeftLng].to_f
@botRightLat = params[:botRightLat].to_f
@botRightLng = params[:botRightLng].to_f
@lngDelta = (@botRightLng - @topLeftLng).abs.to_f # important
@latDelta = (@topLeftLat - @botRightLat).abs.to_f # important
@marker_height = params[:marker_height].to_f
@marker_width = params[:marker_width].to_f
@listings = [] # this is the array where we keep our objects
where_clause = [] # TAKE NOTE: you must send a params[:lat], params[:lng] (Map Center) and params[:distance]
miles = params[:distance].blank? ? 24860 : params[:distance].to_f
h = %Q{POWER(SIN((RADIANS(settings.lat - #{params[:lat]}))/2.0),2) + COS(RADIANS(#{params[:lat]})) * COS(RADIANS(settings.lat)) * POWER(SIN((RADIANS(settings.lng - #{params[:lng]}))/2.0),2)}
r = 3956 # Earth's radius in miles
distance = "2 * #{r} * ASIN(SQRT(#{h}))"
where_clause << "#{distance} <= #{miles.to_i}"
where_clause << "(settings.lat != 0 AND settings.lng != 0)"
sql = User.send(:construct_finder_sql, :conditions => where_clause.join(" AND "), :order => "lng", :select => "users.id, users.lat, users.lng"))
@users = User.connection.select_rows(sql)
@users.each do |user|
x = (user[2].to_f - @topLeftLng.to_f).abs.to_f / @lngDelta.to_f * @map_width.to_f
y = (user[1].to_f - @topLeftLat.to_f).abs.to_f / @latDelta.to_f * @map_height.to_f
@listings << {:lat => user[1], :lng => user[2], :user_id => user[0], :x => x, :y => y, :left => (x - @marker_width/2), :top => (y + @marker_height/2), :right => (x + @marker_width/2), :bottom => (y - @marker_height/2), :isInCluster => false}
end
@clusterList = []
@singleList = []
# travel from length of listings to 0
(@listings.size - 1).downto(0) do |ii|
# if listing is in a cluster, skip it
if @listings[ii][:isInCluster] == false
@cluster = { :lat => nil, :lng => nil, :size => 0 }
# travel from ii-1 to 0
(ii-1).downto(0) do |jj|
# if that listing is in a cluster, skip it
if @listings[jj][:isInCluster] == false
# if two listings intersect add them to cluster
if intersects(@listings[ii], @listings[jj]) # this is another action is Maps Controller
# if it's a new cluster, add the ii listing too
if @cluster[:size] == 0
@listings[ii][:isInCluster] = true
@cluster[:lat] = @listings[ii][:lat]
@cluster[:lng] = @listings[ii][:lng]
@cluster[:size] = @cluster[:size] + 1
end
# add jj listing to cluster
@listings[jj][:isInCluster] = true
@cluster[:size] = @cluster[:size] + 1
else
# if the listings are more than the marker width apart, then no more will intersect
if (@listings[ii][:left] - @listings[jj][:left]).abs > @marker_width
break
end
end
end
end
end
# if cluster size is greater than 0, cluster exists
if @cluster[:size] > 0
@clusterList << @cluster
@cluster = { :lat => nil, :lng => nil, :size => 0 }
end
if @listings[ii][:isInCluster] == false
@singleList << @listings[ii]
end
end
# sort clusters by largest
@clusterList.sort!{ |x,y| y[:size] <=> x[:size] }
# this will maintain the result to a maximum of 100 items sent to the javascript
if @clusterList.size > 100
@clusterList = @clusterList[0..99]
elsif
@clusterList.size + @singleList.size > 100
@singleList = @singleList.sort_by{rand}[0...(100-@clusterList.size)]
end
@return_obj = [@clusterList, @singleList].to_json
render :text => @return_obj
end
def intersects(this, other)
return !(
other[:left] > this[:right] or
other[:right] < this[:left] or
other[:top] < this[:bottom] or
other[:bottom] > this[:top]
)
end
Step 7: Calling Server-Side Clustering with AJAX and Javascript
Here is a quick Javascript way in which we call our server-side cluster. I am using Prototype to call this function with AJAX and then dynamically add the markers.
function loadServerSideClusters() {
var center = map.getCenter();
var bounds = map.getBounds();
var ne = bounds.getNorthEast();
var sw = bounds.getSouthWest();
var topLeft = new GLatLng(ne.lat(), sw.lng());
var botRight = new GLatLng(sw.lat(), ne.lng());
var meters = topLeft.distanceFrom(center);
var miles = meters * 0.000621371192;
if(miles < 1.0) { miles = 1.0; }
req = new Ajax.Request('/maps/server_side_clustering', {
method: 'post',
parameters: { lat: center.lat(), lng: center.lng(), distance: miles, map_width: 525, map_height: 435, topLeftLat: topLeft.lat(), topLeftLng: topLeft.lng(), botRightLat: botRight.lat(), botRightLng: botRight.lng(), marker_width: 41, marker_height: 40 },
onSuccess: function(transport) {
map.clearOverlays();
var result = transport.responseText;
markers = eval("("+result+")");
var clusters = markers[0];
var singles = markers[1];
for(var i=0; i < clusters.length; i++) {
var marker = new GMarker(new GLatLng(clusters[i].lat, clusters[i].lng));
map.addOverlay(marker);
}
for(var i=0; i < singles.length; i++) {
var marker = new GMarker(new GLatLng(singles[i].lat, singles[i].lng));
map.addOverlay(marker);
}
}
});
}
This will call the rails controller with AJAX, return the two arrays (clusterList, singleList( and then uses the information that is stored in them to dynamically create the markers on the map! I call this method on every zoom-level change so that the map is always up to date. Take in to consideration that you will want to code some method of not sending multiple AJAX resquests while the first one you sent is not finished or else you will start stacking on AJAX requests and make everything slow down.
I really hoped this tutorial on Server-Side Clustering with Ruby on Rails was helpful in some way. Please feel free to use my code but please source or “credit” Justin bryant and Inigral Inc in your javascript file! Happy coding! Cheers all!
Download our best practice guides on social media and student engagement.
Learn more about how we're improving enrollment outcomes with social media.
Pingback: Server Side Marker Clustering | Map a Place Blog