Thanks Nic and Christian,
On 22/09/2014, at 8:24 pm, Nic Roets <[email protected]> wrote:
> I agree with Christian that nodes should ordered with the 2D Hilbert curve
> (In Gosmore I made the mistake of using a hybrid between Hilbert curve and
> hashing). I think the improvement is much more than factor 3 when you're
> routing from New York to LA. But it's certainly dependent on the
> implementation details.
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?
> Obviously you should order the nodes according to the Hilbert curve. But you
> should also order the arcs according to the Hilbert curve (the "start_node"
> field that was optimized away). Then the last_arc of a node will be the same
> as first_arc-1 of the next node.
The arcs are ordered that way for the current node ordering - I didn’t make
that very clear in the last email - and so would follow an improved node
ordering.
> In fact, if you put special delimiting entries in your arc array, you can get
> rid of your node array. Then your nodes are subsequences of the arc array.
That’s a nice improvement and simplification. Thanks. However, as you note
later, you lose a compact index of nodes (and as you note, you can work around
that!)
> That's what I did in Gosmore. But I kept the geometry and calculate the costs
> on the fly. So my arc array contains almost everything:
>
> struct doubleArc { // The actual structure has a different name and the
> fields are all int32_t
> int32_t lat, lon;
> doubleArc *forward_end_node, *backward_end_node;
> wayType *wayDetails;
> }
Any reason for calculating costs on the fly? I guess you’re letting users
customise their vehicle speed profiles?
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 have the arc geometry available, but
in a separate array in the same order.
What, though, are your nodes? Some ways are longer than a single arc, so I’m
guessing (but not assuming) that you split ways at each intersection.
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)
> 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.
> To implement Dijkstra, I need some temporary work space. Specifically I need
> 2 structs for every doubleArc (resembling the states of arriving at the node
> using either of the arcs), which is allocated as an array. This array is
> indexed using a direct mapping, so it's entries are also in Hilbert curve
> order. The virtual size of this array is several GB, but it's an mmap() of
> /dev/zero, so it's physical size is typically much smaller.
Especially if you’re using the Hilbert curve! I do much the same - I allocate
one array of int32s for node labels, and a second array to maintain predecessor
information. When you’re generating a distance matrix, you don’t care much
about extracting the paths, so I don’t bother recording predecessors. I
haven’t profiled that, so I’m not sure it’s worthwhile (I know, profiling
should have come first).
> My heaps are arrays of pointers. My experiments showed that the heap stays
> quite small for long route. It seldom exceeds 200 entries.
Thanks, that’s handy to know. Again, some time ago I did some measuring of the
sizes of heaps while generating routes, but I can’t find the notes on what I
learned…
Cheers,
Geoff
[1] https://github.com/geoffleyland/lua-kdtree
_______________________________________________
Routing mailing list
[email protected]
https://lists.openstreetmap.org/listinfo/routing
