Interpolación de la Secuencia de Punto

Question

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

Se aceptan soluciones 2D y 3D. También se agradecen las soluciones que producen una lista de puntos en granularidad arbitraria y soluciones que producen puntos de control para curvas Bezier.

Además, sería genial ver una solución iterativa que podría aproximarse a las primeras secciones de la curva, ya que recibió los puntos, por lo que podría dibujar con ella.

Answer 1

Se garantiza que el Catmull-Rom spline pasará por todos los puntos de control. Encuentro esto más útil que tratar de ajustar los puntos de control intermedios para otros tipos de splines.

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

estrías Catmull-Rom tienen C1 continuidad, control local, y interpolación, pero no se encuentran dentro de la envolvente convexa de los puntos de control .

Dicho de otra manera, si los puntos indican una curva cerrada 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 rigidez de esos giros es controlable, en este caso usando su parámetro tau en la matriz de ejemplo.

Aquí está another example con algunos códigos DirectX descargables.

Answer 2

¿Has mirado el comando spline de Unix? ¿Puede eso ser forzado a hacer lo que quieres?

Answer 3

Una forma es Lagrange polynominal, 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 usted puede find it on this page, se llama solucionador de Lagrange. La página de Wikipedia también tiene una implementación de muestra.

Cómo funciona es así: usted tiene un orden polinominal n, p(x), donde n es el número de puntos que tiene. Tiene la forma a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, donde _ es un subíndice, ^ es poder. A continuación, convertir esto en un conjunto de ecuaciones simultáneas:

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

convertir el anterior en un matriz aumentada, y resolver para los coeficientes a_0 ... a_n. Entonces tienes un polinomio que atraviesa todos los puntos, y ahora puedes interpolar entre los puntos.

Sin embargo, esto puede no adaptarse a su propósito, ya que no ofrece ninguna manera de ajustar la curvatura, etc. - está atascado con una solución única que no se puede cambiar.

Answer 4

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

x _i < x _{i + 1}

Para un conjunto arbitrario de puntos, por ejemplo, una ruta de vuelo del avión, donde cada punto es un par (longitud, latitud), lo mejor será modelar el viaje del avión con la longitud actual & latitud y velocidad. Ajustando la velocidad a la que el avión puede girar (su velocidad angular) dependiendo de qué tan cerca esté del próximo punto de referencia, puede lograr una curva suave.

La curva resultante no sería matemáticamente significativa ni le daría puntos de control más blandos. 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 es necesario que proporcione el conjunto completo de puntos por adelantado, simplemente puede agregar waypoints al final del conjunto según sea necesario.

Answer 5

Existen varios algoritmos para interpolar (y exrapolar) entre un conjunto de puntos aribtrary (pero final). Debería verificar numerical recipes, también incluyen implementaciones C++ de esos algoritmos.

Answer 6

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.

Adición

En presencia de datos ruidosos, el venerable RANSAC algoritmo vale la pena echarle un vistazo.

Answer 7

En el mundo de los gráficos en 3D, los NURBS son populares. Más información es fácil de googlear.

Answer 8

Deberías echar un vistazo al B-splines. Su ventaja sobre las curvas de Bezier es que cada parte solo depende de los puntos locales. Así que mover un punto no tiene efecto en partes de la curva que están muy lejos, donde "lejano" 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 arriba.

Answer 9

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
dude que tenedor ella.