Maps hacks and Rock`n`Roll

Dont afraid maps. Google maps v3, v2, ovi, yandex maps. Maps is your friend. Try them, love them. I`ll show how to cook them

Tuesday, March 23, 2010

Back to basics - lets start the map

Mission:Start map

Goal:Reduce fails

Step1. Test yourself

In the beggining - test your own map application.

Do this in two steps:

Impliment some king of "loading guard", it will fires if map wont start in 40 seconds



 setTimeout(function(){

    somehow test what map is ready and workable.

    for example - map will fires event "weAreDone".

    catch it!

 },40000);

 /* i thing 40sec is alot of time*/


and then define global error catcher



function global_error_catcher(msg, url, num, more){

    if(msg && msg.name){

        var _event=msg;

        msg=(_event.name+"] "+e.fileName+":"+e.lineNumber+"\n"+e+"\n"+e.stack);

    }

    if(typeof(msg)=='object'){

     var evt=msg;

     msg='';

     for(i in evt)msg+=i+":"+evt[i]+"\n";

    }

    var textout=("global error:\n"+msg+",\n"+url+":"+num+"\n:"+more);

    new Ajax.Request("loader/report_site_error.php",{parameters:{'message':textout},async:true});

    return true;

 }

 window.onerror=global_error_catcher;


Then put this application online and see logs.

So i say "if map working for you - it can not work for others"

And this is true.



some time ago i got bug report "hey men, there is no map on your site".

I test it - map exists, i test my site on other PC.. map exists..

I try to ask friends to test site... and.. MAP EXISTS!!!

but next day i`v got same bug report from other user..

So i impliment listed debug scripts and then i see..
2000 users per day see my site with out map.
2000 users of 50k - 4%

So how to fix it

Step2. Start map

First include google loader


 

function add_script(src){

    var fileref=document.createElement("script");

    fileref.type="text/javascript";

      fileref.src=src;

      document.getElementsByTagName("head")[0].appendChild(fileref);

}



function _do_requestLoader(domain){

    add_script("http://www.google."+domain+"/jsapi?hl=ru&key="+GM_APIKEY);

}



var requestLoader_try=0;

function requestLoader(){

    if(requestLoader_try==0)_do_requestLoader("your domain code(.us,.ru,not just .com)");

    else                    _do_requestLoader("com");

    requestLoader_try++;

    

    map.__init_loadingCycle(0);

}


Next try to call it and include google maps



GoogleMap.prototype.__init_loadingCycle = function (tick){

    clearTimeout(this.__loadingTm); 

    if(tick++>200){

        requestLoader();

        return;

    }

    var thisworker=this;

    //we have google loaded. sometimes( apple\safari google loads in 2-5 tick! )

    if(window.google && typeof(window.google)!=undefined && typeof(window.google.load)=='function'){

        this.console("google start at "+tick+" tick");

        thisworker._enterState('GMaps.load',function(){

        google.load("maps", "3", {other_params:"sensor=true",

                    "callback" : function(){

                        if(thisworker.isClosed){

                            thisworker.console("google post-activaion");

                            return;

                        }

                        thisworker._enterState("google start",function(){

                        thisworker.start();

                        },0);

                        },                

                    "sensor":"true",

                    //and some others params like

                    "language" : "ru",

                    "hl":"ru",

                    "base_domain":"maps.google.ru"

                    });

        },0);

    }

    else{

        //start timer

        this.__loadingTm=setTimeout(function(){thisworker.__init_loadingCycle(tick)},10);

    }

}


Next wait until maps starts, and request maps projection



//lest define projection helper

function GoogleV3ProjectionHelperOverlay(map)

{

    this.setMap(map);

}



GoogleMap.prototype.start = function ()

