Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Allow routing from arbitrary start and end coordinates #27

Closed
karussell opened this issue Mar 19, 2013 · 9 comments · Fixed by #115
Closed

Allow routing from arbitrary start and end coordinates #27

karussell opened this issue Mar 19, 2013 · 9 comments · Fixed by #115
Labels
improvement
Milestone
0.2

Comments

@karussell
Copy link
Member

At the moment the routing start and end point can be only on a node. We need to extend the algorithm and the querying to allow arbitrary GPS coordinates on an edge (the road) too.

  • depends on GPS Lookup #17
  • extend the algorithm to allow two multiple start nodes (start(node), end(someCondition) and default is end(PointCondition(endNode))?)
  • calculate the shortest path from the GPS coordinate to one of the start nodes
  • do the same for the end point
@ocampana
Copy link

Can you please explain this? I mean, following the example code in mi app I call

calcPath (fromLatitude, fromLongitude, toLatitude, toLongitude, mapName);

where {from,to}{Latitude,Longitude} are double variables, whose values are not bound to anything. Why does it work?

@karussell
Copy link
Member Author

Not sure if I understand you ... there is a search functionality going on in Location2IDIndex which returns a node id from a point (lat,lon). But the node id could be relative far away from the original requested point. As we only need crossroads for routing, all other information of the actual path (e.g. for displaying) is stored in wayGeometry.

In this ticket we'll have to extend the current algorithm interface to make it possible somehow to return the full path from start to end (both some valid positions on a road or path) not only from cross-road to cross-road.

We could try to somehow introduce a virtual node to the graph. To make that thread safe we would need to separate node access from the Graph interface, e.g. instead of graph.getLatitude(int index) we would need something like new NodeAccess(graph).getLatitude(int index) and then return custom latitude values for our virtual node....hmmh. This change will trigger changes in RoutingAlgorithm and Path.

@karussell
Copy link
Member Author

BTW: this limitation will result in wrong routes if one starts or ends on one-way roads. See http://lists.openstreetmap.org/pipermail/graphhopper/2013-May/000136.html?
attachment-0001

@ngmip
Copy link

ngmip commented May 27, 2013

I have developed a improvement for this.
Feel free to check my fork https://github.com/ngmip/graphhopper
I did two things :

  • First : decorate the LocationIdResult with the closest edge informations so that I have start and end edges (works only with Location2NodesNTree index).
    This allow me to take edge direction into account when electing the start/end node to respect one way.
    Note that tough it improves the current algorithm it not 100% optimal for bidirectional edges as the bes starting node is not alway the closest node to the GPS location. (see the DummyNodeResolver class)
  • Second, compare the resulting path with the edges and adapt geometry, time and distance.
    This is done through my PathFinisher class. It computes a "cut point" being the location where the GPS point is projected on the edge and then add or remove the necessary points of the path to make neat endings.

I think I documented my code quite well and it has been synced with the master branch last Friday.

Suggestion for a perfect optimal solution :
A better way to do this would be to add 2 nodes and 4 edges in the graph at the "cut points" but this involves multi-thread issues as is. A good option would be to create a "virtual graph" ; a kind of wrapper around the actual graph and implementing the Graph interface. This wrapper would mirror method call to the underling actual graph. You could create one virtual graph for each request and add it the virtual node and edges. Those would be in the virtual graph (thread safe) but not in the actual graph. Then in the mirrored methods you could check if it involves virtual nodes/edges and adapt the method behavior to either return virtual objects or call the base graph's method.
I made an attempt to implement this solution but without success, that's the VirtualNodeVelvelGraph class in my repository.

@karussell
Copy link
Member Author

Thanks! I'll have a look into it this week!

@ngmip ngmip mentioned this issue May 27, 2013
Closed
@ngmip
Copy link

ngmip commented Jun 12, 2013

Just a shared thought :

As said before, start/end node are more or less arbitrary chosen.
When the edge can be matched it's still difficult to chose which tower node to use. (unless the edge is one way)
The best tower node would be the node for the shortest/fastest path.

Instead of computing the 4 possible path (or event partly computing them) and take the best I wonder if that would not be possible to "simply" initializes the 4 edges' nodes weight with a weight computed from the GPS point.

Let's take an example for the "from" node:
An edge AB with the P point on it (P being the projection of start GPS coordinate).

A --------------- P --- B

The index returns us the B node as the closest node and routing algorithm will use that node as start giving B the weight 0.
While computing route, the A node will soon have the 'BA' weight as best min weight.
If instead we define the B weight = PB (PB > 0) and the A weight = PA (PA < BA) then the routing algorithm should pass through A point in case it's actually shorter that passing through B.

