[Openstreetmap-dev] Cache the whole world.

[Mikel Maron]

I think this sort of quadrant addressing has it's advantages, and is commonly used. Check out this analysis of the 
Google Maps satellite tiles [ http://www.dunck.us/collab/Simple_20Analysis_20of_20Google_20Map_20and_20Satellite_20Tiles ]

But it's a whole lot more work than simply harmonizing the requests in the slippy map and editor. This lat/lon to tile algorithm would need to be implemented in both javascript and java, and the reverse implemented on the tile server, in the ruby mapserver replacement (mapserver wouldn't understand these requests).


You know, the slippy map and the editors only share the base landsat imagery in common. In the current tile cache configuration, there is zero benefit to harmonizing the requests, since Landsat is not yet cached seperately. The best solution would be for the editor to proxy harmonized requests to OnEarth through the new cache on landsat.openstreetmap.org. The problem has been that Java will throw up Security dialogs if the applet attempts to access content from another domain. This is why editor tile requests are currently proxied www. We do not want to make requests directly to OnEarth: their server is already overloaded, and subject to unexpected problems, as demonstrated the other week. (Don't get me wrong, OnEarth is an excellent service, we just need to be accomodating) So, there are options...

* Get the applet signed so it can make landsat requests through the cache. 
* Configure apache on www to pass requests for editor requests for the landsat layer through the squid proxy on dev.

In both cases, I have unknowns. Can Java http requests be made through a proxy? Same with Apache?

-Mikel

----- Original Message ----
From: Immanuel Scholz <immanuel.scholz at gmx.de>
To: openstreetmap-dev at vr.ucl.ac.uk
Sent: Thursday, February 16, 2006 11:30:59 AM
Subject: Re: [Openstreetmap-dev] Cache the whole world.

Hi,

> Yes.  The problem is, for a given lat/long (the location of a recent
> edit), what are the *exact* URLs of all the tiles that need refreshing?

I still fail to see the complexity of the problem. Maybe this is due my
outstanding intell... err.. ignorance ;-)


Ok, let's tell how I would do it:

First, I need to find a proper name to the tiles. They could be named like
this:

   is the whole world (no name - only one tile at zoom=0)
00 is the upper left quarter of the world (zoom=1)
01 is the upper right quarter
10 is lower left quarter
11 is lower right quarter
0000 is the upper left quarter of the upper left quarter of the world
0001 is the upper right quarter of the upper left quarter of the world
...
0100 is the upper left quarter of the upper right quarter of the world
101101 is the upper left of the lower right of the lower left part...
etc...

This means, zoom level of a name is its length/2. So you have for zoom=10:
2^20 different tile names...


Ok.. next is how to get from any lat/lon and zoom value to the
corresponding tile name f(lat,lon,zoom) -> tile name:

As example if the zoom is 3, then the tile name will be something like:
"xyxyxy". The x'ses are latitude stuff, the y's are longitude.

The longitude bit of the name can be calculated directly, since it scales
linear. The first y is 0 if longitude is < 0 (in the left half of the
world), 1 else. The second y is 0 if longitude is in the left side of the
first half of the world or 1 if it is in the right side of the world's
half. etc.. do this for every 'y'. (This is basically an other way of
describing the tile name)

Or to say it in an algorithmus (I am not so good in describing algos in
words ;)

tile name = "" (the tile name - only the longitude will be set here)
pivot = 0      (Decision threshold)
delta = 90     (range for next threshold)
for i from 0 to zoom
  if lon < pivot
    tile name = tile name + "0?"  (? since we do not know latitude here)
    pivot = pivot - delta
  else
    tile name = tile name + "1?"
    pivot = pivot + delta
  delta = delta / 2


Well, this is more or less an typical divide and conquer example. ;-)

For the latitude part to work, it has first to be converted in something
linear (Hint: Mercator! ;). Any algorithm will do, as example from the
applet (or look at Mercator.java in JOSM, function latlon2xy ;-). After
this, the very same algorithm like for longitude can be used. (With an
other delta, of course ;)


Ok, after we have the name, the problem is getting from the name to any
lat/lon boundaries (and so the url for the WMS server)
f(tile name) -> fromLat,toLat,fromLon,toLon

Almost the same algorithm as above can be used. "delta" holds half the
size in longitude of the area.

So as example (for longitude):

center = 0     (center longitude of the current position in the tile name)
delta = 90     (half the tile size in longitude of current position)
for i from 0 to zoom
  y = next 'y' value in the tile name
  if y is 0
    center = center - delta
  else
    center = center + delta
  delta = delta / 2
fromLon = center - delta
toLon = center + delta

Similar algorithm for latitude (on the linear latitude!). After getting
fromLat/toLat, this has to be converted to the spheric latitude values,
using the inverted algorithm as above (again, use Mercator.java in JOSM,
this time function xy2latlon)


Now, as you already pointed out, calculating introduce rounding problems.

Simplest solution would be a huge lookup table, but a resulting table
would have a total of 2^40 entries for up to zoom level 20 (zoom=20 means
40 binary digits)... not funny this is!


But stop! The longitude is already linear to the boundaries, so this can
be calculated without any rounding difficulties (no triangulating
functions)!

This is because dividing and multiply by powers of 2 as well as adding and
subtracting is always safe with double/float data types. This reduces any
lookup table to 2^20 entries, since half the numbers bits of the tile name
are calculated.

This can be realistic, but still a bit.. If we reduce the zoom to level 16
(as some suggested already), this would reduce the "official lookup table"
to 2^16 or 64k entries, which is quite ok to me.

As an alternitive, you could round the latitude to some sane and safe
level.. ;-)


Last thing is, that you don't need to store any boundary values of smaller
zoom levels, since they can be extracted from the higher zoom values. To
get the from* values, attach "000000..." until you have the zoom level you
stored. To get the to* values, attach "1111..." instead.


Hope this helped and I did not bored you with already known things? ;)

Ciao, Imi.



_______________________________________________
Openstreetmap-dev mailing list
Openstreetmap-dev at vr.ucl.ac.uk
http://bat.vr.ucl.ac.uk/cgi-bin/mailman/listinfo/openstreetmap-dev