a-b-street / a-b-street/utils

Refactor graph code

Open
#2 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
0
Forks
1
PR merge metrics
No merged PRs in 30d

Description

This isn't really related to Sev Snape, I'm just exploring this idea here first.

I'm duplicating lots of backend code between projects to turn OSM data into a graph, do point-to-point routing, and floodfill / calculate isochrones. Some projects are starting to need multiple modes as well, like a-b-street/severance_snape#18 here. If there was something more generic, what would it look like?

# Requirements

- https://github.com/a-b-street/severance_snape
- NodeMap, Mercator, and Tags already definitely common
- `RoadID` and `IntersectionID` types, array lookups
- Snap a point to nearest intersection (or road)
- Isochrone floodfill, giving costs per road
- Calculating a boundary polygon and showing inverted form
- Bounds of area
- The roads/intersection structs need the basic graph info, and the geometry. Also track OSM provenance. Then some custom stuff.
- A-to-B routing with a CH. Custom cost functions, of course. Managing the PathCalculator caching. Plenty of custom code, but at least a higher-level way to get the semantic road edges back would be nice.
- Scraping OSM is definitely shareable. `split_edges` particularly.
- Geometry is stored in Mercator, always transformed back in WASM
- https://github.com/a-b-street/ltn
- Much more complex; stores multiple routers (the CH itself, node map, closest intersection mapping (but that shouldn't really be there))
- Also Mercator geometry
- Otherwise pretty similar, feels like much could be shared
- https://github.com/a-b-street/osm2streets/
- Doesn't use raw `geo` now, but should ideally
- Does complex graph manipulations now, but maybe shouldn't
- Has this complex planar blockfinding routine, which could be generally useful?
- https://github.com/Urban-Analytics-Technology-Platform/od2net
- The most different. Meant to be used over huge areas
- So geometry is kept in WGS84
- Doesn't invent IDs; raw OSM IDs are used. So the edge object doesn't have a node1 and node2, because the key has it
- Extremely custom cost functions for routing
- The detailed route output could use help gluing together geometry maybe, but the core routing logic is deliberately quite custom and barebones
- Could also be used in this nascent 15m revival tool idea
- Maybe could help with part of https://github.com/alan-turing-institute/acbm

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.