That should give the best path, what do you think ?

@karussell
Copy link
Member Author

Exactly. One 'just' needs to put the first two nodes (with the correct weights) in the queue. But additionally one needs to check for two nodes as finish condition instead of only one.

But for that one needs to add a method calcPath to all algorithms that take two EdgeIterator parameters instead of two nodes (+ adjust the finish method for all algorithms). Also we need a bunch of unit tests for this as this is even more complex when pillar nodes (wayGeometry) comes into the game :)

Last but not least one needs the post processing you already have implemented.

@swoker
Copy link

swoker commented Sep 19, 2013

I'm hope this is the correct issue, but I'll +1 it
For this path I would expect totally different routes than the ones shown ...
Example: From Ackerstraße 157 Berlin - To Bergstraße 79 Berlin
The green path is my expectation...

by foot
expected_foot

by car
expected_car

Unfortunately, this issue is keeping me from using Graphhopper in my application.

karussell pushed a commit that referenced this issue Oct 4, 2013
more common methods for (bidir) algos; towards #27 -> new method taki…
ade2e9e 
…ng edges, additional tests for that in AbstractRoutingAlgorithmTester; repairs #105
This was referenced Oct 28, 2013
Closed
Merged
@karussell
Copy link
Member Author

Closing in favor of #115