{

    var _this=this;

    //leave loading state

    this._leaveState(this.loadingState);

    var myOptions = {

      zoom: this.driver.getZoom(),

      center: this.fromLatLng(this.driver.getPosition()),

      mapTypeId: this.decodeMapType(this.driver.getMapType()),

      disableDefaultUI:true,

      scrollwheel:true,

      keyboardShortcuts:false      

    }

    var thisworker=this;    

    this.api = new google.maps.Map(this.divId,myOptions);        

    this.helperOverlay=0;

    this.startIniter=0;

    

    //then define help projector

    GoogleV3ProjectionHelperOverlay.prototype = new google.maps.OverlayView();

    GoogleV3ProjectionHelperOverlay.prototype.draw = function () {

        if (!this.ready) {

            google.maps.event.trigger(this, 'ready');            

            this.ready = true;

            

            //if this overlay ready - start maps

            this.tearMapOn(0);

        }

    };

    

    GoogleV3ProjectionHelperOverlay.prototype.tearMapOn = function(tick){

        //if it have panes - start map

        if(this.getPanes()){

                 _this._enterState("google-doStartInit - "+tick,function(){                 

                 _this.doStartInit();

            });

        }

        else{

            var __this=this;

            setTimeout(function(){__this.tearMapOn(tick++)},1);

        }

    }

    

    //sometimes it good to know how much time took loading of all tiles of map

    this.idleTimer=google.maps.event.addListener(this.api,'idle',function(){

     _this.weAreDone();

     google.maps.event.removeListener(_this.idleTimer);   

    });

    

    this.api.setCenter(myOptions.center);

    this.api.setZoom(myOptions.zoom);

    this.api.setMapTypeId(myOptions.mapTypeId);

    

    //call some callback on API init

    this.onReadyAPI('google','init',this);

    

    //init helperOverlay

    this.helperOverlay=new GoogleV3ProjectionHelperOverlay(this.api);

    this.helperOverlay.setMap(this.api);

    this.helperOverlay.draw();

}



//this function will be called this helperOverlay starts

GoogleMap.prototype.doStartInit = function ()

{

   if( this.startIniter )

     google.maps.event.removeListener(this.startIniter);   

   this.onMapReady();

}




Map started!

and after this step we can convert latlng to pixels as in v2.
Many users want fromLatLngToContainerPixel - here it is!



GoogleMap.prototype.modPointByOffset=function(point,fac){

     var bounds=this.api.getBounds();//this.getBounds();

     var swPoint = this.fromLatLngToDivPixel(bounds.getSouthWest());

     var nePoint = this.fromLatLngToDivPixel(bounds.getNorthEast());

     return {x:point.x-swPoint.x*fac,y:point.y-nePoint.y*fac};

}

     

GoogleMap.prototype.fromLatLngToContainerPixel=function(a){

    var point=this.fromLatLngToDivPixel(a);

    return this.modPointByOffset(point,1);

}

GoogleMap.prototype.fromContainerPixelToLatLng=function(a){

    var point=this.modPointByOffset(a,-1);

    return this.fromDivPixelToLatLng(point);

}

GoogleMap.prototype.fromLatLngToDivPixel      =function(a){

    if(!this.helperOverlay) return {x:0,y:0};

    return this.helperOverlay.getProjection().fromLatLngToDivPixel(a);



}

GoogleMap.prototype.fromDivPixelToLatLng      =function(a){

    return this.toLatLng(this.helperOverlay.getProjection().fromDivPixelToLatLng(a));

}


Step3. Test it again

So we use enter and leavestate functions. The log working flow. If some event "enters", but not "leaves" - we will log.



GoogleMap.prototype._leaveState = function(_event){

    var _this=this;

    _event.leave=_this.microtime();

    _this.console("["+_event.name+"] took " +(_event.leave-_event.enter));

    return _event;

}



GoogleMap.prototype.__callState = function (_event){

    try

    {

            _event.func();

            this._leaveState(_event) ;

    }catch(e){

        _event.error=e;

        this.console("state-error ["+_event.name+"] "+e.fileName+":"+e.lineNumber+"\n"+e+"\n"+e.stack);

        this._leaveState(_event) ;

        this.__stateException(_event,e);

        ;

    }

}



GoogleMap.prototype._enterState = function(name,func,sync,catcheble){

    var _event={'name':name,'func':func,'enter':this.microtime(),'leave':0,'catcheble':catcheble};

    var _this=this;

    this.console('entering ['+name+']'+this._stages.length);

    this._stages.push(_event);

    if(func){

        clearTimeout(this._stageTimeout);

        if(sync){ _this.__callState(_event);

        }

        else{

            this._stageTimeout=setTimeout(

                function(){

                    _this.__callState(_event);

                },1);

        }

    }

    return _event;

}






See error logs again.

W\O this patches 1-5% of request fails

with this patches still some request fails, but just some of this.



so test yourself and see. I test this on 4 sites with 150k unique visitors per day. And i think it is true that map exists not for all of then then you use "standart" way

