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

Refactor graph code

Aperta
#2 3 commenti 0 reazioni 0 assegnatari Vedi su GitHub
Lingua principale
Rust
Stelle
0
Fork
1
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Descrizione

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

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Direzione di ricerca

Examine the graph code in the linked repositories (severance_snape, ltn, osm2streets, od2net) to identify common patterns like NodeMap, Mercator geometry, and routing algorithms. Focus on abstracting shared components such as road/intersection structs, OSM data scraping, and cost functions for routing. The goal is to design a generic library that can be used across these projects without duplicating logic.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
rust
Ambito
backend
Tipo di issue
Refactoring
Difficoltà
5/5
Tempo stimato
Più di una settimana
Stato di attività
Ferma
Chiarezza
Abbastanza chiara
Idoneità per principianti
30/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.