Clustering/Bunching markers server-side (PHP/MySQL)

[Flamer]

I'm searching for a server-side solution like the clustermarker of
Martin Pearman what is a javascript solution: http://googlemapsapi.110mb.com/clustermarker/
His idea for clustering is to put all markers on the map and after
that checking which marker boundings (not the point, but the icon)
intersects other marker boundings. The clustering goes fast with 1000
markers on FireFox, but with IE the loading goes extremely slow.

What I want is to do this clustering on the server-side: 1 to keep the
data small (only sending detail and cluster markers that are visible
on the map), 2 to speed up the performance of loading these markers.

I have a MySQL table with latitude and longitude columns. I know there
are special spatial columns like Point and Polygon for these things,
but I can't find a way to use these for clustering.
Maybe there is an algorithm to cluster these markers with PHP? I tried
to use a distance range for the clustering (calculating the distance
to every marker and cluster them when they are inside the range of #
kilometers), but that causes jumping cluster markers each time I move
the map.

The opensource MarkerManager is not calculating the clustering
automaticly so I can't use it for this problem.

[jgeerdes [AJAX APIs "Guru"]]

To work with the map, any solution like this is going to require two
parts; one server-side and one client-side. Here's a walk through the
process:

STEP 1: The client-side (Javascript) portion clears the map of any
existing markers, harvests the viewport and zoom information from the
map, constructs a url for the server-side portion, including the
viewport and zoom information as parameters, dynamically creates a new
script element with the url as its src, and appends the script el to
the document head.

STEP 2: The server side component uses the viewport and zoom
parameters to retrieve relevant points from the database which have
been grouped by the lat and lng coordinates into boxes of a given
size. For instance, in one application that I have, I use the
following group by clause:

GROUP BY lat/.02*(grpThreshold-currentZoom),lng/.02*(grpThreshold-
currentZoom)

grpThreshold is the threshold beyond which I don't want the markers to
be grouped at all, and currentZoom represents the zoom level of the
map.

STEP 3: Once the points are retrieved, your server-side bit generates
a line of Javascript that will (a) call a globally-accessible client-
side callback function that can relay information back to the map and
(b) pass that callback function an array of javascript objects that
will define the lat, lng, and other information for the markers.

STEP 4: The client-side portion hears this information, uses it to
generate a series of Markers, and adds those Markers to the map.
Please note that, if you have other markers on the map, you're going
to want to stash these markers in an array somewhere so that you can
remove them when the viewport changes again.

Jeremy R. Geerdes
Effective website design & development
Des Moines, IA

For more information or a project quote:
http://jgeerdes.home.mchsi.com
jgee...@mchsi.com

If you're in the Des Moines, IA, area, check out Debra Heights
Wesleyan Church!

[Flamer]

Thank you for your support.

Your solution puts all the markers in a grid, and then groups them
when there are more than 1 in a box. This is a great solution, however
it will be better when they a grouped based on intersection.

I didn't understand what you meant with the treshold, what number do
you use there? I tried it now with 'COUNT(*) AS numof, ROUND(lat,2) AS
latround, ROUND(lng,2) AS lnground.......GROUP BY latround,lnground'.
This gives me also boxes in a grid.
To avoid the 'neat' placement of the clustermarkers I use 'AVG(lat) AS
avglat, AVG(lng) AS avglng', it returns the average latitude and
longitude of the markers in the cluster, so when placed on the map it
gives a little 'distortion'.
With the 'numof' you can see when it's a detailmarker (numof = 1) or
clustermarker (numof > 1).

However it's not based on intersection, this speeds up the performance
of clustering and displaying the markers extremely! It goes fast in
IE, so it's a good solution for me now, thank you!

Thanks,
Marcel

On 6 aug, 13:49, "jgeerdes [AJAX APIs \"Guru\"]" <jgeer...@mchsi.com>
wrote:

> jgeer...@mchsi.com

[jgeerdes [AJAX APIs "Guru"]]

The grouping threshold is simple the zoom level above which you don't
want markers to be grouped anymore. You could replace it with the
current map type's maximum resolution or any other arbitrary zoom
level. In the application that I utilized this in, I used 14. As for
basing the grouping on intersection, I guess I'm not understanding
what you're wanting unless you mean that you want to group points
where the markers would otherwise overlap. This can be done easily
enough; it's just that you have to do some additional calculations.
Namely, you have to know how much lat/lng the marker is going to
cover. This means translating the points' lat/lng coordinates into
map pixel coordinates and then grouping the markers based on those
coordinates (i.e., y/height, x/width).

You can find the formulae to translate lat/lng to pixel coordinates in
the Mercator projection used by all of the standard map types in
Google Maps in my post here:

http://groups.google.com/group/Google-Maps-API/msg/e318e5cdf58c212c

For other map types with other projections, you're on your own.

Jeremy R. Geerdes
Effective website design & development
Des Moines, IA

For more information or a project quote:
http://jgeerdes.home.mchsi.com

jgee...@mchsi.com

[Dibyendu Das]

Hi Jeremy,

I search for the solution and checked several posts, but it seems you are the only person giving the exactly what I am searching of.  

Can you please give me example code on the same or return JSON server side? 

I checked http://jory.dk/AreaGMC/MapClustering.html and seen they are also doing the same, It would be really helpful if you can please give me some code example.

Thanks for your valuable post.

[Dan]

Possible a but late now but have you looked at http://clustermash.com, they have been able to cluster at least 8 million points of the GeoNames DB on one of their demos. They also show integration with MapQuest and their geocoding and direction API's.