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?

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.

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.

Answer 3

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

Answer 4

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

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