Place 10000 markers on map. And cluster them

Mission:Make map workable with 1000 markers on it

Goal:Cluster and filter

note: if you use google markers directly - you will loose. Rule the MVC and split marker into data,view and controller.
Fetch data from server and store it as data, create controller objects basing on this data.
Next controller will create view, and then view can create marker( or inherits from GOverlay, or just return GIcon and others ballons and hints for marker).


In this article we work with data

---

Step1. Create 1000 markers




somehow




Step 2 or 3. Filter visible markers by viewport

We dont see markers behind map borders. Why not to hide them?

Step 3 or 2. Some markers instersects. Glue them

Is one marker hide other marker - why not to hide bottom marker. Sometimes we dont see it.

Sometimes we see it, but we can click it. And sometimes maps become just a bit overloaded

Lets solve

So we sort markers by some field( actuality, qualyty or roughneck )

Next we take one marker, determine area he "own" and moving all markers in this area from map into "stackedChilds" field of first marker.




Next take next, still alive marker, and go on.

To speed up this step lets use "grid" hashtable.

Divide area into WxH rect pieces( one rect must be smaller than marker ).

Precalculate integer indexes of markers position in this grid, and next search you neightboards only in this area

So what step goest first?

• Clustering is a bit complex thing. I takes a lot of time, so lets filter markers first.
• Dammm it! Now then i move map new markers appers and after clustering i`v gov new image( cos we have new set of data )

Lets work around this.

Map blocks, Cluster index and render set

As told you - we load markers from server in set of tiles. So then you filter - filter only markers from data tiles you can see now.

blocks... tiles... indexes...

Lets repeat this technics one more time

Lets divide map to several blocks( and lets name them clusters ), and cluster them as atoms.

cluster step 1: determine visible set




    //setup cluster by current bounds, zoom and generation

    //hint - generations incriments on each marker insert, or block insert.( so one every change of markers set )

    var workingset=this.cluster.setup(bounds.x1,bounds.y1,bounds.x2,bounds.y2,bounds.zoom,ingen);

    var realbounds=this.cluster.getBounds();

    

    //we have update!

    if(workingset.update.length){

        this.cluster.start(workingset);

        //this function will insert markers to cluster

        QRprepare();

        this.cluster.end();

    }




this functions returns set of cluster to update and bounds cluster want to calculate

next insert data into




if(((obj.LATITUDE)>realbounds.y1 && (obj.LATITUDE)<realbounds.y2 &&

    (obj.LONGITUDE+dimw)>realbounds.x1 && (obj.LONGITUDE-dimw)<realbounds.x2)){

    this.cluster.push(obj);

}




next ask cluster about visible markers




//ask cluster to calculate visible set

this.cluster.setVisibleSet();

//visible objects, hide all not in this set

var torender=this.cluster.getRender(tilethis.LIMIT_OBJECTS);

//hidden objects, show all in this set

var updateset=this.cluster.getUpdateset(tilethis.LIMIT_OBJECTS);




render set is a VISIBLE markers, and you need to hide all markers not in this set( by yourself )

update set is a set of markers you must show, or update( update also fires then changes internal stack-count of marker)

So hide some markers and show others
Note: we collect all hide\show\update in long arrays and execute them in packs. DIP cost and so so :)

To do same just HIDE map, show\hide 10-100 markers and SHOW map.

if you just showing markers - you can create them in other node, detached from document, and then you ready - attach this "group marker" to map node

There is also mistical "DocumentFragments", margical reflow-and-redraw and other dreadfull things, we dont talk about.




//hide

for(i in this.visiblePipeline){

            if(i && this.visiblePipeline[i])

             if(!torender[i] || typeof(torender[i])=='undefined'){

                this.hideObject(i);

             }

}

//and show

for(ii in updateset){

    i=updateset[ii];

    tilethis.showObject(i);

}

//hint: show commands will be stored in visiblePipeline




End. So what we got

1. First ask cluster for bounds it want to calculate

2. Put data only in nodes cluster want to be updated.

3. Clustering is executed only then you have some update or maps moves more than cluster-size pixels

4. Cluster rule you! It produce dirrect comands to show\hide, and you just execute.

5. My english is not so good as this article. Please turn on your own brain-spell-corrector and correct me.

(comrade - to much vodka i drink, and bears cry out on the street and i can sleep )
to find bears on the streets of moskow and see how this clustering works - try GdeEtotDom

Bugs?

In this implemetation there is one feature, not the bug.

As we calcucate cluster as atoms - one cluster dont know nothing about markers in next cluster.

So one cluster truly thinks that markers near the edge dont have niegboards( the pass to other cluster )

So you can got something like this.



How to reduce this effect:

variant 1 - make cluster bigger

variant 2 - after clustering tiles we got static set of rendermarkers. Lets try apply one more cluster index on this set, but move cluster start by CLUSTERSIZE/2 px.

As result new clusters will glue wrong markers.

Try it by yourself

For now you can try this version, but file is not documented and also you can see how it works here



some images used from this article

Homework: And what it R-trees?

All of sections, i list here, is allready done by me. I need just to wrap code into article, and, yap, english article :)

If you want to know more - ask

How to cluster map markers in serven days

this is a mirror of this article