Caching overlays by rounding coordinates rectangles - how?

Question

I have a map with overlays which i want to cache - on each place the user visited on the map (which is a rectangle area) - i check if i have a cache of the overlays that reside in this rectangle .

In order to improve caching (so if the user was previously on the same rectangle,except that now he is a few meters away from the previous rectangle) - i want to "round" the coordinates.

This way, each time the user is in a rectange - i check if this rectangle is similar to previously cached rectangles and if so i bring the cached result .

Also, if the user is zoomed out and his rectangle is contained within a bigger (previously cached) rectangle - then I also can use the cached rectangle.

Any suggestions ?

Answer 1

If you're just looking at how to group the coordinates, decide on the maximum difference between coordinates in x and y or latitude and longtitude you want. Then there are two ways you can go about grouping them. The first is easier, but it will be slow if you have many points.

Say we have a data structure called cachedPoints, a max distance between related points called maxdistance and a new point we're trying to check to see if it's close to the other called point.

for each cachedPoint in cachedPoints
{
    if (point.x - cachedPoint.x < maxdistance)
    {
        if (point.y - cachedPoint.y < maxdistance)
        {
              cachedPoint.incrementvisits();  
        }
    }
}

the other way is to use a data structure sorted by x or latitude, and then search to see if there is a cachedpoint with an x or latitude within maxdistance of point, then check the y or longtitude. It'd be a bit faster, but it would take some kind of a hash to implement and adds a bunch of complexity you may not need.

Hopefully that's what you're asking.

Answer 2

If you set up a data structure like:

var a = { 'scales' : [50, 100, 200, 400, 1000],
   'cachedRects': [{'location': 'rect-large-1234-5678.png', x: 1234, y: 5678, scale: 3}
                   {'location': 'rect-small-1240-5685.png', x: 1240, y: 5685, scale: 1} ]
}

you can use the modulo function to do this:

var currentx = GetCurrentX();
var currenty = GetCurrentY();

var currentScale = GetCurrentScale();

var rectFound = false;

foreach(rect in a.cachedRects) {
    if (rect.scale === currentScale 
        && currentx % a.scales[currentScale] === rect.x
        && currenty % a.scales[currentScale] === rect.y) {
            rectFound = true;
            useOverlay(rect);
            break;
    }

}

if(!rectFound) {
    //could loop again for a larger rectangle of a lower scale.
}

the above may or may not turn out to be valid JS - I've not tried to run it. I hope you get the gist, anyway.