Algorithm for path simplification and smoothing of 2D trajectories

Question

I'm searching for an algorithm for path simplification and smoothing for 2D trajectories. So I have a ordered list of 2D points. These points should be simplified, e.g. with the Ramer–Douglas–Peucker algorithm. But the output must be smooth, so the resulting path should be constructed from Bezier curves or splines. Is there any modification of the Ramer–Douglas–Peucker algorithm which could handle this?

I found a path simplification algorithm in the paper.js library, which does exactly what I'm searching for: http://paperjs.org/examples/path-simplification/ But I was not able to understand the algorithm from the undocumented javascript source code.

Answer 1

The work you want to do falls into the category of "curve fitting". There are tons of different algorithms for curve fitting but almost all curve fitting algorithms can be divided into two different categories: interpolation and approximation. Interpolation algorithms produce a curve that passes through all the data points exactly while approximation algorithms generate a curve that lies close to the data points. Of course, hybrid algorithms also exist.

Since you want the data points to be smoothed, you should be looking for approximation algorithms. For the two algorithms you mentioned: RDP algorithm and Schneider algorithm (the one in Paper.js), they are both approximation algorithms. So, basically you can use either of them. For RDP, after obtaining the simplified path, you can use create a Catmull Rom spline or Overhauser spline thru the vertices of the simplified path to obtain a smooth curve. However, you don't have direct control for the deviation between the resulting spline and the vertices in the original path.

For Schneider algorithm, it will starts with fitting the data points by a cubic Bezier curve with end tangent constraints. If the deviation to the resulting curve is too large, then it will split the data points into two "regions" and fit each region of data with a cubic Bezier curves with end tangent constraints. This process will be repeated until the deviation to all cubic Bezier curves are small enough. As a result, it produces a series of cubic Bezier curves connected at best with C1 continuity (very likely it is actually G1 only). Furthermore, since this algorithm evaluate the end tangents from original data points, the noise in the data point will affect the end tangent evaluation and therefore the cubic Bezier fitting.

If you can spent time in the topic of curve fitting, you should look into least 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 don't have much time to spent, then Schneider's algorithm is a good choice that strikes a balance between the implementation cost (if you have to re-implement it in a specific language) and the resulting curve's quality.

Answer 2

What you're trying to do is called Curve Fitting.

While the Ramer-Douglas-Peucker algorithm essentially smoothes 'noise' out of a polyline by removing unnecessary points - a curve fitting algorithm will fit bezier curves through those points.

Here is a pretty nice example on Youtube and here is the original paper describing the algorithm itself.

---

As for the Paper.js example:

• This is the Github link for that particular functionality you mentioned and this is pretty well commented. The research paper that was used is this.

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

Answer 3

In my case I found Catmull-Rom Splines easiest to apply. Smooth Paths Using Catmull-Rom Splines article from Mika's Coding Bits is very helpful. I used it to implement a spline interpolation script with C# in my Unity3D project. This is the script:

public static Vector2 CatmullRomInterpolation(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float t, float alpha = .5f, float tension = 0)
{
    float t01 = Mathf.Pow(Vector2.Distance(p0, p1), alpha);
    float t12 = Mathf.Pow(Vector2.Distance(p1, p2), alpha);
    float t23 = Mathf.Pow(Vector2.Distance(p2, p3), alpha);
    Vector2 m1 = (1.0f - tension) * (p2 - p1 + t12 * ((p1 - p0) / t01 - (p2 - p0) / (t01 + t12)));
    Vector2 m2 = (1.0f - tension) * (p2 - p1 + t12 * ((p3 - p2) / t23 - (p3 - p1) / (t12 + t23)));
    return (2.0f * (p1 - p2) + m1 + m2) * Mathf.Pow(t, 3) + (-3.0f * (p1 - p2) - m1 - m1 - m2) * Mathf.Pow(t, 2) + m1 * t + p1;
}

p0 and p3 are the control points which should be different from p1 and p2 which are the start and destination points in your path.