Interpolación de secuencia de puntos

Question

Dada una secuencia arbitraria de puntos en el espacio, ¿cómo se produciría una interpolación continua y suave entre ellos?

Se aceptan soluciones 2D y 3D.También se aprecian las soluciones que producen una lista de puntos con granularidad arbitraria y las soluciones que producen puntos de control para curvas de Bézier.

Además, sería genial ver una solución iterativa que pudiera aproximarse a las primeras secciones de la curva a medida que recibió los puntos, para poder dibujar con ella.

Answer 1

El Spline de Catmull-Rom Se garantiza que pasará por todos los puntos de control.Considero que esto es más útil que intentar ajustar puntos de control intermedios para otros tipos de splines.

Este PDF de Christopher Twigg tiene una breve introducción a las matemáticas del spline.La mejor frase resumida es:

Las estrías de Catmull-ROM tienen continuidad C1, control local e interpolación, pero no se encuentran dentro del casco convexo de sus puntos de control.

Dicho de otra manera, si los puntos indican una curva pronunciada hacia la derecha, la spline se inclinará hacia la izquierda antes de girar hacia la derecha (hay una imagen de ejemplo en ese documento).La estanqueidad de esos giros es controlable, en este caso usando su parámetro tau en la matriz de ejemplo.

Aquí está otro ejemplo con algún código DirectX descargable.

Answer 2

Una forma es polinomio de Lagrange, que es un método para producir un polinomio que pasará por todos los puntos de datos dados.

Durante mi primer año en la universidad, escribí una pequeña herramienta para hacer esto en 2D, y puedes encuéntralo en esta página, se llama solucionador de Lagrange.La página de Wikipedia también tiene una implementación de muestra.

Cómo funciona es así:tienes un polinomio de orden n, p(x), donde n es el número de puntos que tienes.Tiene la forma a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, dónde _ es subíndice, ^ es poder.Luego conviertes esto en un conjunto de ecuaciones simultáneas:

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

Convierte lo anterior en una matriz aumentada y resuelve los coeficientes a_0 ... a_n.Entonces tienes un polinomio que pasa por todos los puntos y ahora puedes interpolar entre los puntos.

Sin embargo, tenga en cuenta que es posible que esto no se adapte a su propósito, ya que no ofrece ninguna forma de ajustar la curvatura, etc.: se quedará atrapado con una única solución que no se puede cambiar.

Answer 3

Deberías echar un vistazo a B-splines.Su ventaja sobre las curvas de Bézier es que cada parte depende únicamente de puntos locales.Por lo tanto, mover un punto no tiene ningún efecto en las partes de la curva que están lejos, donde "lejos" está determinado por un parámetro de la spline.

El problema con el polinomio de Langrange es que agregar un punto puede tener efectos extremos en partes aparentemente arbitrarias de la curva;no hay "localidad" como se describe anteriormente.

Answer 4

¿Has mirado el Unix? ranura ¿dominio?¿Se puede obligar a eso a hacer lo que quieres?

Answer 5

Existen varios algoritmos para interpolar (y exrapolar) entre un conjunto arbitrario (pero final) de puntos.deberías revisar recetas numéricas, también incluyen implementaciones en C++ de esos algoritmos.

Answer 6

Desafortunadamente, Lagrange u otras formas de interpolación polinomial no funcionarán en un conjunto arbitrario de puntos.Solo funcionan en un conjunto donde en una dimensión, p.X

X_i <x_yo+1

Para un conjunto arbitrario de puntos, p.e.En una trayectoria de vuelo de un avión, donde cada punto es un par (longitud, latitud), será mejor que simplemente modele el viaje del avión con la longitud, latitud y velocidad actuales.Al ajustar la velocidad a la que el avión puede girar (su velocidad angular) dependiendo de qué tan cerca esté del siguiente punto de ruta, puede lograr una curva suave.

La curva resultante no sería matemáticamente significativa ni le daría puntos de control Bézier.Sin embargo, el algoritmo sería computacionalmente simple independientemente del número de puntos de referencia y podría producir una lista interpolada de puntos con granularidad arbitraria.Tampoco requerirá que proporciones el conjunto completo de puntos por adelantado, simplemente puedes agregar puntos de referencia al final del conjunto según sea necesario.

Answer 7

Se me ocurrió el mismo problema y lo implementé con algunos amigos el otro día.Me gusta compartir el proyecto de ejemplo en github.

https://github.com/johnjohndoe/PathInterpolation
Siéntete libre de bifurcarlo.

Answer 8

Google "regresión ortogonal".

Mientras que las técnicas de mínimos cuadrados intentan minimizar la distancia vertical entre la línea de ajuste y cada f(x), la regresión ortogonal minimiza las distancias perpendiculares.

Apéndice

En presencia de datos ruidosos, el venerable ransac También vale la pena echarle un vistazo al algoritmo.

Answer 9

En el mundo de los gráficos 3D, los NURBS son populares.Se puede buscar más información fácilmente en Google.