[GraphHopper] Improve route's geometry

Tue May 14 18:17:25 UTC 2013

Hi Nicolas,

> But as you already have your idea of the way to implement it I'd be
glad if you could give me guide lines so that I don't diverge (much)
from your idea an keep a good coherency in the project.

I would really welcome your contribution.

Although I've thought about it I've not yet found 'the best' solution.
E.g. one could introduce a 'virtual node' (between the tower nodes)
which wouldn't require any changes to the algorithms. But this is hard
for multithreaded environments and could also introduce several other
problems.

Your idea about returning EdgeIterator from Location2IDIndex is better
as we could later on also implement a lookup index where the direction
of a car could be taken into account too.

> So as I said earlier my vision was modify the Location2IDIndex
<eclipse-javadoc:%E2%98%82=graphhopper/src%5C/main%5C/java%3Ccom.graphhopper%7BGraphHopper.java%E2%98%83GraphHopper%5Eindex%E2%98%82Location2IDIndex>
and return an edge instead of a nodeId.

I've done some changes in my local branch for foot/bike support where
the location index returns a LocationIDResult (where we could embed the
EdgeIterator) ... probably we should move the discussion to the issue
and I'll try to publish this branch. The solution is similar to this
here where also the closest index (for wayGeometry) is returned:
https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/storage/index/LocationIDResult.java

> to find the tower node to be rooted out of

This is not as simple as you describe. At least for edges which are not
one-way an algorithm needs to know *both* tower nodes in order to decide
which route is better S1-E1, S1-E2, S2-E1 or S2-E2 (S=START, E=END) ...
so all algorithms will have to implement additionally a method like
'Path calcPath(LocationIDResult,  LocationIDResult)'

> The two problem of this approach I can already see, are

> 1.       how can I retrieve one single edge when I only have its ID

edgeIterator = graph.getEdgeProps(edgeId, -1);

> 2.       how can I retrieve the two tower nodes out of an EdgeIterator

edgeIterator.baseNode
edgeIterator.adjNode

(and the pillar nodes are identically to edgeIterator.wayGeometry)

Regards,
Peter.

> Hi Peter,
>
>  
>
> Thanks for you answer.
>
>  
>
> We are willing to have this feature as ap so we could develop it and
> share it.
>
> But as you already have your idea of the way to implement it I'd be
> glad if you could give me guide lines so that I don't diverge (much)
> from your idea an keep a good coherency in the project.
>
>  
>
> So as I said earlier my vision was modify the Location2IDIndex
> <eclipse-javadoc:%E2%98%82=graphhopper/src%5C/main%5C/java%3Ccom.graphhopper%7BGraphHopper.java%E2%98%83GraphHopper%5Eindex%E2%98%82Location2IDIndex>
> and return an edge instead of a nodeId.
>
> Then create instrument method to find the tower node to be rooted out
> of (the edge + gps point + boolean telling if it's an origin or
> destination (for one way restrictions))
>
> I would then get proper from and to tower nodeIds I can pass to the
> routing algorithm to compute the path.
>
> Once the algorithm returns me the path, I'd use my 2 previously
> computed edges to "finish the job" and correct the extremities of the
> road.
>
>  
>
> The two problem of this approach I can already see, are
>
> 1.       how can I retrieve one single edge when I only have its ID
>
> 2.       how can I retrieve the two tower nodes out of an EdgeIterator
>
>  
>
> What do you think ?
>
>  
>
> Thanks
>
>  
>
> Nicolas GILLET
>
>  
>
> *Market-IP --*///Creating Mobile Intelligence/
>
>  
>
> *De :*Peter K [mailto:peathal at yahoo.de]
> *Envoyé :* mardi 14 mai 2013 16:32
> *À :* graphhopper at openstreetmap.org
> *Objet :* Re: [GraphHopper] Improve route's geometry
>
>  
>
> Hi Nicolas,
>
> this limitation will be removed with solving this issue:
> https://github.com/graphhopper/graphhopper/issues/27
>
> BTW: nodes between edges in graphhopper are only stored in wayGeometry
> (see GraphStorage), not as real nodes. This was introduced as this
> speeds up querying a lot and also space is reduced.
>
> Regards,
> Peter.
>
>     Hello,
>
>      
>
>     I noticed that routes are computed only between the graph's nodes,
>     and the route does not go close enough to the actual GPS points.
>
>     I also noticed that there is a small mistake when selecting the
>     start/end node when the GPS point falls on an "one way" edge.
>
>      
>
>     The current behavior is to find the closest edge to the lon/lat
>     coordinates and then find the closest node on this edge to the
>     lon/lat.
>
>     When an edge is one way, you don't have to take the closes node on
>     the edge but the node that will respect the traffic flow.
>
>     Mean if your starting point fall on an one way edge, you'll have
>     to start the routing form the end point of this edge, no matter
>     the starting point may be closer to your GPS coordinates. Indeed,
>     if you go from you gps point to the start node, you'll have to
>     violate the one way restriction.
>
>      
>
>     (see attachment as example)
>
>      
>
>     In this picture we also see the first thing I mentioned : the
>     geometry lacks of accuracy between nodes and GPS coordinates ; the
>     blue line does not "stop" exactly at the two little flags
>     representing my GPS coordinates. (green flag: start, red flag : end)
>
>      
>
>     I started digging into the code in order to solve these two issues
>     and I came up thinking that the whole API needs a bit of rework.
>
>     Right now the node resolution returns a node ID but I think it
>     should rather return an EdgeIterator of the matched edge.
>
>     With this edge, it's possible to find the appropriate start/end
>     node depending on the lon/lat of the point and the fact that edge
>     is one way. It's also possible "finish" the road and compute the
>     missing/exceeding parts of the road.
>
>      
>
>     Am I missing something ?
>
>     Do you think that my point of view is correct ?
>
>      
>
>     Thank you
>
>      
>
>     Nicolas GILLET
>
>      
>
>     *Market-IP --*///Creating Mobile Intelligence/
>
>
>
>
>     _______________________________________________
>
>     GraphHopper mailing list
>
>     GraphHopper at openstreetmap.org <mailto:GraphHopper at openstreetmap.org>
>
>     http://lists.openstreetmap.org/listinfo/graphhopper
>
>
>
>
> -- 
> GraphHopper.com Your way is our destination!
>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/graphhopper

-- 
GraphHopper.com Your way is our destination!

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130514/a7981c7e/attachment-0001.html>