Map clustering on S40

[A_Kalinin]

Hi,

I develop S40 app which need to show big amount of points on map. The problem is in points' clustering. How do I implement it on Java ME?

I want something like this: http://api.maps.nokia.com/en/playgro...ermarkers.html but on Java ME not web app.

Thanks in advance

[symbianyucca]

With Java, I don't think we have class like nokia.maps.clustering.ClusterProvider(), so you would propably need to construct this yourself. I would suppose it not being too easy to do, but would assume the idea would generally be to monitor zoom level changes, and then determine which items should be grouped.

The grouping could be determined by checking the icon size in pixels, seeing how much that is in physical distance with current zoom level, and then checking what is the distance between the items. And then having a logic which determines when they should be grouped based on the values.

[jasfox]

The logic behind map clustering is relatively simple. Something like the following pseudo code would do:

Create cluster list.
//For each marker within the current viewport ....
      for (int i= 0; index < markers.Count; i++)
            {
                  if (cluster nearby?){
                        add marker to nearest cluster.
                  } else {
                        create new cluster
                        add marker to cluster
                         add cluster to cluster list 
                  }
                  
            }
return cluster list;

As well as holding an array of associated markers, any cluster needs two further properties - a center point and a radius.
The simplest way to set a centre point would be to use the location of the first marker in the cluster.
The distances should really be related to the viewport size i.e the distance between the
The "nearby" bit can be done using the Haversine formula ie. Geocordinate.distanceTo()


The reason there is no MapComponent providing clustering on the device is due to the limits of the Java ME environment. It doesn't make sense to hold the information about 10,000 markers on a device and it is very likely to run out of memory.

Your best bet would be to look at server side clustering. You could create a MapComponent that overrides mapUpdated so that when the viewport changes it makes a request to a server passing back the coordinates of the viewport. The server would then return the details of the markers within the viewport using clustering as necessary in the form of an XML or JSON file. As a refinement I'd suggest loading a slighltly larger area than the viewport so you only need to make another server request if the user has panned out of area (or altered the zoom.)

If you can move the computations server side, the Maps API is reduced to being a presentation layer, which is the job it does best.

public  abstract class ClusterComponent implements MapComponent {

...
    protected MapDisplay map;
 private double thresholdDistance;

 public void attach(MapDisplay map) {
      this.map = map;
        radius= map.getCenter().distanceTo(
                map.pixelToGeo(
                        new Point(map.getWidth(), map.getHeight())));
    }

    // from MapComponent
    public void mapUpdated(boolean zoomChanged) {
        mapUrl = getMapURL(map);

        if (zoomChanged || map.getCenter().distanceTo(coord) > radius/2) {
           //map.getCenter();
           // radius= map.getCenter().distanceTo(
           //         map.pixelToGeo(
           //                 new Point(map.getWidth(), map.getHeight())));
           
          // 1) Create new thread....
          // 2) Make Server request passing in centerpoint and radius...
          // 3) When received clear all points and re-add markers.
          // etc.
        }
    }

[hamishwillee]

The logic behind map clustering is relatively simple. Something like the following pseudo code would do:

Hi Jason

Is there a wiki article on this, and if not, could you create one?

Regards
Hamish

[jasfox]

I've created a stub for wiki article here: http://www.developer.nokia.com/Commu...PI_for_Java_ME .
I've added two "toy" example coded examples loading asynchronous XML marker data which demonstrate the ideas behind marker clustering. I haven't written the commentary as yet.
Neither example would have any practical use though, as they do not scale and they slow down exponentially as the number of markers increases.
The commentary and examples really need to include information on server side clustering to be of much use in a real world application.

There is a simple PERL script described in the book below which explains how to obtain clustered XML data from a source file
http://books.google.com/books?id=-np...20perl&f=false
This is the source file: http://mappinghacks.com/projects/gmaps/cluster_data.txt
This is the clustered XML data endpoint: http://mappinghacks.com/projects/gma...1&size=240+100

The coded example could be altered to asynchronous load XML from the server which would reduce calculations on the device.
The other bottleneck I've found is the time taken to render each marker on the emulator. If this is a problem on the device, the obvious answer would be to load the whole cluster data as an overlay.