Interpolation de séquence de points

Question

Étant donné une séquence arbitraire de points dans l'espace, comment produiriez-vous une interpolation continue et lisse entre eux?

Les solutions 2D et 3D sont les bienvenues. Les solutions qui produisent une liste de points à granularité arbitraire et les solutions qui produisent des points de contrôle pour les courbes de Bézier sont également appréciées.

En outre, il serait intéressant de voir une solution itérative qui permettrait de se rapprocher des premières sections de la courbe au fur et à mesure de la réception des points, de sorte que vous puissiez dessiner avec.

Answer 1

La Spline Catmull-Rom est garantie pour réussir à travers tous les points de contrôle. Je trouve cela plus pratique que d’essayer d’ajuster des points de contrôle intermédiaires pour d’autres types de splines.

Ce PDF de Christopher Twigg a une belle brève introduction à la mathématique de la spline. La meilleure phrase de synthèse est:

  

Les splines Catmull-Rom ont C1   continuité, contrôle local et   interpolation, mais ne se trouvent pas dans   la coque convexe de leur contrôle   points.

En d’autres termes, si les points indiquent un virage serré à droite, la spline s’incline à gauche avant de tourner à droite (vous trouverez un exemple de photo dans ce document). L’étanchéité de ces tournants est contrôlable, en utilisant ici le paramètre tau dans la matrice exemple.

Voici un autre exemple avec du code DirectX téléchargeable.

Answer 2

Une solution consiste à Polynominal de Lagrange , qui est une méthode permettant de produire un polynôme qui sera à travers tous les points de données donnés.

Au cours de ma première année à l'université, j'ai écrit un petit outil pour le faire en 2D et vous pouvez trouvez-le sur cette page , il s’appelle solutionneur de Lagrange. La page Wikipedia contient également un exemple de mise en œuvre.

Voici comment cela fonctionne: vous avez un polynôme d’ordre n, p(x), où n est le nombre de points que vous avez. Il a la forme a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, où _ est en indice, ^ est le pouvoir. Vous transformez ensuite cela en un ensemble d’équations simultanées:

p(x_1) = y_1
p(x_2) = y_2
...
p(x_n) = y_n

Vous convertissez ce qui précède en une matrice augmentée et résolvez les coefficients a_0 ... a_n. Ensuite, vous avez un polynôme qui passe par tous les points, et vous pouvez maintenant interpoler entre les points.

Notez cependant que cela peut ne pas convenir à votre objectif, car il ne vous offre aucun moyen de régler la courbure, etc. - vous êtes coincé avec une solution unique qui ne peut pas être modifiée.

Answer 3

Vous devriez consulter B-splines . Leur avantage sur les courbes de Bézier est que chaque partie ne dépend que de points locaux. Ainsi, déplacer un point n'a aucun effet sur les parties de la courbe qui sont éloignées, où & "Loin &"; est déterminé par un paramètre de la spline.

Le problème avec le polynôme de Langrange est que l’ajout d’un point peut avoir des effets extrêmes sur des parties apparemment arbitraires de la courbe; il n'y a pas de " localness " comme décrit ci-dessus.

Answer 4

Avez-vous examiné la commande Unix Spline ? Cela peut-il être contraint de faire ce que vous voulez?

Answer 5

Il existe plusieurs algorithmes d'interpolation (et d'exrapolation) entre un ensemble de points aribtrary (mais final). Vous devriez consulter les recettes numériques , qui incluent également les implémentations C ++ de ces algorithmes.

Answer 6

Malheureusement, la méthode de Lagrange ou d’autres formes d’interpolation polynomiale ne fonctionnera pas avec un ensemble de points arbitraire. Ils ne fonctionnent que sur un ensemble où, dans une dimension, par exemple. x

x _i < x _{i + 1}

Pour un ensemble arbitraire de points, par ex. une trajectoire de vol d'avion, où chaque point est une paire (longitude, latitude), il vaudra mieux modéliser simplement le trajet de l'avion avec la longitude actuelle & amp; latitude et vitesse. En ajustant la vitesse à laquelle l’avion peut tourner (sa vitesse angulaire) en fonction de sa proximité avec le prochain point de cheminement, vous pouvez obtenir une courbe douce.

La courbe résultante ne serait ni mathématiquement significative ni vous donnerait des points de contrôle de Bézier. Cependant, l'algorithme serait simple sur le plan des calculs, quel que soit le nombre de points de cheminement, et pourrait produire une liste interpolée de points à une granularité arbitraire. Cela ne nécessiterait pas non plus que vous fournissiez l’ensemble complet de points à l’avance, vous pourriez simplement ajouter des points de passage à la fin de l’ensemble, si nécessaire.

Answer 7

J'ai eu le même problème et je l'ai mis en place avec des amis l'autre jour. J'aime partager l'exemple du projet sur github.

https://github.com/johnjohndoe/PathInterpolation
N'hésitez pas à le fourrer.

Answer 8

Google & "Régression orthogonale &" ;.

Alors que les techniques des moindres carrés tentent de minimiser la distance verticale entre la droite d'ajustement et chaque f (x), la régression orthogonale minimise les distances perpendiculaires.

Addendum

En présence de données bruitées, le vénérable algorithme RANSAC mérite également une vérification.

Answer 9

Dans le monde graphique 3D, les NURBS sont populaires. De plus amples informations sont facilement googlé.