Offline routing

[HarelM]

Feature

As a user who doesn't have network connection I would like to still be able to plan a route on my mobile device.

Technical research so far:

1. Graphhopper port to iOS seems lagging behind the main version which will make it problematic if we need to create the graph-db to each platform: see Is this project still supported? graphhopper/graphhopper-ios#40
2. Graphhopper for android - I couldn't find a branch that supports this, all I have is this issue: Future of 'Offline' Routing graphhopper/graphhopper#1940
3. OsmAnd seems to have implemented their own routing engine, which I think we won't be able to use.
4. Valhalla is written in c++ and therefore can be used in both iOS and Android assuming one is able to compile them and run them on the device.
5. I've recently came across the following site which seems to have wrapped Valhalla in iOS and Android packages that one should be able to get using a package manager, I don't know if this is possible and how much it might cost, but this seems to be the closest thing I found to something that is cross platform: https://globus.software/

[zstadler]

Valhalla has a micro and micro2 branches that aims at mobile devices. Compare micro with main.
I'm not sure it includes Android, or just iOS.

[zstadler]

globus.software seems to be the owner of the GetYourMap GitHub account.

The GetYourMap website, https://getyourmap.com/, redirects to https://globus.software/.

[HarelM]

@bmarcco @cigone-openindoor if you have any pointers related to this issue it would be great :-) I saw that you posted something on maplibre repo... I'm using cordova in this project.

[HarelM]

I've found this discussion about Valhalla for offline usage, maybe we could try to post a solution there.
valhalla/valhalla#2887
As a side note, I'm not sure but I think Valhalla routing is not returning a height profile from the routing, which means that if we want to use this as offline routing it won't have height in it...? This might be a show stopper...

[HarelM]

Relevant findings:

1. I was able to make Valhalla run through docker on my dev env using this manual: https://gis-ops.com/valhalla-how-to-run-with-docker-on-ubuntu/
2. Valhalla has elevation integrated in order to be able to calculate bike routing but it is not part of the "per node" info as I understood from here: https://valhalla.readthedocs.io/en/latest/sif/elevation_costing/
3. When requesting routing the response is a shape encoded polyline without elevation info
4. One can query the elevation api to get the elevation of a shape
5. The elevation is downloaded from aws and is hard coded 3601x3601 hgt files, the code has this hardcoded I believe.
6. The size of the tar tiles file that is used by Valhalla for Israel is ~140 Mb which is reasonable.

