[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.

[Nigel Magnay]

I've become confused... - for longitude, the world is -180 to +180. Dividing
the tiles down by halves gives you 90, 45, 22.5, etc., etc - I don't follow
where this is irrational? Or, to make things easier, I've usually tended to
scale the world to be (0,0)->(1,1).

I'm not even trying to do a float->int conversion (and I'm not sure there is
one to interleave the bits without some fairly aggregious bit munging
afterwards).

(x,y) conversion to arbitary QT location is just
  String convert(double x, double y,int numberOfQtPositionsRequired)
  {
      final String lookup = "abcd"; // tl tr bl br
      String result = "";
      while((--numberOfQtPositionsRequired) > 0)
      {
        x -= Math.floor(x);
        y -= Math.floor(y);

        char c = lookup.charAt((x >= 0.5 ? 1 : 0) + (y >= 0.5 ? 2 : 0));
        quad = quad + c;

        // now descend into that square
        x *= 2;
        y *= 2;
      }
      return result;
  }


>
> Let me explain; If we use two 32 bit ints to represent lat and lon, we
> could split the globe into 4.2949673Bn angular increments. Of course,
> this gives us best value in terms of precision for the bits available.
> However, this is at the expense of making conversion from degree to int
> and int to degree reliant on multiplying with a floating point
> irrational number coefficient. In the GPX trace table, I have foregone a
> small degree of the available precision (about 2mm for any location on
> the planet's surface) to use a decimal integer coefficient - 10000000
> instead of 11930464.711111111 recurring.
>
> The 1E7 coefficient makes conversion to/from degrees totally intuitive,
> clean and fast. Hopefully, programmers to the API would be inclined to
> use integer increments of 100nD (nanodegree) as provided by the 1E7
> coefficient.
>
> If we were to sub-divide the world in equal quarters from the start, we
> will end up with values which do not fit the 1E7 coefficient. I
> therefore suggest the quadtile function at bits 3 and 4 represents an
> asymmetric division. On the face of it this may seem messy, but it is
> really neat and clean, and makes degree based calculation easier and
> faster.
>
> The first two bits represent sign for lat/lon. This naturally divides
> the world into quarters. But then, for the value to fit into the 1E7
> coefficient, we simply interleave the integer 1E-7 degree value. Bingo!
> That's it. It is very clean and easy to convert using degrees.
>
> From the freethepostcode database let's use a worked example:
> 51.523343 -0.135136 WC1E 6JL
>
> Multiply with the 1E7 coefficient and make integer positive. Note the
> sign for later.
>
> S=0       _LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
> 515233430 00011110101101011101011010010110
>
> s=1       _lllllllllllllllllllllllllllllll
> 1351360   00000000000101001001111011000000
>
> Loose the MSB (which would otherwise be a sign bit) then interleave:
>
> Capital = Lat Lower=Lon
> s|S=sign bit
> l|L=binary values from above
>
> For an exact location, we get a 64 bit tile reference locating the
> object to within about 1cm
> SsLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLlLl
> 0100001010101000100010110011001011100011011111001101001000101000
>
> If we just take the first 32 bits, we get a 655m tile containing the
> object:
> 01000010101010001000101100110010
>
> If we add the rest of the number into the object, we get the complete
> location:
> 11100011011111001101001000101000
>
> Of course, everything works as per wiki page examples, but part of the
> number ranges will be invalid by using the 1E7 coefficient. In
> visualisation terms, some tile will disappear along a fold in each
> quadrant but for all workable mathematical or computing examples, this
> would be irrelevant and makes for a very obvious conversion function and
> consequently, potential widespread use of integer 100nD increments with
> associated computational savings.
>
>
>
>
>
>
> Nigel Magnay wrote:
> > Ok - I suspect I'm not explaining myself terribly well and the threading
> > gets a bit lost on emails. I have set up the following page on the Wiki:
> >
> > http://wiki.openstreetmap.org/index.php/QuadTiles
> > <http://wiki.openstreetmap.org/index.php/QuadTiles>
> >
> > I have tried to explain why I think tile addressing is essential, and
> > why it ought to be a quadtree implementation and not a simple
> > tile-addressing scheme, and some details of how it might work in
> practice.
> >
> > Whether the address is packed into a 32 or 64-bit integer isn't really
> > that important in comparison. I have a suspicion that it will actually
> > be slower than just using fixed char arrays, but - I don't know mysql
> > that well, and it's totally amenable to experimentation and metric
> > gathering.
> >
> > I'd like to see it in (an|the) API. I don't think it'd be that hard, but
> > it might make sense to resolve the current status of segments at the
> > same time.
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20060918/7ae45025/attachment.html>