polyligne lisse avec une déformation minimale

Question

J'ai une polyligne fermée 2D, ce qui est assez lisse. Les sommets qui définissent la polyligne mais ne sont pas espacées de façon égale. Parfois, deux seront très proches, parfois jusqu'à quatre seront très proches.

Je voudrais lisser la polyligne, mais un algorithme régulier de moyenne tend à se rétrécir la zone:

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

Mes polylignes contiennent des milliers de points et l'angle entre deux segments adjacents est typiquement inférieur à 1 degré.

Y at-il une meilleure façon de lisser ces courbes, ce qui va espacer les sommets plus même, sans trop affecter la région?

Answer 1

Vous pouvez regarder la littérature « courbe simplication » tel que l'algorithme de Douglas-Peucker ou cet article http://www.cs.ait.ac.th/~guha/papers/simpliPoly.pdf .

Ce ne sera probablement pas fonctionner correctement si vous avez besoin de sommets régulièrement espacés, même lorsque les segments de ligne adjacents ils définissent sont presque colinéaires.

Answer 2

Je pense que vous êtes à la recherche pour l'algorithme de Chaikin . Il existe une variante de cette idée qui fait la courbe lissée passe directement à (au lieu de « l'intérieur » de) les points de contrôle, mais je vais avoir du mal à googler le moment.

Answer 3

Vous pouvez également utiliser splines pour interpoler - il suffit de rechercher dans wikipedia

Answer 4

Quelqu'un a porté 2 algorithmes de lissage à C #, avec une licence CPOL (gratuite), voir ici:

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