dabreegster
commented
5 months ago Hi, thanks for using the project and glad it's been helpful so far!
Country-wide or very large areas are challenging because this library was designed for smaller areas. So the whole graph is meant to fit in one file, generally under 10MB gzipped, and download + deserialize pretty quickly. And then the pathfinding itself uses a simple Dijkstra's algorithm, so it starts to fail for larger areas.
The easiest answer would be to check if your use case really needs cross-country routing, or if people are always drawing routes confined in some areas, like administrative boundaries. For example, we divide England like this -- https://acteng.github.io/atip -- and build a file per area. The user first selects the area, then starts the route tool. I've also started doing this without the first step -- just drop people on a map, and press a button to download tne route snapper for the area currently in the viewport. https://github.com/acteng/will-it-fit/blob/main/web/src/match_area.ts uses Turf and finds the boundary area best overlapping the viewport.
If this approach of dividing areas works, then something like https://github.com/acteng/atip-data-prep/blob/main/split_uk_osm.sh and https://github.com/acteng/atip-data-prep/blob/main/build_route_snappers.sh can work for splitting the entire country's osm.pbf into smaller files and processing each. It's using osmium to split the pbf, and pueue to parallelize / track tasks, but you could use GNU parallel or something else too.
If you do need routes that possibly cover a huge area, then I'm not sure this project is the best fit. To make the pathfinding itself performant, we'd have to use preprocessed contraction hierarchies like https://github.com/easbar/fast_paths/ or a similar technique, but this would increase the size of the file to load. And the size of that file probably gets very big anyway, as you've seen.
The smarter approach would be to tile the country (without the concept of zoom levels), dynamically load the necessary tiles, and have a way to glue them together in the graph. I've never implemented this approach because I haven't needed it yet. I think Valhalla or OSRM has offline routable tiles, as possible reference. And if you can run a backend API, then just using an existing routing engine like that might be easier.
Hope that helps -- if you have more info about your use case, happy to help think it through. Thanks!
howllian27
Hello,
First, I'd like to express my appreciation for the RouteSnapper project. It's been an invaluable tool for our mapping and routing needs. However, we are encountering challenges with building graphs efficiently for various regions, especially larger areas like entire countries or states.
We have been using RouteSnapper to create route graphs from OSM data for specific regions. For smaller areas, the process works well, but for larger regions (e.g., entire countries or large states), the process becomes resource-intensive. We tried downloading and processing large OSM PBF files, but this approach consumes a significant amount of storage and processing time.
Thus, I was wondering what would be the most optimal way to build graphs for different regions (e.g., countries, states, cities) using RouteSnapper? Are there recommended practices or tools that can streamline this process, particularly for large datasets?
Additionally, would preprocessing the graph for each required region be an optimal solution? For example, creating and storing preprocessed graph files for each country, state, or city in advance, and loading these preprocessed files as needed. If preprocessing is recommended, what tools or methods would you suggest for efficiently preprocessing and storing these graphs? Was also wondering whether you think it will efficient if we were to run RouteSnapper based on fetched data in an mvt file created from zooming in on an area in a map.
Would greatly appreciate your advice on this!