[Routing] Tools for getting from OSM to a routable network

[Nic Roets]

On Tue, Sep 23, 2014 at 2:23 AM, Geoff Leyland <geoff_leyland at fastmail.fm>
wrote:

>
> I’ll definitely have a look an Hilbert curves then.  Christian mentioned
> them being a bit difficult to implement, but from last time I looked at
> them (some time ago) and a quick look at Wikipedia, the transform doesn’t
> seem too tricky.  Am I missing something?  Does special care have to be
> taken in non-square regions?
>

AFAIK, Hilbert curves require n iterations for n bits. Morton codes require
only log(n) iterations for n bits (Not as a computer scientist, but from
the point of few of an x86 hacker). But the encoding speed is not really
important as it's not needed inside the routing loop.

Here is my current encoder, (there certainly will be faster code on the
web):
uint64_t hilbert_order (uint32_t x, uint32_t y)
{
  uint64_t h = 0, m = ((uint64_t) x << 32) | y;
  uint64_t s = m ^ (((uint64_t)y << 32) | x), nots = ~s;
  #define G(z) \
    if ((1ULL<<(z+32))&m) h |= ((1U<<z) & m) ? 2ULL<<(z+z) : 1ULL<<(z+z); \
    else if ((1U<<z) & m) { h |= 3ULL<<(z+z); m ^= nots; } else m ^= s;
  G(31) G(30) G(29) G(28) G(27) G(26) G(25) G(24) G(23) G(22) G(21) G(20)
  G(19) G(18) G(17) G(16) G(15) G(14) G(13) G(12) G(11) G(10) G( 9) G( 8)
  G( 7) G( 6) G( 5) G( 4) G( 3) G( 2) G( 1) G( 0)
  #undef G
  return h;
}



>
>
> Any reason for calculating costs on the fly?  I guess you’re letting users
> customise their vehicle speed profiles?
>

Because the code is simpler


>
> I have int32s for what I guess is the same reason: I mmap the data, and I
> don’t want to require that everything be mapped to the same address every
> time, so I store offsets from a base address.


I do the same, but's easier do discuss the code when it's written as
pointers.


>
> What, though, are your nodes?


My nodes are these substrings/subarrays (I previously referred to them as
subsequences) of the arc array that all have the same lat and lon. The size
of each subarray is equal to the number of ways touching it. If the OSM
node is tagged as something special like a bus stop or a traffic signal,
then the subarray will be one larger.


> Some ways are longer than a single arc, so I’m guessing (but not assuming)
> that you split ways at each intersection.


No. I don't split my ways.


> Likewise, some ways end in the middle of what I think of as an arc (for
> example if there’s a speed limit change), and I stitch these together.  Do
> you also, or do you accept nodes that have only 2 incident ways?  (I know
> that “only 2 incident ways” becomes ambiguous if all your arcs are one-way,
> but I hope my meaning is clear)
>

I don't stitch them together.

So my storage format is very close to the underlying OSM data. it would
relatively easy for me to earn Frederick badge for realtime updates. But I
already have enough badges.

-- 
Regards,
Nic
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20140923/0740d72e/attachment.html>