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

[Christian Vetter]

Hi,

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?

Z-Order/Morton codes can be computed in a few lines of code without
any branches (https://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN),
Hilbert Curves usually need some loop/recursion. Of course it's
relatively easy to confirm that the rotations are correct by just
looking at the result, but it is still more work than just
interleaving bits *g*. Basically both of them map two pairs of
(unsigned) integers to one (unsigned) integer of twice the size, e.g.
uint32 x + uint32 y <-> uint64 code.

>> Also note that there a binary(ish) search algorithm to find all the nodes in a given bbox. So there is no need for quad trees.
>
> That’s handy, though I have a kdtree implementation that’s adequate [1].  It needs a bit of work, but does the job.

The advantage of Morton/Hilbert codes are, that your node array
implicitly forms a quadtree. However, it is only a quadtree over the
points. whereas you might need something to find ways.

Best regards,

Christian Vetter