UP.route

A 3D geoportal that finds routes between buildings on the UPWr campus on foot, by bike and by car. My master’s thesis.

A 3D view of the cathedral and the Ostrów Tumski area with building shadows, and the shadow settings window. — Shadows over Ostrów Tumski, 13 October, 10:41

Problem

The thesis set out to build a 3D navigation system for the Wrocław University of Environmental and Life Sciences campus, as an open alternative to closed commercial platforms. All of the logic, route calculation included, had to run in the browser, with no computing server.

What it does

Three networks (pedestrian, bicycle, car) split out of OpenStreetMap road data and repaired topologically in FME.
Routing between campus buildings with A* on a graph built in the browser.
A 3D globe in CesiumJS with building models, with the route drawn on it.
Tools: measurements, shadow analysis for a chosen time of day, terrain profile and flood simulation.
Map state (camera, layers, open tools) kept in the link; the app runs as a PWA, in Polish and English.

A walking route between buildings C2 and A2 on the 3D campus model, next to the route finder window. — A walking route between buildings C2 and A2

Technical decisions

A* instead of Dijkstra

I compared the two algorithms over 15 warm-up and 100 measured iterations in Node.js. A* found a route in 34 ms on average, while Dijkstra needed over 8 s, so A* went into the app.

An adjacency list instead of half-edges

The half-edge structure did not speed up A*, and it used about twice the memory: 530.44 MB against 278.67 MB for the adjacency list on a network of 459,675 elements. On that basis I chose the adjacency list.

Data repaired before routing

OpenStreetMap is community-made, so the network lacks nodes at junctions and attributes. I fix that once, in FME, before the graph is built, instead of patching data in the app. Paths tagged in OSM only as cycleway went into the pedestrian network too, so pedestrian routes do not break.

Computation on the user’s side

Routing runs in the browser, with nothing to install and no server. The cost is a heavy start-up while the full graph is built; in the thesis I name moving that to a backend as the next step.

A map of Wrocław with a long route between two university sites. — A route from DS4 to F11 across the whole city

Outcome

A working geoportal at uproute.dworecki.dev. In the benchmark, A* found a route in 34 ms on average. The thesis also shows the limit of this approach: with large networks, building the graph has to move to a server.