Skype - Google Maps
More work on bunching and display in Google Maps.

I've currently got both a "Viewport" in Google Maps and a "Dataport". The Viewport is what you can see, the dataport is the area for which I get points to plot when I do a refresh. The dataport is twice the size (4 times the area) so that if you scroll the map a short way I don't need to do a round trip to get new data.

What I'm now doing with bunching is this. I've divided the dataport into an 8*8 grid, which implies a 4*4 grid for the viewport. I get the data for the whole dataport. If there are more than 64 points in total I iterate through the cells of the 8*8 grid. If a cell has more than 2 points, I mark the first one as a bunch. I take the average of the others and compute a centre point for the group and apply it to the first point. I then mark the others as "deleted". When I've gone through all 64 cells, each cell has at most 2 points so in the worst case there are 128 points to be mapped. I then go through the remaining points and if there are 2 with identical locations I spread them slightly by adding a small random offset.

The next problem is dealing with the international dateline where the viewport and dataport straddle the transition from longitude 180 to -180. The best solution I've found so far is to work out which side has the most visible and to ignore the other side. So the dataport edge is fixed at 180 or -180. This seems to work well except at one zoom level and map centre. I think this where the dataport actually straddles both 180 and zero. Still working on this.

Apart from the dateline problem there's one last glitch. This happens where there are more than 64 points at a single location. In my dataset this almost happens for "London, UK". The problem is that no matter how much you zoom in, there will always be more than 64 points in total and they are all in one cell so will be bunched. The other limitation is going to be dealing with very large numbers of points, say bigger than 10,000. At some zoom and centre values, bringing all the data into an in memory array and iterating though it repeatedly is going to slow down too much. At that point it would probably be more efficient to do 64 SQL queries rather than one large one and then 64 runs through the data.

So I'm closing in on a set of algorithms to automatically bunch points and to keep speed up by limiting the total number of points that are actually mapped. It works really well!

[ << MSN Messenger Beta ] [ Official Google Base Blog: Create ads for your items >> ]
[ 13-May-06 12:34pm ] [ , ]