What about you?




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 start Google V3

Friday, March 19, 2010

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

Wednesday, March 17, 2010

I`ll carve you into tiles

Mission:Make loading a bit faster, and a bit cleaner

Goal:Load data in set of information tiles

loading data blocks via custom map type

Step 1. Load data into map

Lets request server for tiles in visible viewport



$.get("ajax/load-map-data?SE="+MySECorner.toString()+"&NE="+MyNECorner.toString()+"&zoom"+currentZoom,

      function(data){

        //wow! i got the data for map!

        //forwhole visible viewport( and just for it)

      });


Step 2. Kill users, server and youself

Just answer two single things
  • will you rerequest data if maps is moved by pixel
  • can you cache request
If first answer is "no" and second is "no" - close this page. You allready find nirvana :)

And if you still here - you loading your data in wrong way, yet. Until now.

Step 3. How google loads image for tiles?

He(it?) loads it in.. tiles, segments 256x256 pixels :)

Step 4. Think! Why not to do same?

If you load you marker data in set of tiles -
  • you can Perfectly cache them
  • Map shift below 256px will not produce any requests to server
  • Normal browser can perform 4-6 request to one server at one moment, so you`ll ask tiles in parrallel, 4-6 times faster
Define your own tile source, not for image tiles, but for data tiles





var ServerFetchedTiles=[];



function ServerFetchMapType() {

}



ServerFetchMapType.prototype.tileSize = new google.maps.Size(256,256);

ServerFetchMapType.prototype.maxZoom = 32;

ServerFetchMapType.prototype.name = "Server Tile #s";

ServerFetchMapType.prototype.alt  = "Server Data Tile Map Type";      



ServerFetchMapType.prototype.getTile = function(coord, zoom, ownerDocument) {

  var addr=this.getAddr(coord,zoom);

  //test - may be we allready load this block?

  if(ServerFetchedTiles[addr]){

    return

  }

  $.get("ajax/load-map-tile?"+addr,

      function(data){

        ServerFetchedTiles[addr]=data;

        //wow! i got the data just for this tile

        //and any map moving is nothing for me!

      });

};



//and add this tile overlay to current map type

map.overlayMapTypes.insertAt(0, new ServerFetchMapType() );




And you can request tiles in two ways - as google do (x,y,z), or as latlngbox.
I write some code for second variant( i think you`ll use second at the begining )



//we can request tile as tile(x,y,z)

ServerFetchMapType.prototype.getAddrXY = function(coord, zoom){

   return "x="+coord.x+"&y="+coor.y+"&z="+zoom;

}



//or as latlng box

ServerFetchMapType.prototype.getAddrLatLng = function(coord, zoom){

    

    //helper function for mercator projection

   var mercator = function(point){

     //

     var numtiles=Math.pow(2,point.zoom);

     var bitmapsize=numtiles*256;

     var bitmaporigo       =bitmapsize/2;

     var pixelsperlondegree=bitmapsize/360;

     var pixelsperlonradian=bitmapsize/(2*Math.PI);

     

     var lat=bitmaporigo+(pixelsperlondegree*point.x);

     var ged2rad=((point.t*Math.PI)/180.0);

     var sn=Math.sin(deg2rad);

     var lng=((bitmaporigo - 0.5 * log((1+sn)/(1-sn)) * pixelsperlonradian));

     return new google.maps.LatLng(lat,lng);

   }

   var point1={x:coord.x*256,y:coord.y*256,z:zoom} ;

   var point2={x:(coord.x+1)*256,y:(coord.y+1)*256,z:zoom} ;

   var ne=mercator(point1);

   var sw=mercator(point2);

   return "NE="+ne.toString()+"&SW="+sw.toString()+"&z="+zoom;

}


more info about map tiles can be found at google code, and there they point this idea somehow.
Idea - you can load not only images

Step 5. Enjoy

Now try to impliment pieces of this into your own code. Or see how it works on

What lasts?

Ask one question - what you will do if there is no data for tile( you are viewing siberia ), may be just load tile for other zoom( currrent_zoom-2? ).
And how to do it?(we do it).



Homework: and why cites, listed above use other technics? Benefits of quadtree?
( ps: in this mode tiles can he cached on file level. For dirrect nginx access )



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

Load data into google maps. And do it as google do

Tuesday, March 16, 2010

Codename: Romeo-Zulu-Nine-Quebec-Whisky

http://romeowhiskey.net/

yes, this is dash board on google maps v3.

(tech version )

Basic polygon editor

Mission:Make interface able to edit polygon

Goal:Create polygon with edit interface

Step1. Create Polygon

Lets define polygon of 3 points



    var verticles=[new GLatLng(37.4419     , -122.1419),

                   new GLatLng(37.4419+0.03, -122.1419),

                   new GLatLng(37.4419     , -122.1419+0.03)]

    

    myPoly = new myEditablePolygon(verticles,map);

    myPoly.attachClickEvent();

    myPoly.draw();

    

What next?

Next - we need to edit it. Drag edge markers, create new, and delete unused

And i`ll present THREE variants of editor. In one box :)



