How to draw an even route on the map, having a large number of GPS coordinates with errors?

Question

satellite navigation

We are developing a mobile application, one of the functions of which is to track the user's route. The application simply sends the coordinates to the server when the user navigates.
Then the main problem arises - how to draw an even route on the map using these coordinates?
If we simply connect all the points in order, then we have 2 problems:
1. Too many points. This problem is solved with curve simplification algorithms such as RDP .
2. The GPS is not perfect, and sometimes the error may be 100-200 meters. As a result, zigzags, loops and other ugly things appear on the map, although obviously the person was simply moving in a straight line.
Example:

black - if you just connect the dots in order
red - about what is required
Question: can someone suggest the desired algorithm, or at least give advice on where to dig? Interested in the possibility of smoothing errors.

Answer 1

take a geo-information system such as Nexgis QGIS (free and Russian-speaking programmers) and rummage through its documentation about smoothing tracks.
in general, there are a lot of sequence averaging/smoothing algorithms, only it will be necessary to choose the appropriate one that produces the best line based on the test data set.

Answer 2

https://en.wikipedia.org/wiki/Curve_fitting
Many statistical packages such as R and numerical software such as the GNU Scientific Library, MLAB, Maple, MATLAB, GNU Octave, and SciPy include commands for doing curve fitting in a variety of scenarios. There are also programs specifically written to do curve fitting; they can be found in the lists of statistical and numerical analysis programs as well as in Category:Regression and curve fitting software.

Answer 3

It is not simple. And it gets more complicated if you need real-time anti-aliasing. If not, smooth not the current, but the past (3-5 points, depending on the speed of the object).
More measurements means fewer errors. And for the excess, you can apply filtering and thinning .
Speed ​​filter: build a radius (or sector) waiting for the next sample to appear and discard if it does not fall within it.

Answer 4

Track vector movement speed and total movement vector relative to the previous path reference point with a depth of 3-4 (transition direction).
According to the picture: the 2nd points are close to each other (4.6 and 7.8) - it is immediately clear that the speed has fallen there. So you can fix the reference point in this radius and a possible break in the route trajectory.
Adjacent tolerances - calculated on the basis of acceleration (time marks on coordinates).
For visualization - use Bizier curves . This will be much better for visual perception and will make it much easier for you to understand track smoothing.

Answer 5

although obviously the person was just moving in a straight line

What is obvious? In the general case, this is not at all obvious, unless there are some additional restrictions, for example, that the user is guaranteed to drive the car along the street. If there are no such restrictions, then any "combing" will be an unreasonable fantasy.
Of course, some optimization tools can be applied to tracks. For example, remove segments where the speed is atypically high (which may be outliers due to poor reception). But there simply cannot be a simple algorithm for combing tracks.

Answer 6

Search:

• "line simulation"
  
• "Douglas-Peucker algorithm"
  
• "FastSTRay algorithm"
  

Answer 7

https://developers.google.com/maps/documentation/r...