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:

path2.png

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

path1.png

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:

spline.png

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.

Shortlink

This article has a short URL available: http://drck.me/spline-au2

Comments

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

Add Comment

Name:
Email:

Will not be posted. Please leave empty instead of filling in garbage though!
Comment:

Please follow the reStructured Text format. Do not use the comment form to report issues in software, use the relevant issue tracker. I will not answer them here.


All comments are moderated

Life Line