How to create a master track from a large set of coordinates received from gps trackers?

Question

satellite navigation

There is a self-written transport monitoring system.
There are several hundred cars equipped with GPS trackers.
All cars ride from Moscow to the regions. Imagine a map of Moscow and the region, the main highways leaving the Moscow Ring Road and going to Vladimir, Yekaterinburg, Krasnoyarsk, St. Petersburg, Krasnodar, etc. Dozens and hundreds of cities.
For a year of work, several tens of millions of coordinates have accumulated in the system. If you display them on the map, they will mainly fall on the tracks mentioned above. Sometimes there will be "garbage coordinates" - a car under the roof of a gas station, or some other kind of interference, bypassing traffic jams. For example, you can go to St. Petersburg from Moscow through Chekhov. We found out about it only after the launch of monitoring. "Garbage" is enough.
The task is as follows: to teach the monitoring system to independently determine the departure from the main / usual route of movement. To do this, I want to process all existing points and get the so-called. master track. And then look for the nearest coordinate from the master track to the one received from the tracker from the car, and if the distance is more than a certain one 2 times in a row, consider it a departure from the route.
Currently coordinates are stored as XX.XXXXXX and YY.YYYYYY. Those. precision six decimal places. The master track must contain five decimal places.
The algorithm should filter out "garbage", i.e. if there are no other points around the point that we are considering within a radius of five decimal places or there are less than a certain number of them, then we consider the point to be garbage and do not take it into account in the calculations.
Those. You can start by simply cutting off the sixth decimal place. Then we "remove" the garbage points. And then from the rest you need to calculate the master track.
I tried many options and realized that the ideal option is the median. But I don't know how to apply it to coordinates.
Colleagues, any ideas?

Answer 1

Think about this option:
1) with your hands on the map, roughly draw the geometry of the area (not necessarily rectangular) where one track appears clearly (to highlight an array of points related to one track). It is unlikely that this is easy to do automatically
2) beat the entire manually designated area into small squares. For each of these squares, we will look for the average value. That's just here and you can take into account the very sixth sign - i.e. build squares so that in the coordinates of the square's boundaries, the sixth sign is equal to zero (i.e., there will be 10 possible values ​​of the real coordinate for each square).
3) for each square we make a selection of coordinates from the base (if there is a normal spatial index, it should be fast). If no coordinates fall into the square, we skip it (there will be most of them, but the fewer of them, the more accurately you manually selected the area of ​​one track). If at least one hit (and preferably several) - we consider the average value. This average becomes part of the master track.
By changing the size of the averaging "grid" described above, one can either reduce the number of points in the master track, coarsening the detour detection, or increase the number of points, as well as the determination accuracy.

Answer 2

My opinion:
1) I think You can reduce the data if, for example, weed out the nearest / identical points using clustering.
2) Numerical Methods. Interpolation.