karussell pushed a commit that referenced this issue Nov 12, 2013
Merge pull request #115 from graphhopper/issue_27
d7cf22c 
Allow GPS-exact routing (not just from junction to junction) #27
karussell pushed a commit that referenced this issue Jun 23, 2020
@boldtrn
Fix continue instruction translation (#27)
6b7bc84 
* Fix issues with Continue instruction and fixed some typos

* Use GH translation map instead
karussell added a commit that referenced this issue Jul 10, 2020
@karussell @boldtrn @easbar
Merge of navigation repository (#2071)
75a162a 
* Initial commit, moving relevant files from #1422 over to the new repository

* Remove debugging output

* Update README.md

* Rename to graphhopper-navigation-mapbox

* Add Tests (#3)

* Make MapboxResponseConverter testable

* Added Travis.yml

* Mavenbuild (#4)

* try maven build

* packaging pom

* Corrected conflict resolution

* Add Travis build status image

* Minor test improvement

* Fix indentation issue

* Remove WebHelper, fixes #1

* added a few properties required for deploying to maven central

* let's configure executable from settings

* Allow multiple waypoints (#5)

* First approach at allowing multiple waypoints

* Fix resetting time and distance

* First improvement to repeat instructions regularly

* Add a very far distance instruction to instruct users to continue on the road

* Moved the very far message a bit

* Reduce initial delay

* Improve roundabout banner instructions

* Add the very close instruction fall back

* Added a simple translation map

* Upper case the first letter of turn descriptions in bannerInstructions

* Update README.md

* Use GH translation map

* Move translations to resources

* Use Helper.firstBig

* Have TranslationMap as singleton

* TranslationMap as static variable

* Update README.md

* Update README.md

* Update README.md

* Update README.md

* move to stable dep of GH core 0.11.0

* set explicit version to maven-compiler-plugin

* Add bearings (#17)

* Inigial approach of using bearings in the request

* Disable CH

* log test

* Added Tests for MapboxResource#getBearing

* Sett pass through to false

* Add alternative Routes to Navigation Endpoint (#18)

* Allow the addition of multiple routes when using headings

* Use alternative routes by default

* Add test for alternative routes

* Remove alternative route calculation

* upgrade GH core dependency

* Add then voice and banner instruction (#19)

Add comment and minor rename

* Change Endpoint name and Maven Package (#20)

* Rename maven package, endpoint, and files

* Fix tmp issue with openjdk

* Remove tmp fix for jdk issue

* Update README.md

* Update README.md

* Update README.md

* Update README.md

* Update README.md

* use jdk-12 instead of 10

* Add points

* updated GH core version

* upgraded to 0.12.0-pre3

* updated GH core to 0.12.0-pre6

* upgrade to 0.13-SNAPSHOT and using GH core 0.12.0

* upgrade GH core to 0.13.0-pre1

* upgrade GH core to 0.13.0-pre2

* Upgrade gh core to 0.13.0-pre3

* Init imperial voice unit support

* Move VoiceInstructionConfig to seperate file

* Add imperial unit translations

* Add voice instruction tests

* Set right inital voice instruction key

* Remove redundant init from unit

* Remove voiceUnit metric check

* Set imperial as default if no voiceUnit is set

* Refactor voice instruction configuration creation

* Upgrade gh core to 0.13.0-pre4

* upgrade GH core to 0.13.0-pre5

* upgrade GH core to 0.13.0-pre6

* upgrade GH core to 0.13.0-pre7

* upgrade GH core to 0.13.0-pre8

* upgrade GH core to 0.13.0-pre12

* Fallback to the original profile (#26)

* Load the correct translation map

* upgrade GH core to 0.13.0-pre15

* Upgrade GH core to 0.13.0-pre16

* Upgrade GH core to 0.13.0-pre17

* Upgrade GH core to 0.13.0-pre18

* Upgrade GH core to 0.13.0-pre19

* Upgrade GH core to 0.13.0

* Upgrade GH core to 0.14.0-pre1

* Upgrade GH core to 1.0-pre1

* Upgrade GH core to 1.0-pre2

* Upgrade GH core to 1.0-pre3

* Upgrade GH core to 1.0-pre4

* Upgrade GH core to 1.0-pre5

* Update README.md

* Fix continue instruction translation (#27)

* Fix issues with Continue instruction and fixed some typos

* Use GH translation map instead

* Upgrade GH core to 1.0-pre7 (#28)

* Upgrade GH core to 1.0-pre9

* Update pom.xml

* Upgrade GH core to 1.0-pre11

* Upgrade GH core to 1.0-pre12

* Upgrade GH core to 1.0-pre14

* Upgrade GH core to 1.0-pre16

* Upgrade GH core to 1.0-pre17

* Upgrade GH core to 1.0-pre18

* Upgrade GH core to 1.0-pre21

* Upgrade GH core to 1.0-pre22

* Upgrade GH core to 1.0-pre23

* Upgrade GH core to 1.0-pre24

* Upgrade GH core to 1.0-pre25

* Upgrade GH core to 1.0-pre27

* Upgrade GH core to 1.0-pre28

* Upgrade GH core to 1.0-pre29

* Upgrade GH core to 1.0-pre30

* Fix compiler error, tests still fail

* fix tests #31

* Upgrade GH core to 1.0-pre31

* update to jdk14

* Upgrade core to 1.0-pre32

* Upgrade core to 1.0-pre33

* Upgrade core to 1.0-pre33.2

* Upgrade core to 1.0-pre33.3

* Upgrade core to 1.0-pre33.4

* Upgrade core to 1.0-pre35

* fix resource

* Upgrade core to 1.0-pre37

* Upgrade core to 1.0-pre38

* for now we need the legacy resolver also here

* add logging

* make profile mapping between mapbox and graphhopper configurable; remove legacy resolver

* Update README.md

* Update README.md

* Update README.md

* updated GH core

* Set versions to 1.0-SNAPSHOT in pom.xml, keep dependency hashes in separate file

* Move gh_dependencies into pom.xml instead

* Rename: PathWrapper -> ResponsePath

* Use core dependency from jitpack

* Remove hash

* Upgrade to 1.0-pre42, revert to old build process

* Upgrade GH core to 1.0-pre43

* Upgrade GH core to 1.0

* Upgrade version to 2.0-SNAPSHOT

* add development profile

* Update core version, use GitHub packages, remove sonatype snapshot repository

* Add GitHub workflow to publish packages, see core/#n2049

* Add missing distributionManagement

* Add access token setup for travis with github packages

* travis job: include access also for github packages

* Update core version

* Include sources for GitHub Packages deployments

* Update core to 'remove unused methods encoder.defineNodeBits...'

* Update core to 'Set default algo for edge-based CH back to Dijkstra'

* Update core to 'Use Envelope in API'

* Update core to 'Add comment about module GpxFromInstructions belongs to'

* Update core to 'Add creator method for LMApproximator'

* move into navigation subfolder

* remove duplicate files

* removed andorra osm

* added apache license header to 2 files

* added note in changelog

Co-authored-by: Robin <[email protected]>
Co-authored-by: easbar <[email protected]>
Co-authored-by: Stefan Kienzl <[email protected]>
frodrigo pushed a commit to cartoway/graphhopper that referenced this issue Oct 9, 2024
@JordiGiros
[QA-000] Add coverage config and publish report on Jenkins (graphhopp…
74f8c3d 
…er#27)

* Add coverage config and publish report on Jenkins

* Chenge test to verify in Jenkins
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
improvement
Projects
None yet
Milestone
0.2
Development

Successfully merging a pull request may close this issue.

Allow GPS-exact routing (not just from junction to junction) #27 graphhopper/graphhopper
4 participants
@karussell @swoker @ocampana @ngmip