Suggestion: Implementing Polyline Simplification in Traccar Client

As is the client sends locations every X seconds no matter how the device has moved since last location was send. This can give a lot of unimportant locations if the device is moving on a straight line or standing still. We might also miss the important locations where the device turns direction. This can give a less smooth traveling curve on the map. I would suggest that a Polyline Simplification algoritm is implemented to calculate which locations are important to send to the server.

The Reumann-Witkam Algorithm is a simple very effective method which I have used before. Reumann-Witkam routine uses a point-to-line (perpendicular) distance tolerance. It defines a line through the first two vertices of the original polyline. For each successive vertex v(i), its perpendicular distance to this line is calculated. A new key is found at v(i-1), when this distance exceeds the specified tolerance. The vertices v(i) and v(i+1) are then used to define a new line, and the process repeats itself.

Only one configuration parameter is needed: "Tolerance distance". The algorithm can be combined with the existing time-frame configuration so that a position is send every X seconds if no position has been choosen by Reumann-Witkam Algorithm.

Calculation of the Perpendicular Distance can be done with simple trigonometry like this:

public static double PerpendicularDistance(TrackPoint pointA, TrackPoint pointB, TrackPoint pointP)
{
// Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)| Area of triangle
// Base = √((x1-x2)²+(x1-x2)²) Base of Triangle
// Area = .5Base*H *Solve for height
// Height = Area/.5/Base

    double area = Math.Abs(.5 * (pointA.Lat * pointB.Lon + pointB.Lat * pointP.Lon + 
        pointP.Lat * pointA.Lon - pointB.Lat * pointA.Lon - pointP.Lat * pointB.Lon - pointA.Lat * pointP.Lon));
    double bottom = Math.Sqrt(Math.Pow(pointA.Lat - pointB.Lat, 2) + Math.Pow(pointA.Lon - pointB.Lon, 2));
    double height = area / bottom * 2;
    return height;
}

Does this make sence?

Good suggestion. Advanced GPS devices usually implement three reporting options:

1. Report by time interval (all GPS devices have this including Traccar Client app)
2. Report by distance
3. Report by angle

I want to implement the second option for Traccar Client in one of the future versions.

You are correct that many GPS devices (I'll not call them advanced) uses time, distance, angle options in some proprietary algoritm. I'm of the opinion that they often fail to deliver a good smooth location trajectory.

One of the main challenges in creating trajectories is to locate when the device changes direction. If you base it on simple time/distance/angle algoritm you are in a risk of missing when multiple sharp turns are made within a short interval which result in a bad trajectory.

Many Polyline Simplification algoritms have been with different advantages ex:

• N'th Point
• Radial distance
• Perpendicular Distance
• Reumann-Witkam
• Opheim
• Lang
• Douglas-Peucker
• etc...
  some of them better than others and some uses complex mathematical calculations and needs many GPS-locations in the memory buffer to be able to make the correct calculation because they work on a sliding window of historical GPS-locations.
  I have been analyzing trajectories for more than a decade - I'm no longer in the buisness but can't stop when I see an interesting project like yours. It is my experience that you get the best result with minimal effort by using the Reumann-Witkam algoritm instead of trying to implement your own algotritm. It only needs a maximum of four GPS-locations in memory buffer to make the calculations: Last GPS-log send to server [v(0)], The first GPS-log after v(0) [v(1)], The cuurent GPS-log [v(i)] and The previous GPS-log [v(i-1)]. By evaluating the triangle made by [v(0)], [v(1)] and [v(i]] the algotritm decides if [v(i-1)] should be sent to the server. If so [v(i-1)] becomes the new [v(0)] and [v(i)] becomes the new [v(1)]. Otherwice we forget about [v(i-1)] and [v(i)] becomes the new [v(i-1)] waiting for a new [v(i)] to arrive.
  I realy hope that you will consider to implement this simple algoritm.

I will definitely consider it for one of the next version of Traccar Client apps.

Thanks again for sharing this information.

Hi Anton,

Is this something already added to the clients apps?

No, it's not implemented yet.

any news about this? we need to smooth the path of moving GPS or when it is at a single place, how can I reduce the "star" of error points of GPS... any idea would be appreciated, tnx!

This is not implemented yet. You can get rid of "stars" by using server side filtering.

Great! Can you provide the file path where I need to edit the code to deploy it? After tried it I will share it here if it works

You don't need to change any code. You can do it via config file:

https://www.traccar.org/configuration-file/

I tried with some numbers in the config but I still have the errors in the map, I need to smooth the signal until 1 point in the map or more than 1 but very close to improve accuracy in object tracking. Check my screenshot https://www.dropbox.com/s/k9him0bju47gvfe/snapshot1.png?dl=0

The present config is (important part only):

<entry key='event.enable'>false</entry>
<entry key='event.overspeedHandler'>false</entry>
<entry key='event.overspeed.notRepeat'>true</entry>
<entry key='event.motionHandler'>false</entry>
<entry key='event.geofenceHandler'>false</entry>
<entry key='event.alertHandler'>false</entry>
<entry key='event.ignitionHandler'>false</entry>

<entry key='geocoder.enable'>true</entry>
<entry key='geocoder.type'>google</entry>

<entry key='location.enable'>true</entry>
<entry key='location.type'>mozilla</entry>

<entry key='filter.enable'>true</entry>
<entry key='filter.zero'>true</entry>
<entry key='filter.invalid'>true</entry>
<entry key='filter.duplicate'>true</entry>
<entry key='filter.distance'>10</entry>

<entry key='coordinates.filter'>true</entry>
<entry key='coordinates.error'>10</entry>

You shouldn't have both "filter.distance" and "coordinates.filter". Also, 10 meters is a really low value. GPS error is higher than that. I would recommend at least 30, but probably it has to be even higher.

ah ok, which one is it better to keep and the other remove? the filter or the coordinates to achieve better smooth of data? I will try the 30 in filter or coordinates after your message, thanks a lot!!

The difference between those two is that one filters out report completely, the other one just adjusts the coordinates to avoid fluctuations.

OK, then maybe we need some more advanced... I would need a low pass / kalman filter or something to smooth big errors (ignore them) and move the position in map slowly without weird jumps, I would do it if it doesn't exist in code. I just need to know where I can put the code to process the new GPS positions before storing them in DB.