My Amazon wishlist can be found here.

# Smoothing lines with splines

For my OpenStreetMap year of edits videos I use PovRay to animate edits of OpenStreetMap. Over the course of a year I show all the edits that have been made. In previous years, I used a simple sine function to rotate the Earth alone it's North/South and East/West axises. This year I wanted to highlight specific events so I needed a different method to rotate the Earth.

I started out with finding events and created two paths for them:

This one starts in Greenland, moves towards Brazil and then heads over Russia, India, the Philippines and ends in Indonesia.

The second one starts in Korea, moves through Africa, heads towards Antarctica and then heads back to France over Brazil.

Each of the two paths have points highlighted which are (about) 15 days apart. The paths I converted into data files, which look like

```0000  -24   70   8500
0180  -64   58   9500
0240  -81   29  10000
0480  -43  -16  15000
0720   -8   36  20000
0840   27   44  15000
1020   76   20  15000
1140  115   25  15000
1320  127   -2   9000
1460  157  -24  10000

```

The first column is the frame number (four frames per day), then the longitude and the latitude and finally the height of the camera over the point. As you can see, I have not included a line for each of the points in the path images.

From the points in the data files, I then needed to generate all the intermediate points for each of the three columns. And my first (naive) attempt was to simply do a linear interpolation. Point 1's longitude can be calculated by: `-24 + (1-0) * ((-64 - -24) / (180 - 0))` and point 856's longitude with: `27 + (855 - 840) * ((76 - 115) / (1020 - 840))`. Doing that for all of the three axis (for the first 300 frames) results in the following video:

Linear interpolation of a line between a set of points

As you can see, the changes in direction (and height) are really abrupt, and doesn't make for a nice smooth rotating body. So I had to come up with something else: a smoothed line.

There are various different ways of smoothing line, but one of the easier ones that I found was the Spline. A spline is a smoothing function that connects all the data points with sufficiently smooth curves. I used the implementation at http://www.script-tutorials.com/smooth-curve-graphs-with-php-and-gd/ with the other script available through https://github.com/derickr/osm-year-in-edits/blob/master/changes/create-camera-from-file.php

If we now look at the same section of the video, we see that the turns and zoom level are much smoother:

Interpolation between a set of points with a spline

Just focussing on the zoom aspect, I am also reproducing a line graph of the interpolated points here:

As you can see, between 1172 and 1328 it makes a very big dipβand that wrecked with my video as it zoomed in too much. I've fixed that manually for the video, but I would like to find an algorithm that did produce smooth lines without such a big "dip". Any ideas are most welcome.

Maybe the easiest solution is to insert a "correcting dot" at about (1300, 8000)?

Since your point at the right of 1328 is so far "off", it causes the line to do a small dip at the left of 1328. I'd still call it small, compared to the offset of your last point...

Moving average could help, even if "noises" appear anywhere in the data set:

http://en.wikipedia.org/wiki/Moving_average

CatmullβRom spline should do what you want: http://en.wikipedia.org/wiki/Hermite_curve#Catmull.E2.80.93Rom_spline