Smooth polyline with minimal deformation

Question

I've got a 2D closed polyline, which is reasonably smooth. The vertices that define the polyline however are not spaced equally. Sometimes two will be very close, sometimes as many as four will be very close together.

I'd like to smooth the polyline, but a regular averaging algorithm tends to shrink the area:

for (int i = 0; i < (V.Length-1); i++)
{
   PointF prev = V[i-1]; //I have code that wraps the index around.
   PointF next = V[i+1];       
   PointF pt = V[i];

   float ave_x = one_third * (prev.X + next.X + pt.X);
   float ave_y = one_third * (prev.Y + next.Y + pt.Y);

   smooth_polyline[i] = new PointF(ave_x, ave_y);
}

My polylines contain thousands of points and the angle between two adjacent segments is typically less than 1 degree.

Is there a better way to smooth these curves, something which will space the vertices more equally, without affecting the area too much?

Hildick

What do you mean by "space the vertices more equally?" A smoothing algorithm is either going to amplify the signal or compress it. – Bailee

Let's see if I can do this in ascii... Imagine I have the following polyline (dots are corners): ●─●─●─●─────────────● I want to change this so that it becomes: ●────●────●────●────● By "vertex spacing" I mean I'd like to make the distance between any given adjacent vertices more similar. – Hildick

Answer 1

You could look at the "curve simplication" literature such as the Douglas-Peucker algorithm or this paper http://www.cs.ait.ac.th/~guha/papers/simpliPoly.pdf.

This probably won't work well if you need evenly spaced vertices even when the adjacent line segments they define are nearly collinear.

Sherri

Thanks Doug, this is promising. – Hildick

Answer 2

I think you are looking for Chaikin's Algorithm. There is a variant of this idea that makes the smoothed curve pass directly through (instead of "inside" of) the control points, but I'm having trouble googling it at the moment.

Sherri

@Doug, this algorithm involves adding points. I need to redistribute the existing points instead. – Hildick

David, in that case, I would add lots of points using this (or another) smoothing method, and then remove them at evenly spaced intervals. In that case, you might have better luck using a spline method and some sort of check that the point you are deleting has sufficiently similar curves on either side of it. The problem is that most of the smoothing algorithms are local (for efficiency in rendering, etc.) but the optimal solution to your problem is necessarily global. – Sherri

Answer 3

You can also use splines to interpolate - just search in wikipedia

Shinto

@whatnick, how will spline interpolation let me re-position the existing points? It would be a great method for adding points in between existing ones, but I do not want to change the topology of my polyline. – Hildick

There are error limits in splines (called tension) used to minimize oscillations.A spline is basically a set of polynomials, you are fitting a set of curves that pass through your points. You can do an error estimate once the spline is fitted to ensure the topology generated is within tension limits which you set. – Shinto

Answer 4

Somebody has ported 2 smoothing algorithms to C#, with a CPOL (free) license, see here:

https://github.com/RobinCK/smooth-polyline

Vinificator