polilínea suave con deformación mínima

Question

Tengo una polilínea 2D cerrado, que es razonablemente suave. Los vértices que definen la polilínea sin embargo, no están espaciadas por igual. A veces dos estarán muy cerca, a veces hasta cuatro estarán muy próximos entre sí.

Me gustaría suavizar la polilínea, pero un algoritmo de promedio normal tiende a encogerse la zona:

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);
}

Mis polilíneas contienen miles de puntos y el ángulo entre dos segmentos adyacentes es típicamente de menos de 1 grado.

¿Hay una mejor manera de suavizar estas curvas, algo que va más espacio en los vértices por igual, sin afectar a la zona demasiado?

Answer 1

Se podría buscar en la literatura "curva de simplificación", tales como el algoritmo de Douglas-Peucker o este trabajo http://www.cs.ait.ac.th/~guha/papers/simpliPoly.pdf .

Esto probablemente no funcionará bien si necesita vértices espaciados uniformemente incluso cuando los segmentos de línea adyacentes que definen son colineales casi.

Answer 2

Creo que busca de Chaikin Algoritmo . Existe una variante de esta idea que hace que la curva suavizada pasar directamente a través de (en lugar de "dentro" de) los puntos de control, pero estoy teniendo problemas buscando en Google por el momento.

Answer 3

También puede utilizar splines para interpolar - sólo la búsqueda en Wikipedia

Answer 4

Alguien ha portado 2 algoritmos de suavizado a C #, con una licencia CPOL (gratis), ver aquí:

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