GPS Urban Canyon

The Problem

GPS positioning in dense cities is notoriously bad, and the reason is geometric: a receiver needs at least 4 satellites with an unobstructed line of sight to compute a fix, and a 200-meter tower across the street removes a huge wedge of sky. Standing mid-block on a Midtown avenue, buildings can mask everything below 60–80° of elevation in most directions — leaving only a thin sliver of sky along the street axis.

Worse, the satellites you can't see directly don't just disappear. Their signals arrive anyway, bounced off glass facades, with tens of meters of extra path length. The receiver happily uses them and produces the classic urban GPS failure mode: you're on 5th Avenue, your dot is two blocks away. This project models the whole chain, starting with the visibility geometry shown here.

This model was originally written at Grubhub, where the problem was practical: our courier simulation system needed artificial GPS traces that failed the way real ones do. Uniform noise is easy to filter; real urban error is structured — biased along the street axis, correlated in time, and snapping between discrete reflection geometries as a courier walks a block. Feeding physically-derived errors like these into simulation let us stress-test our CRP-based map-matching service, which ran a hidden Markov model over the road graph to find the signal in the noise and consistently snap couriers to the right streets. To break a filter that's good at its job, you have to lie to it the way the city lies.

The Model

Buildings are 2.5D prisms: a 2D footprint polygon extruded from the ground to a roof height. Because a sight-line's height grows monotonically with horizontal distance, the binding constraint against any prism is at the ray's horizontal entry point into the footprint — so line-of-sight reduces to a 2D ray cast plus one height comparison per building, and the whole sky collapses to a one-dimensional function of azimuth:

The sky-wide horizon mask is sampled every 0.5° of azimuth, and every visibility question for the rest of the pipeline becomes a lookup.

Satellite positions come from a real IGS precise orbit file (SP3 format), fetched and parsed in your browser, with a 10-point Lagrange interpolation over the 15-minute grid — the standard technique, good to well under a centimeter. ECEF positions are rotated into the local east-north-up frame to get azimuth and elevation, and a satellite is usable when it's above the standard 5° receiver cutoff and above the building mask at its azimuth.

The default city is the real one: 2,000 building footprints from NYC Open Data, an 800 m study area around 6th Avenue in the West 40s, with roof heights and ground elevations (published in US survey feet — a classic unit trap) converted to meters in a local east-north frame. One Vanderbilt anchors the skyline at 427 m, and terrain enters as per-building base heights. A synthetic Manhattan-like grid is also included — ~80 m between cross streets, ~270 m avenue-to-avenue, rotated 29° east of true north like the real street grid (which matters: it biases which satellite geometries survive the canyon), with lognormal building heights, because real blocks are jumbles, not monolithic slabs.

Multipath: The Image Method

Blocking a satellite doesn't silence it. Every footprint edge is a vertical facade, and glass curtain walls are strong specular reflectors at GPS's L-band wavelength. For each blocked satellite the demo runs the classic image method: reflect the receiver through each candidate facade plane, shoot a ray toward the satellite, and check that the specular point lands on the physical facade — within the edge, between base and roof — with clear paths from facade to sky and facade to receiver.

Each surviving bounce carries an excess path length with a closed form that is almost embarrassingly simple:

The geometry does all the work: a facade 20 m away at 30° incidence adds ~35 m to the measured range — no material properties, no signal processing, just mirror geometry — and a receiver tracking such a signal eats the whole excess as a pseudorange bias: exactly the magnitude of observed urban GPS errors. The amber diamonds in the skyplot are these NLOS satellites — present, trackable, and lying about their range. In the 3D view you can watch their reflected paths kink off the facades that produce them.

A Trick Worth Stealing

GPS satellites orbit at ~20,000 km, so moving the receiver a full kilometer changes a satellite's apparent direction by about 0.003° — effectively nothing. The demo exploits this: azimuth/elevation for all 32 satellites across the whole day is computed once, and dragging the receiver only recomputes the horizon mask and reclassifies each epoch against it. That's why the timeline updates in real time as you drag.

From Bias to Blue Dot

The punchline is a position fix. The demo feeds every usable satellite into a weighted least-squares solution — four unknowns, three position and one receiver clock — with each NLOS satellite's excess reflection delay injected as a pseudorange bias and fully-blocked satellites dropped. With satellites effectively at infinity the model is linear, so the biases displace the solution by exactly the amount the geometry dictates: the fix slides away from the satellites that are lying.

Two Phase 3 deliverables run in a web worker: error-vs-time at the receiver across the full day, and an error heatmap over a 480 m square at the chosen epoch — practical only because of the trick above: satellite directions are computed once and reused at every one of the ~1,000 grid points, so each point costs only its own ray casts and reflection search. Street canyons glow amber with tens-of-meters errors while intersections and parks stay dark; red cells can't even see four satellites. "Your dot is two blocks away" stops being an anecdote and becomes a computed, mapped consequence of geometry.