bla-bla-bla.. lets go down to mathematics

Step2. Determine where we click, and place to add new point

Algorithm is the same as in article about polygon reduce

Take the point, find distance from it to all segments of polygon and add new verticle in right place!

So tranform it to screen space



    /* transform polygon and click point to screen space */

    var screen=this.mapper.toScreenSpace(set);

    var point =this.mapper.toScreenSpace([pt])[0];

    //and add first point as last point

    var L=set.length;

    screen.push(screen[0]);

    

And find that point!



    var minval=10000000;

    var minfit=-1;

    var x2=point.x;

    var y2=point.y;

    var i;

    for( i=0;i<L;i++){

        //remeber the milk!

        /** same login. find distance from point to segment */

        var x1=screen[i].x;

        var y1=screen[i].y;



        var x3=screen[i+1].x;

        var y3=screen[i+1].y;

        

        var vx1=x2-x1;

        var vy1=y2-y1;

        var len=Math.sqrt(vy1*vy1+vx1*vx1);



        var v1=this._norm(vx1,vy1,len);



        var vx2=x3-x1;

        var vy2=y3-y1;

        var len2=Math.sqrt(vy2*vy2+vx2*vx2);

        //if distance to test point is greater that distance to other side of the egde - skip 

        if(len>len2){

            continue;

        }

        var v2=this._norm(vx2,vy2);



        var dot=this._dot(v1,v2);

        var angle=(Math.acos(dot));

        /** we need positive angle and not greater that 60 degress*/

        if(angle>Math.PI/3)continue;

        var sa=Math.sin(angle);



        var perp=sa*len;

        // so this is best fit for point

        if(perp<minval){

            minval=perp;

            minfit=i;

        }

    }

    //and distance must be not very big

    if(minval<50){

     return minfit;

    }

    return -1;

    

Done, all other work you can see by yourself in scripts

Step3. Delete Verticle

just click the marker :)

Google polygon editor variant 1

online version, you can drag markers and you must
CLICK the map near edge to spawn new verticle



  GEvent.addListener(this.map, "click", function(overlay,point){

    _this.newMarker(point,'auto');

  });

  

Google polygon editor variant 2

online version, you can drag markers and just move mouse over edge to create new verticle.

if you click spawned marker - it become normal. So variant like one you can see on wikimapia.org



  GEvent.addListener(this.map, "mousemove", function(point){

    if(!point)return;

    //get current point and move it by 30 pixel to bottom

    var sx=_this.mapper.toScreenSpace([point])[0];

    sx.y+=30;

    point=_this.mapper.toMapSpace([sx])[0]

    //remove old marker

    if(_this.dragMarker){

        _this.removeHold(_this.dragMarker.holdpoint);

        _this.map.removeOverlay(_this.dragMarker);

        delete _this.dragMarker;

    }

    //find where we can(if we can) place new marker

    var position=_this.findBestPosition(point);

    if(position<-1)return;

    else{

      //and place it!  

      var marker=_this.newMarker(point,'auto');

      _this.dragMarker=marker;      

    }

  });

  

Google polygon editor variant 3

online version, you can drag markers and.. hm who add green markers where?

How i do it? Just perform some preprocess before render

    

