Algorithm for simplifying the path and smoothing two-dimensional trajectories

Question

I am looking for an algorithm to simplify and smooth paths for 2D paths. Therefore, I have an ordered list of two-dimensional points. These points should be simplified, for example. with the Ramer-Douglas-Pyuker algorithm. But the output should be smooth, so the resulting path should be built from Bezier curves or splines. Is there any modification of the Ramer-Douglas-Puker algorithm that could handle this?

I found a path simplification algorithm in the paper.js library that does exactly what I'm looking for: http://paperjs.org/examples/path-simplification/ But I couldn’t understand the algorithm from the undocumented javascript source code.

Answer 1

The work you want to do is classified as curve fitting. There are many different algorithms for curve fitting, but almost all curve fitting algorithms can be divided into two different categories: interpolation and approximation. The interpolation algorithms produce a curve that exactly passes through all the data points, while the approximation algorithms generate a curve that is close to the data points. Of course, there are hybrid algorithms.

Since you want the data points to be smooth, you should look for approximation algorithms. For the two algorithms that you mentioned: the RDP algorithm and the Schneider algorithm (the one in Paper.js), they are both approximation algorithms. So basically you can use any of them. For RDP, after obtaining the simplified path, you can use the creation of the Catmull Rom spline or the Overhauser spline through the vertices of the simplified path to obtain a smooth curve. However, you do not have direct control over the deviation between the resulting spline and the vertices of the original path.

For the Schneider algorithm, it starts by fitting the data points of a cubic Bezier curve with boundary tangent constraints. If the deviation from the resulting curve is too large, then it will divide the data points into two “regions” and place each data region with cubic Bezier curves with boundary tangent constraints. This process will be repeated until the deviation to all Bezier curves is sufficiently small. The result is a series of cubic Bezier curves connected at best with continuity C1 (most likely, this is only G1). In addition, since this algorithm estimates the final tangents from the source data points, noise at the data point will affect the estimate of the tangency of the end and, therefore, the cubic Bezier setup.

If you can spend time on fitting a curve, you should look at the smallest square fitting with B-spline curves. This will generate an output curve with high continuity (C2 for cubic B-spline curves, for example). If you have little time to spend, then the Schneider algorithm is a good choice that balances the balance between the cost of implementation (if you need to re-implement it in a certain language) and the resulting quality of the curve.

Answer 2

What you are trying to do is called Curve Fitting.

While the Ramer-Douglas-Puker algorithm substantially smooths out the “noise” from the polyline by removing unnecessary points, the curve fitting algorithm will correspond to the bezier curves through these points.

Here is a pretty good example on Youtube, and here is the original article describing the algorithm itself.

---

Regarding the Paper.js example:

• This is the Github link for this particular functionality that you talked about, and it is pretty well commented. The research document used is this .

• Also here is a very short discussion of the mailing list about what was used and what is not (apparently, Ramer-Douglas-Peucker was used, but deleted later)