Thanks for the quick response Daniel. I'll need to think it over a bit; I
may end just using something along the lines of GetNetworkDistance[WithCore]
Senior Software Engineer
[image: Lyft] <http://www.lyft.com/>
On Wed, Nov 30, 2016 at 4:13 PM, Daniel Patterson <dan...@mapbox.com> wrote:
> Hi Chris,
> Ah, this is tricky. If you just create a Datafacade pointing at a
> `.osrm` files, you don't really get an easily explorable graph. Only the
> Contraction Hierarchy is loaded into memory, and it's not really conducive
> to simple neighbor traversal. In order to find a path in a CH, you need to
> know both ends of the route, it's inherently bidirectional.
> Check out the workflow at:
> this shows the various transformations that happen to the road graph
> from OSM data. We then create the Contraction Heirarchy based on the
> edge-expanded graph, and that's what's available during routing. I didn't
> bother drawing the CH graph as the final step after the edge-expanded
> graph, because, well, it's just a mess of lines and shortcuts.
> When you call NearestPhantomNodesInRange(), it returns the IDs of the
> edge-expanded-graph nodes (the black dots in the fourth step). A single
> PhantomNode will have two node IDs, one for each travel direction allowed
> on the snapped edge.
> The .u and .v properties *are* the original node-based-graph node IDs
> and can be looked up with GetCoordinateOfNode(). In order to get the
> node-based-node IDs for the rest of the road between the endpoints, you
> need to call GetUncompressedForwardGeometry(phantom_node.packed_geometry_id)
> which will return a vector of node-based-node IDs that you can pass to
> The GetAdjacentEdgeRange/GetTarget functions return nodes in the CH
> graph, so they could go anywhere. The problem is that the CH is inherently
> bidirectional, so if you ask for all the outgoing edges from a node, you
> may not get all the neighbors - the connection may only exist in the graph
> in reverse *from the neighbor* - there's no way to discover the reverse
> edge without already knowing the target. If you look in the codebase for
> "FindSmallestEdge", you'll find a function that does this: looks at all the
> edges from the source, and if no connection is found, looks at all the
> edges from the target.
> Hopefully this demonstrates that directly exploring a CH is ....
> However, all is not lost. This might help help in your quest:
> This is an unfinished, but basically functional, isochrone generator.
> It creates a normal Datafacade, but *also* loads the full node-based-graph
> into memory. It uses the NearestPhantomNode function to find the
> edge-based-node, and the nodeIDs from GetUncompressedGeometry to find the
> entry point into the graph.
> Note that this tool is *not* exploring the edge-based-graph, which is
> probably what you would want if you're trying to follow valid connectivity
> - the node-based-graph doesn't have any turn restriction information in it,
> so it may not work for your case, but hopefully this points you in the
> right direction.
> On Nov 30, 2016, at 1:53 PM, Chris Elion <cel...@lyft.com> wrote:
> Hi folks,
> I'm trying to write some code that accesses the road graph, so that I can
> try out some alternative mapmatching algorithms (and also allow our data
> scientists to experiment with some other things). We're already using osrm
> in production, so leveraging the infrastructure we already have should in
> theory make my life easier.
> The GetAdjacentEdgeRange/GetTarget interface for the static graph (as
> described in https://github.com/Project-OSRM/osrm-backend/wiki/Quick-
> start-to-Code) seems straightforward. However, I'm stuck trying to find a
> node or edge close to a Coordinate as the starting point for my iterations.
> My two attempts so far have been
> 1) Use BaseDataFacade::NearestPhantomNodesInRange() - it's not obvious to
> me how to get the "real" node from the phantom node.
> 2) Use BaseDataFacade::GetEdgesInBox() gives reasonable-looking results -
> the NodeIDs EdgeBasedNode::u and ::v appear correct when I pass them to
> BaseDataFacade::GetCoordinateOfNode(). But the IDs are out of range when
> I pass them to BaseDataFacade::GetAdjacentEdgeRange()
> Any suggestions on how to salvage either of these approaches? Or is there
> a better way to go about this?
> Thanks in advance!
> OSRM-talk mailing list
> OSRM-talk mailing list
OSRM-talk mailing list