How Maps and Navigation Work: Location, Road Graphs, Traffic, and Routing

A navigation app must answer several different questions:

Where are you?
Which road are you on?
Which roads connect?
Which route is currently best?
How long will it take?

Navigation is graph search guided by geographic constraints, positioning uncertainty, and changing real-world travel costs.

The shortest geometric line is rarely the drivable route.

A concrete example: rerouting around traffic

The app initially chooses a highway route.

Traffic reports show a collision has raised expected travel time on several segments. The routing engine updates their cost, finds an alternative road sequence, and compares the benefit with the disruption of rerouting.

It changes the route only when the expected improvement is meaningful.

Geographic data

Maps store:

roads,
intersections,
addresses,
buildings,
boundaries,
transit,
terrain,
and points of interest.

Data comes from providers, governments, imagery, surveys, vehicles, businesses, and user corrections.

Coordinates

Latitude and longitude locate points on Earth.

Rendering and routing often transform them into projected coordinate systems suitable for screens and distance calculations.

Earth is not flat, so projection choice creates distortion.

Positioning

Phones estimate position from:

satellite navigation,
cellular signals,
Wi-Fi observations,
Bluetooth beacons,
accelerometer,
gyroscope,
and compass.

Each source has different accuracy, power use, and indoor behavior.

GPS and satellites

A receiver estimates distance from several satellites using precise timing signals.

It solves for position and clock error. Buildings, atmosphere, and reflected signals can reduce accuracy.

The phone receives satellite signals; ordinary GPS location does not require sending data to satellites.

Sensor fusion

No one sensor is perfect.

The device combines:

GPS position,
movement sensors,
compass direction,
and previous trajectory

to produce a smoother estimate. It can continue briefly through tunnels using inertial movement.

Map matching

Raw location may place a car beside the road.

Map matching compares position, direction, speed, and road geometry to infer the most likely road segment.

It must avoid snapping a vehicle to a nearby parallel road incorrectly.

Road graph

The road network becomes a graph:

intersections and meaningful points are nodes,
traversable road segments are edges.

Edges carry attributes:

length,
speed,
direction,
turn restriction,
road type,
toll,
and access rule.

Routing algorithms

Algorithms such as Dijkstra's or A* search for a low-cost path.

A* uses a destination estimate to avoid exploring every direction equally. Large map systems add preprocessing and hierarchical shortcuts for speed.

The mathematical goal is minimum cost, not necessarily minimum distance.

Cost function

Edge cost can include:

expected travel time,
toll,
fuel,
road preference,
safety,
elevation,
and turn penalty.

Walking, cycling, trucks, and wheelchairs need different rules.

Turn restrictions

A route must obey:

one-way roads,
no-left-turn signs,
timed closures,
vehicle limits,
and private access.

A missing restriction can make a mathematically connected route physically illegal.

Traffic data

Traffic estimates come from:

anonymized device speeds,
road sensors,
transport agencies,
incident reports,
and historical patterns.

Data is aggregated and filtered for privacy and reliability.

Historical travel time

Monday at 08:30 differs from Sunday at 08:30.

Models learn expected speed by:

road,
day,
season,
event,
and weather.

Live observations adjust the historical baseline.

Estimated arrival time

ETA sums expected segment and turn times, then accounts for uncertainty and route progression.

Models can learn systematic effects such as parking exits, border crossings, or slow urban turns.

An ETA is a prediction, not a promise.

Rerouting

Continuous rerouting can create instability.

The app considers:

current route,
new cost difference,
confidence,
driver's progress,
and reroute frequency.

A two-second theoretical gain may not justify a confusing detour.

Offline maps

Downloaded map regions store:

road graph,
labels,
addresses,
and rendering data.

Live traffic and recent closures may be unavailable offline. Route calculation can continue using stored data if the app has local routing capability.

Map correction and freshness

Roads open, businesses move, and turn restrictions change.

Mapping systems combine automated detection with reports from authorities, partners, vehicles, and users. A correction needs validation because malicious or mistaken edits can reroute many people. Critical closures may receive faster temporary handling before the permanent map database is updated.

Satellite positioning weakens inside large buildings.

Airports, malls, and hospitals may combine indoor maps with Wi-Fi, Bluetooth beacons, inertial sensors, and known entrances. Floor level and accessible routes become part of the graph, while privacy and calibration remain significant challenges.

Map tiles

Visual maps are divided into tiles by zoom level and location.

The client requests only visible tiles, caches them, and loads more during movement.

Vector tiles contain geometry and attributes that the client styles; raster tiles contain rendered images.

Search and geocoding

Geocoding converts an address or place description into coordinates.

Reverse geocoding converts a coordinate into a human-readable place. Ambiguity comes from duplicate street names, incomplete addresses, language, and changing businesses.

Search ranks candidates by relevance and proximity.

Privacy

Location history can reveal:

home,
workplace,
medical visits,
religion,
and relationships.

Use permission, minimization, retention limits, aggregation, secure access, and clear controls.

Precise background location deserves especially strong justification.

Knowledge check

Which signals help a phone estimate location?
What is map matching?
How does a road graph represent navigation?
Why is the lowest-cost route not always shortest distance?
Which privacy risks make location data sensitive?

The one idea to remember

Navigation combines uncertain device position with a detailed road graph, legal constraints, routing algorithms, live and historical traffic, and learned travel-time models. Routes and ETAs are continuously updated predictions about a changing physical world.