myEditablePolygon.prototype.preprocess = function(){

    this.removeGhosts();

    this.ghostMarkers=[];

    var i=0;

    var verts=[];

    var inverts=this.verticles.slice(0);

    var L=inverts.length;

    inverts.push(inverts[0]);

    // lets to trought verticles and create some markers in middle of edges

    for ( i=0;i<L;i++){

        var _this=this;

        (function(){

        var x1=inverts[i]._x;

        var y1=inverts[i]._y;

        var x2=inverts[i+1]._x;

        var y2=inverts[i+1]._y;

        var point = new GLatLng(x1+(x2-x1)/2,y1+(y2-y1)/2);

        

        //blue marker from google`s exmaple

        var blueIcon = new GIcon(G_DEFAULT_ICON);

        blueIcon.image = "http://gmaps-samples.googlecode.com/svn/trunk/markers/blue/blank.png";

        

        var marker = new GMarker(point, {draggable: true,icon:blueIcon});

        marker.parent=_this;

        _this.ghostMarkers.push(marker);

        _this.map.addOverlay(marker);

   

        //on mouse down - remove blue marker and create new normal marker

        GEvent.addListener(marker, "mousedown", function() {

          this.parent.map.removeOverlay(this);

          this.parent.newMarker(this.getPoint(),'auto')

        });

        })();

    }

    return this.verticles;

}




Homework: inherit from smartPolygon to perform more complex solution



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

lest make a Very simple polygon editor

how to reduce polygon to fit current zoom level resolution

Mission: create polygon of 1000 verticles and display it w\o lags

Goal: control LOD in real time

Step1. Create Polygon

lets create circle



    //lests create circle

    var polydata=[];

    var Nverts  =1000;

    var step    =Math.PI*2/Nverts;

    var radius  =0.03;

    var i;

    for(i=0;i<Nverts;i++){

      

      polydata.push(new GLatLng(37.4419  +radius*Math.cos(i*step),

                                -122.1419+radius*Math.sin(i*step)));

    }

    

next add it to map



    return new smartPolygon(createCircle(),map,new CoordinatesMapper(map));

    

setup redraw on zoom change



    GEvent.addListener(map, "zoomend", function(){

        _this.render();

    });

    

and change complexity on zoom change



    //convert data to screen space

    var set=this.mapper.toScreenSpace(this.data);

    var inL=set.length;

    //reduce

    set=this.performReduce(set);

    var outL=set.length;

    /** log **/

    document.getElementById("message").innerHTML='polygon reduced from '+inL+' to '+outL;

    //convert back to map space and return

    return this.mapper.toMapSpace(set);

    

But how to change it?


having points 1,2,3 and 4 we need to remove point 2 but keep point 3.

Lets create vector from 1 to 3, and from 1 to 4. We need to caclucate perpendicular P from 3 to L

If it is greater that some delta - so we have visible shift. And we store point 1 and 3 in result set.




    var resultset=[];

    var L=dataset.length;

    resultset.push(dataset[0]);

    dataset.push(dataset[L-1]);    

    var cur=0;

    var j=0;

    for(j=1;j<L;j++)

    {

        var x1=dataset[cur].x;

        var y1=dataset[cur].y;



        var x2=dataset[j  ].x;

        var y2=dataset[j  ].y;



        var x3=dataset[j+1].x;

        var y3=dataset[j+1].y;

        //first points must be different in screen space 

        if(!(((Math.round(x1)==Math.round(x2)) && (Math.round(y1)==Math.round(y2))) ||

             ((Math.round(x2)==Math.round(x3)) && (Math.round(y2)==Math.round(y3)))))

        {



            /*

             goal - create two vectors -

             from current to test point

             and from current to next point

             we need to drop a perpendicular from test point to cur-last vector

             just simple mathematics

            */

            var vx1=x2-x1;

            var vy1=y2-y1;

            var len=Math.sqrt(vy1*vy1+vx1*vx1);



            var v1=this._norm(vx1,vy1,len);



            var vx2=x3-x1;

            var vy2=y3-y1;

            var v2=this._norm(vx2,vy2);



            var dot=this._dot(v1,v2);

            var sa=Math.sin(Math.acos(dot));



            var perp=sa*len;

            //so if perpendicular is bigger than delta, and length of vector is bigger than delta

            //add point to result set

            if(Math.abs(perp)>=delta && len>=delta)

            {

                cur=j;

                resultset.push(dataset[j]);



            }

        }

    }

    

Next iteration will begin from point 3.

In any case - it works!

and, all of this you can see online


Just zoomin and out, and set different deltas(end press enter) to see how it works!

Homework: inherit smartPolygon from GOverlay to produce more transparent solution



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 reduce polygon complexy and be happy