Comments (15)
The number of those islands is usually huge (>15m). Just have a look into the world wide import where it says e.g. edges: 177458975, nodes 132784561, there were 17 675 148 subnetworks. removed them => 4611970 less nodes
from directions-api.
Another problem occurs here, which should give a route for hike.
The reason for this seems to be that it is disconnected here at the parking lot. This might be also fixable by routing over areas.
from directions-api.
It is indeed the problem I guessed (too few nodes). Will fix this via a configuration, if this does not help we could reset to the default config (of min_network_size) and remove small subnetworks only if they are also small "area-wise" as the suspected area is not small (15km²). This will be live in ~2 days
from directions-api.
This is fixed now
from directions-api.
Now we get problems with islands due to access restrictions e.g. here and here. We have to revert this change for the time being and consolidate how to properly fix this (e.g. via the area calculation and a 1km^2 limit (?) instead of junction count). See GH core issue here
from directions-api.
Could we, instead of removing the islands, connect them, by a high-penalty synthetic edge, to their surroundings?
This would be closer to physical reality: You can get from a footpath on an airport to the outside. The problem is not that the footpath exists, but that it appears disconnected in the model.
from directions-api.
(Prof. always calls this 'bushwhacking'. Assuming in a model that you can get from every place to every other, just very slowly and inconveniently.)
from directions-api.
But how would such a connection heuristic look like? What about dangerous areas that really no one should enter? Maybe for foot/bike there is a heuristic, but what about cars or trucks?
One solution to the island problem could be a many to many routing, so one could route within the islands. But then there is another problem: how do you weigh in the beeline distance vs. the time (the actual weighting)? A similar problem we have in map matching.
Also more problematic are cases where there is no disconnected island but instead the direct connection is missing and a huge detour has to be made.
from directions-api.
Where I see a big problem are islands that are indirectly introduced per-request. Example: we block ways for vehicles with width=2.7m and have a vehicle with width=3m, then islands are easily created and a full graph scan can be the result. Hmmh, this could be reduced if we use a similar approach that you defined for the pt
branch (distance restriction): detect 'how far' the destination is without the restriction (define this as X) and then search further but not longer than 2*X
from directions-api.
Yeah. I'm currently trying to see how far I get with this (I'm doing multi-criteria by default):
- All constraints are "soft" in the way that they're not modelled as removed edges where you cannot even be in the first place or which aren't explored, but by weight = large or weight = infinity.
- We are responsible for terminating the search. (So the user can't do DOS attacks by specifying weird cost functions.)
- I'm trying to see "terminating the search" as: There is some mode which "always works". For me this is walking(*). I write my function which checks if a partial solution can still improve the set of already-found solutions in a way that always says No at some point after at least one solution is there. Queue runs empty. -> Termination.
(*) = Would probably have to be changed to be not the "user-defined-speed-walking" but some hard-coded walking with fixed speed, meant as a catch-all. Which I think is the same as what you said, just differently imagined. :-) It could also do forbidden things, and the layer above can then decide not to report that solution.
from directions-api.
We are responsible for terminating the search. (So the user can't do DOS attacks by specifying weird cost functions.)
We should be kind of safe due to the maximum number of visited nodes.
Still this is interesting: if we e.g. increase a weight of a bridge too much the search might be successful but performance could suffer as too many unrelated nodes have to be explored before the bridge is further investigated and the destination is found. And so we should somehow guide the user/developer that a too extreme weighting difference (from 'default') can be very bad for performance. Or if we at some point make a lot more things configurable per request we should e.g. only allow factors from 1 to 5, not arbitrary 'bad'. Hmmh, but blocking/infinity is arbitrary bad and often required.
from directions-api.
Could we, instead of removing the islands, connect them, by a high-penalty synthetic edge, to their surroundings?
Do we know the number of islands? Maybe we could look at the most important (biggest) ones and try to fix the underlying data. For example creating issues for OSM, so locals can fix it, or sometimes fixes are obvious. For example I fixed a road once that was disconnected by one OSM contributor that probably made a mistake by disconnecting it.
I would assume that most areas are accessible, but the mapping is simply incorrect/insufficient.
from directions-api.
The number of those islands is usually huge (>15m)
Thanks for the clarification. That makes things more complicated :(.
from directions-api.
Another problem occurs here, which should give a route for hike
.
from directions-api.
Seems to be mostly fixed and if not, will continued at graphhopper/graphhopper#897
from directions-api.
Related Issues (20)
- Sync swagger specs and clients
- add possibility to optimize for open routes with optimize=true HOT 1
- time_windows should get hint to unix timestamp
- big font is too bold and the standard is too light HOT 1
- avoid fetching stuff from google due to google font HOT 1
- Add documentation about ShortFastestWeighting HOT 5
- Improve gisgraphy geocoding docs
- Add generic documentation about address
- Completely wrong route HOT 1
- ascent and descent too high along river HOT 6
- Remove 'in progress' HOT 7
- Routing API lacks description of 'details' in the output structure
- barrier blocking although access=yes HOT 2
- Correct elevation on tunnel and bridge HOT 1
- create a new time dependent routing documentation entry in the documentation HOT 2
- Meaning of error code 501 HOT 1
- Issue while querying Routing API - incorrect received route HOT 2
- Incorrect route
- What is the correct way to enter from_points and to_points? HOT 1
- Issues when looking up Fürth
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from directions-api.