flowchart TD
A[Raw GPS Records] --> B[Anomaly Detection]
B --> C[DBSCAN Clustering]
C --> D{Stop Cluster?}
D -->|Yes| E[Collapse to Centroid]
D -->|No| F[Keep Points]
E --> G[Douglas-Peucker Simplification]
F --> G
G --> H[OSRM Map Matching]
H --> I{Gap Detected?}
I -->|Yes| J[Route via OSRM]
I -->|No| K[Continue]
J --> L[Aggregate Distances]
K --> L
L --> M[Generate JSON]
M --> N[Render in Leaflet]
Why C/C++
What we are building is a GPS Trajectory Reconstruction and Stop-Detection Engine, so performance matters. We could use Python with libraries such as Scikit-learn for DBSCAN and call OSRM as a REST service, or use Java for the clustering logic and still call OSRM over HTTP.
The Python approach is convenient because we do not need to implement DBSCAN ourselves. However, it adds an extra runtime dependency and gives us less control over the implementation. If we need custom behavior such as T-DBSCAN, adaptive eps, or other variants, we may eventually need to reimplement or deeply modify the algorithm anyway.
The Java approach is also reasonable, but for this engine we want fine-grained control over performance, memory usage, and low-level optimizations such as SIMD and multithreading. We also want the engine to be deployable as a standalone executable and reusable across projects without requiring a JVM or interpreter on the target system.
Using C/C++ fits this design well because OSRM itself is built in C++, integration is straightforward, and the resulting engine is portable and self-contained.
DBSCAN Clustering (Stop Detection)
Due to GPS drifts stops form clusters, this behavior can be used to detect when the truck stopped, and how long did it stop. To extract this behavior a data clustering algorithm was used, unlike k-means DBSCAN does not require one to specify the number of clusters in the data a priori, also DBSCAN can find arbitrarily-shaped clusters and robust to outliers. Therefor DBSCAN was picked instead of other algorithms.
T-DBSCAN (Spatiotemporal Density Clustering)
Our implementation of DBSCAN is a bit different, what we implemented is T-DBSCAN where it clusters not just using x and y coordinates, but also adds the aspect of time. Time is needed to separate trips, let me give you an example:
let's say we passed by a place A at 08:00AM, and then we passed by the same place at 01:00PM, now we passed by the same place but in different time, if we don't include time this may form a cluster and indicate a stop even though we didn't stop at that location.
By adding the time aspect the algorithm becomes spatiotemporal, and will fix the issue above.
Intuition (all together)
Two points belong to the same cluster only if:
- they are close in space ε
- close in time Δt
- and part of a dense neighborhood MinPts
Parameter
- MinPts: Minimum number of points required to form a dense region (core point).
- ε: Maximum spatial distance between two points to be considered neighbors.
- Δt: Maximum time difference allowed between points for them to be considered neighbors in time.
Optimization
The T-DBSCAN algorithm is optimized with KD-Tree, this will help find the nearest points faster, if further optimizations are needed then we should look into improving the Cash Hits and maybe change the algorithm to use SIMD and Multi-Threading.
Douglas-Peucker Simplification
The Douglas-Peucker Simplification algorithm (often called the Ramer-Douglas-Peucker algorithm) is a technique used in computational geometry to reduce the number of points in a curve or line while preserving its overall shape.
Imagine you have a line made of many points (like a GPS path or a drawn shape). The algorithm removes unnecessary points so the line becomes simpler—but still looks almost the same.
Why it's needed?
Having hours of GPS records will slow down OSRM Map Matching, so to speed it up, we reduce and simplify number of points, using line simplification algorithm.
We choosed Ramer-Douglas-Peucker Algorithm as it the most common algorithm but there is other like:
- Visvalingam-Whyatt
- Reumann-Witkam
- Opheim simplification
- Lang simplification
- Zhao-Saalfeld
- Imai-Iri
How it works (step-by-step)
- Start with endpoints
- Take the first and last point of the line segment.
- Find the farthest point
- Look for the point between them that is farthest from the straight line connecting the endpoints.
- Check distance vs tolerance (ε)
- If the distance is greater than ε (epsilon) → keep that point and split the line there.
- If the distance is less than ε → remove all intermediate points (they're not important).
- Repeat recursively
- Apply the same process to each new segment.
Parameter
- ε: Small value will keep more points, Large values will remove more points.
Map Matching
Map Matching is the process of taking raw geographic data—usually a sequence of GPS points—and snapping it onto a known map, like a road network, to figure out the exact path someone actually traveled.
Why it's needed
GPS data isn't perfectly accurate, Signals can drift due to buildings, weather, or device limitations, So if you record a trip, your points might look like they jump around or even go off-road. Map matching corrects this.
For us Map Matching is handled by OSRM (Open Srouce Route Matching).
Example
Imagine your phone records these GPS points while you're driving:
- Some points fall slightly off the road.
- A few might even appear on nearby streets.
Map matching analyzes those points and determines You were actually on this road, following this route.
Basic Idea
It combines:
- Geometry: Distance between GPS poitns and roads.
- Topology: How roads connect.
- Movement Logic: Speed, Direction, and continuity.
Advanced methods use probabilistic models like Hidden Markov Models (HMMs) to guess the most likely path.
Gap Detections
GPS records are not perfect, and sometimes you get gaps, so when we do Map Matching you may not get one path, we may get multiple paths, if we get multiple paths it means that we have a gap.
Number of gaps is determined by n_{\text{gaps}} = n_{\text{paths}} - 1
How to handle gaps
Handling gaps is very simple, we take last point from PATH_1, then we take first point from PATH_2, then we run Routing Engine OSRM on these two points. We do this to all gaps.
Rendering
Polyline
A polyline in GPS and mapping systems is a compact way to encode a sequence of latitude/longitude points into a short string. It is commonly used to reduce payload size and transmit route geometry efficiently.
Normally, a route looks like this:
[
[36.7525, 3.04197],
[36.7530, 3.04250],
[36.7540, 3.04320]
]
That's a lot of data. A polyline encoding compresses it into something like:
}_p~F~ps|U_ulLnnqC_mqNvxq`@
This reduces size for faster transmission over APIs.
How Polyline Encoding Works (Simplified)
The algorithm:
- Multiplies coordinates by 1e5 (to preserve precision).
- Converts to integers.
- Stores the difference between points (delta encoding).
- Applies binary + Base64-like encoding.
Polyline in JS
In JS we use @mapbox/polyline library:
const polyline = require('@mapbox/polyline');
const encoded = '}_p~F~ps|U_ulLnnqC_mqNvxq`@';
// decoded is an array of [lat, lng] pairs
const decoded = polyline.decode(encoded);
// render it to leaflet map.
L.polyline(decoded).addTo(map);
Or you can decode it manuly
Java
import java.util.ArrayList;
import java.util.List;
public class PolylineDecoder {
public static List<double[]> decode(String encoded) {
List<double[]> coordinates = new ArrayList<>();
int index = 0, lat = 0, lng = 0;
while (index < encoded.length()) {
int b, shift = 0, result = 0;
// Decode latitude
do {
b = encoded.charAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
int deltaLat = ((result & 1) != 0)
? ~(result >> 1)
: (result >> 1);
lat += deltaLat;
// Decode longitude
shift = 0;
result = 0;
do {
b = encoded.charAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
int deltaLng = ((result & 1) != 0)
? ~(result >> 1)
: (result >> 1);
lng += deltaLng;
coordinates.add(new double[] {
lat / 1E5,
lng / 1E5
});
}
return coordinates;
}
public static void main(String[] args) {
String encoded = "}_p~F~ps|U_ulLnnqC_mqNvxq`@";
List<double[]> points = decode(encoded);
for (double[] point : points) {
System.out.println(point[0] + ", " + point[1]);
}
}
}
JavaScript
function decodePolyline(str) {
let index = 0, lat = 0, lng = 0;
const coordinates = [];
while (index < str.length) {
let result = 0, shift = 0, b;
do {
b = str.charCodeAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
const deltaLat = ((result & 1) ? ~(result >> 1) : (result >> 1));
lat += deltaLat;
result = 0;
shift = 0;
do {
b = str.charCodeAt(index++) - 63;
result |= (b & 0x1f) << shift;
shift += 5;
} while (b >= 0x20);
const deltaLng = ((result & 1) ? ~(result >> 1) : (result >> 1));
lng += deltaLng;
coordinates.push([lat / 1e5, lng / 1e5]);
}
return coordinates;
}