Bottom line, both Valhalla and Graphhopper has their drawbacks :-(

[zstadler]

The Valhalla doc say (my annotation in bold):

Given a segment of road, we evenly sample points (at 60m apart) along it. At each sample, we measure the elevation. We then compute the grade/slope between each pair of sample points and weight it using the above function.

Therefore I think that as far as routing is concerned, a 30-meter DEM is good enough.

As discussed on the phone, augmenting the routing result with 30-meter elevation information in offline mode would differ differ from a future 10-meter online augmentation. This would be similar to the difference in the elevation graph between planned routes and recorded tracks.

[HarelM]

I don't think that's a correct conclusion - from my understanding if the road is long the segment is sampled more times to avoid long segments that are sampled only at the beginning or at the end, but if you have segments that are shorter than 30 meters the precision of the DEM is relevant.

Having said that, I agree that offline routing can be less accurate in terms of elevation, Valhalla currently only support their elevation provider and does not return the elevation for each node in the route.

See the following thread:
valhalla/valhalla#2450 (comment)
I don't think running an elevation service on a mobile device is a good direction, we can maybe leverage the RGB tiles, but that's a lot of work too.
I would rather have the elevation data as part of the route like I get it with graphhopper...

[zstadler]

I don't think running an elevation service on a mobile device is a good direction, we can maybe leverage the RGB tiles, but that's a lot of work too.

Stating the obvious: Using the TerrainRGB for elevation will avoid the need for additional storage on the device, but will require adding a different elevation provider. Perhaps this repository can help.

If you plan to implement such an elevation provider, note that the WGS84 coordinates used by Valhalla and hgt need to converted to the Transverse Mercator projection used by TerrainRGB.

[github-actions]

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 7 days

[github-actions]

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 7 days

[HarelM]

Another interesting alternative might be:
https://github.com/samueltardieu/pathfinding
Although this is more of a algorithm library than a routing/navigation library...

[github-actions]

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 7 days

[github-actions]

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 7 days

[HarelM]

It might be better to support a "poor man solution" just for when the reception isn't great.
There's also this interesting library:
https://github.com/dabreegster/route_snapper

[HarelM]

Recent thoughts on this matter:
Very very poor man solution for offline, only relevant for paying customers that downloaded the terrain and vector tiles:

1. Check that the start and end point are in the same tile at maxzoom (14 or so) or adjacent tiles (limit to 4 tiles for offline routing)
2. Parse the relevant tiles for elevation (maybe use maplibre's source cache)
3. Parse the relevant tiles for highways that are valid for the selected routing
4. Create a route using this limited data and enrich it with elevation.

The above code shouldn't be too complicated I hope and it will allow a good enough solution when a call to the server for routing fails.
My knowledge on the internals of maplibre should allow me to do it, hopefully...

[dabreegster]

Sorry for dropping the conversation on this! I think it'd be really cool to seed route-snapper with currently loaded vector tiles. queryRenderedFeatures is the only way I know to get tiles loaded, but maybe there's a way to grab everything in the cache. If you can filter for highways and paths, then pass line-strings somewhere, I could help write a method to take all the line-strings and turn it into a graph. One caveat will be with bridges/tunnels -- unless this is retained in the vector tiles, it'll look like shared points and thus be routeable.

[HarelM]

Thanks for reaching out! Basically what I has in mind is that we already have the tiles in a local database on the device (for this specific use case), fetching them and parsing them should be possible with exiting tools that are already part of maplibre-gl-js (i.e. @mapbox/vector-tile-js). once read into memory one could filter by layer and other properties and then get the geometry out for the method you mentioned.
I'll see if I can have a proof of concept for this in the next weeks and let you know what I find.
Would be super cool if you could help me with the graph part and finding the shortest route.

[dabreegster]

Definitely! Building a graph from MVT on-the-fly is something I want to try to do anyway,dabreegster/route_snapper#4 (comment). If you can get to the point of feeding in a bunch of line-strings, I can write something in JS or Rust->WASM->JS to turn it into the graph, and we can see how performant / correct the results look

[HarelM]

@dabreegster the following is a very simple typescript code that extracts features from a specific tile and filters only the highways (at the moment):
https://stackblitz.com/edit/typescript-offline-routing
It uses a tile that is hosted on our server.
I still want to see how I get the elevation from the RBG tile, but for you, this should be enough.
I'm printing the features' class to screen and printing the geometry (geojson) in the console log.
Let me know if you need anything else to create a graph and find the shortest route.
Would be interesting to try out to route from 32.624746,35.041598 to 32.612893231959916,35.0370270335134 (coordinates are lat,lng), this is also written in the comments there.

[HarelM]

I've stumbled across the following library which might solve the missing part here:
https://github.com/perliedman/geojson-path-finder
It would be interesting to see what it can do...
See the following issue:
perliedman/geojson-path-finder#86

[HarelM]

Initial POC seems to be working, this is very rudimentary obviously, but shows that this can be done with relatively little code (a lot of the code is for presentation in the below stackblitz):
https://stackblitz.com/edit/typescript-offline-routing

[HarelM]

Almost there...
Two last issues to solve - route simplification and the ability to click in the middle of a straight line and still get results.
geokdbush might help with the second problem and there might be a need to have high precision in order to remove simplification, I still need to research that...

[HarelM]

@psociety if you have any insights in order to avoid some of the problems you probably solved it can be great!

[psociety]

@HarelM i can't help much, i worked on this some years ago and never touched it again.
But i can share snippets of what i have, maybe it's useful to you:

 <script src="/js/path-finder.js?v=6"></script> <!-- grabbed using https://bundle.run/[email protected] -->
 <script src="/js/leaflet.geometryutil.js"></script>

              class Coordinates {
                constructor (lat, lon) {
                    this.latitude = lat;
                    this.longitude = lon;
                }
                
                toArray () {
                    return [this.latitude, this.longitude];
                }
            }
            
            class Geo {
                static EARTH_RADIUS = 6371008.8;
                
                static deg2rad(degrees) {
                  return degrees * (Math.PI / 180);
                }
                
                static distanceHaversine(from, to)
            	{
            		const $lat1 = Geo.deg2rad(from.latitude),
                		$lng1 = Geo.deg2rad(from.longitude),
                		$lat2 = Geo.deg2rad(to.latitude),
                		$lng2 = Geo.deg2rad(to.longitude);
            
            		const $dLat = $lat2 - $lat1,
            		    $dLon = $lng2 - $lng1;
            
            		const $a = Math.sin($dLat / 2) * Math.sin($dLat / 2) +
            			Math.cos($lat1) * Math.cos($lat2) *
            			Math.sin($dLon / 2) * Math.sin($dLon / 2);
            
            		const $c = 2 * Math.atan2(Math.sqrt($a), Math.sqrt(1 - $a));
            
            		return Geo.EARTH_RADIUS * $c;
            	}
            }

                // following the given coords, it will find the nearest coords IN our geoJsons
                getClosestCoordsAndLayer (coordinates) {
                    const closestLayer = L.GeometryUtil.closestLayerSnap(this.map, this.connectionsLayer.getLayers(), coordinates);
                    if (closestLayer === null) {
                        return null;
                    }
                    const closestPoint = L.GeometryUtil.closest(this.map, closestLayer.layer, coordinates);
                    let nearestPoint = null;
                    let distance = 9999999999;
                    let layerCoords = {
                        lat: [],
                        lon: [],
                    };
                    closestLayer.layer.getLatLngs().forEach(latlng => {
                        layerCoords.lat.push(latlng.lat);
                        layerCoords.lon.push(latlng.lng);
                        
                        let dist = Geo.distanceHaversine(new Coordinates(closestPoint.lat, closestPoint.lng), new Coordinates(latlng.lat, latlng.lng));
                        if (dist < distance) {
                            distance = dist;
                            nearestPoint = latlng;
                        }
                    });
                    
                    return {
                        nearestPoint: nearestPoint,
                        closestPoint: closestPoint,
                        distance: distance,
                        layerCoords: layerCoords
                    };
                }
                
              onMouseMove (coordinates) {
                    if (this.selectedUnit === null) {
                        return;
                    }
                    
                    // preview unit path
                    const mouseCoords = this.getClosestCoordsAndLayer(coordinates);
                    
                    if (mouseCoords === null) {
                        return;
                    }
                    
                    const unitCoords = this.getClosestCoordsAndLayer(this.selectedUnit.marker.getLatLng());
                    
                    if (unitCoords === null) {
                        return;
                    }
                    
                    const nearestPoint = mouseCoords.nearestPoint;
                    const layerCoords = mouseCoords.layerCoords;
                    const closestPoint = mouseCoords.closestPoint;
                    
                    const bestPath = this.pathFinder.findPath({
                        geometry: {
                            coordinates: [unitCoords.nearestPoint.lng, unitCoords.nearestPoint.lat]
                        }
                    }, {
                        geometry: {
                            coordinates: [nearestPoint.lng, nearestPoint.lat]
                        }
                    });
                    
                    if (bestPath === null) {
                        return;
                    }
                    
                    let paths = [];
                    const totalEntries = bestPath.path.length;
                    const len = totalEntries - 1;
                    
                    bestPath.path.forEach((coords, i) => {
                        if (i == len && totalEntries > 1) {
                            let prv = bestPath.path[i - 1];
                            let previousPoint = new Coordinates(prv[1], prv[0]);
                            
                            if (Geo.distanceHaversine(new Coordinates(coords[1], coords[0]), previousPoint) < Geo.distanceHaversine(new Coordinates(closestPoint.lat, closestPoint.lng), previousPoint) ||
                                layerCoords.lat.indexOf(previousPoint.latitude) !== layerCoords.lon.indexOf(previousPoint.longitude) ||
                                layerCoords.lat.indexOf(previousPoint.latitude) === -1
                            ) {
                                paths.push([coords[1], coords[0]]);
                            }
                        } else {
                            paths.push([coords[1], coords[0]]);
                        }
                    });
                    paths.push([closestPoint.lat, closestPoint.lng]);
                    this.selectedPath = paths;
                    if (typeof this.selectedUnit.line === "undefined") {
                        this.selectedUnit.line = L.polyline.antPath(paths);
                    }
                    
                    this.selectedUnit.line.setLatLngs(paths);
                    this.selectedUnit.line.addTo(this.map);
                }

[HarelM]

Thanks! I don't see the pathFinder initialization in this code. but I see what you did about finding the closest point, which is similar to what I wrote just now.
I have some problems with the data on the end of the tile, but this is probably related to the data and not the code, I'll need to investigate what's causing this...
In any case, this is the final stretch I believe, it's starting to look good and I can test all kind of scenarios:

For example different routing types:

[HarelM]

Man... these wild debugs are interesting :-)
The following is the last issue I'm facing with routing between two tiles.
The following is what I see, which the data explains, I'm just not sure how to overcome this.
The lines in each tile are extended to go a bit more than the tile itself for presentation purpose.
The algorithm only knows about points and the lines that are crossing a tile might not have points that are the same so the algorithm can join these lines.
Here is the image I captured for debug purpose:
blue are the start and end points to do the routing,
purple is the route that the algorithm found,
black points are the points that are part of the line's data, black lines are the lines,
red is the tile boundary
orange line is just a line close to the start point.
Looking at it closely the points in orange line can't be connected well to the tile on the left causing the routing to go around...
There's probably some more processing that is needed in order to connect the lines when they cross the tile boundary...
I need to think about it...

[HarelM]

The solution to this issue is probably removing the lines that are outside the tile boundaries using this method - lineintersect and linesplit:
https://gis.stackexchange.com/questions/290438/turfjs-intersect-line-and-polygon

[HarelM]

The above solution fixed the problem.
But there's still another one :-(
The following routing goes around instead of going through the short route.
If I need to guess, based on the things I saw, this is caused due to the simplification of the street that is straight, and so the junction point is removed from that street, causing the route to go around.
I'll see if I can reproduce this in a small example to support my hunch:

[HarelM]

Further investigation into this reveals that the problem here is the data in the tiles, I'm guessing that this data is simplified for the rendering, so it removes the points in straight lines, which removed the intersection point in the רקפות street in this case, causing the routing to go around...
I'll need to think how to solve this, the issue here is not with the geojson-path-finder.

[HarelM]

I've added a simple solution to this case: go over every line ending and see if it is part of another line.
It's not performant, so I optimized it a bit. It solve this specific issue.
I think this is good enough to start testing, hopefully we will be able to release it before passover.

[HarelM]

This seems to be working, there are still issues with routing through the edge of a tile, I'll see if I can find the root cause of this.
Feels like the final stretch :-) I hope this could be fixed in the next day or two and then we can release a new version.

[HarelM]

I've tested some of the issues, I've reduced the graph tolerance to 2e-5 as it seems that some tile edge coordinates have a bit of distance between them like the following:

upper:
lat: 32.61094562745822
lng: 35.068360204645955
lower:
lat: 32.61094322689087
lng: 35.06836037228334
diff:
lat: 2.40056e-6
lng: 1.67637381e-7

[HarelM]

Closed this issue as this will be released shortly.
Further improvements should be handled by new issues and can link to the issue here with the relevant research that was performed.