StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Really nice question!</p> <p>Quad tree is a solution, as you can also index lines/edges into it, not only nodes.</p> <p>But the problems with this 'naive' approach is that these solutions are memory intensive. E.g. if you already have a very big graph for shortest path calculation then you need the same or more memory for the quad tree (or I was doing something very stupid).</p> <p>One solution is as follows:</p> <ul> <li>use an array which is a grid over the used area. I mean you can devide your area into tiles, and per tile you have an array entry with the list of nodes.</li> <li>so per array entry you'll have a list of nodes in that tile. For an edge you can just add both nodes to the entry. Take care when there are edges crossing a tile without having its node in this tile. The BresenhamLine algorithm will help here.</li> <li>querying: converte the input ala (lat,lon) into a tile number. now get all points from the array entry. Calculate the nearest neighbor of the nodes AND edges to your <em>point A</em> using euclidean geometry (which should be fine as long as they are not too far away which is the case for nearest neighbor).</li> </ul> <p>Is this description clear?</p> <p><strong>Update</strong> This is now <a href="https://github.com/graphhopper/graphhopper/blob/master/src/main/java/com/graphhopper/storage/Location2IDPreciseIndex.java" rel="nofollow">implemented</a> in graphhopper!</p> <p>To get a more memory efficient solution you have to simply exclude identical nodes for one entry (tile). </p> <p>A bit more complicated technic to reduce mem-usage: if a graph traversal respects the tile bounds you can imagine that the graph is then devided into several sub-graphs for that tile (ie. a graph traversal wouldn't reach the other sub-graph within the tile-bounds). Now you don't need all nodes but only the nodes which lay in a different sub-graph! This will reduce the memory usage, but while querying you need to traverse not only one edge further (like in the current graphhopper implementation)! Because you need to traverse the full tile - i.e. as so long as the tile bounds are not exceeded.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload