math - ubicar - Forma simple de interpolar puntos en el espacio tridimensional para formar una superficie lisa

interpolacion formula

Question

Estoy tratando de encontrar una forma simple y eficiente de crear una superficie lisa que intersecte una cantidad de puntos de "muestra" dados.

Para cualquier punto X, Y en la superficie, identifico hasta 4 puntos de muestra en cada una de las 4 direcciones (los siguientes puntos más altos y más bajos en la X, y luego los ejes Y). Dado este punto, quiero una forma de calcular un valor Z que interpola entre los 4 puntos de muestra.

Por supuesto, el algoritmo, dada la posición X, Y de cualquiera de los 4 puntos de muestra, debe dar salida al valor Z para ese punto. Tenga en cuenta también que puede haber menos de 4 puntos de muestra.

Supongo que alguna función de los valores Z para los 4 puntos de muestra, de alguna manera inversamente sesgada por la distancia al punto de muestra, pero no puedo encontrar la manera de hacerlo.

¿Alguien tiene alguna idea sobre una forma simple de hacer esto?

Answer 1

Puede utilizar la interpolación bilineal / bicúbica, pero en tres direcciones (trilineal / tricúbica, respectivamente). Es bastante trivial si comprendes cómo funcionan estas formas de interpolación. Vea la interpolación tricubica en Wikipedia para más información.

Answer 2

Use catmull-rom parches

Answer 3

¿Estás buscando una interpolación de superficie o una red sería suficiente?

Para una interpolación de superficie, veo que otros han sugerido usar triangulaciones (por ejemplo, use esto: http://en.wikipedia.org/wiki/Delaunay_triangulation )

Para crear una grilla: uno de mis colegas usó la ecuación de calor ( http://en.wikipedia.org/wiki/Heat_equation ) para calcular los valores de los píxeles fuera de los puntos de muestra dados. Esto produjo superficies de terreno de aspecto extremadamente realista, y fue trivial para paralelizar.

Answer 4

Si desea una interpolación lineal simple de ese punto, entonces el valor Z del punto central es solo la media de los 4 valores Z vecinos, dado que las distancias son simétricas en Y y X.

Si las distancias no son simétricas, pero el punto central siempre está en las mismas líneas X e Y, puede calcular las interpolaciones Y y X, y el valor final es la media de esas.

Entonces Zc sería: Zc = (Zx1 + x * (Zx2-Zx1) / (x2-x1) + Zy1 + y * (Zy2-Zy1) / (y2-y1)) / 2, donde xey son distancias de x1 y y1.

Answer 5

Puedes hacer esto construyendo parches desde las splines de Catmull-Rom. Estas splines afectarán a cada uno de los puntos de control y son continuas en la primera derivada (aunque no en la segunda). También me parece que es extremadamente fácil trabajar con ellos. La matemática es directa y se comportan intuitivamente con ligeros cambios en los puntos de control.

En el nivel más alto, necesitará 16 puntos por parche (en el borde de su conjunto de datos, puede usar los puntos de esquina y borde dos veces en la misma spline).

Primero, necesitará interpolar a través de los puntos p [i] [j] en cada fila en su matriz 4x4 para crear un conjunto de cuatro puntos de control intermedios q [i] . Aquí hay un bosquejo ASCII aproximado de lo que quiero decir.

p00 p01 q0 p02 p03
p10 p11 q1 p12 p13
p20 p21 q2 p22 p23
p30 p31 q3 p32 p33

Ahora puede interpolar entre cada uno de esos cuatro puntos de control intermedios para encontrar un punto final ranurado en su superficie.

Aquí hay una construcción de la spline Catmull-Rom en cuatro puntos. En este ejemplo, está interpolando entre los puntos p [i-1] yp [i] , usando puntos de control en cualquier lado p [i-2] yp [i + 1] . u es el factor de interpolación que va de cero a uno. τ se define como la tensión en la spline y afectará la forma en que su superficie estriada se ajusta a sus puntos de control.

 | 0 1 0 0 | | p[i−2] |
|−τ 0 τ 0 | | p[i−1] |
p(u) = 1 u u2 u3 | 2τ τ−3 3−2τ −τ | | p[i] |
|−τ 2−τ τ−2 τ | | p[i+1] |

NOTA: no es inmediatamente obvio cómo establecer esto en la interfaz gráfica de usuario de , pero u2 y u3 se supone que representan u al cuadrado y en cubos , respectivamente.

Answer 6

Un problema al interpolar usando el esquema sugerido en la pregunta, en el que algún subconjunto de vecinos más cercanos se eligen de un conjunto disperso, es que el resultado no necesita ser continuo.

Piénsalo. Supongamos que debo moverme a lo largo de un camino suave y continuo a través del plano (x, y). Siempre y cuando los 4 vecinos más cercanos no cambien, el interpolador será suave, definido como lo prefiera. Sin embargo, en algún momento, ese subconjunto de vecinos más cercanos cambiará repentinamente. En ese punto, debe tener el interpolador constante a través del límite. Lo mejor es usar una triangulación del conjunto de variables independientes. Esto asegura un interpolador continuo (lineal) dentro del casco convexo de los datos. Con más trabajo, también se pueden lograr interpolaciones de orden superior con una triangulación.

Las funciones de base radial también se usan comúnmente para la interpolación, o Kriging, si te interesa la geoestadística. Como estaba buscando métodos basados ​​en distancia, considere las funciones de base radial. Por ejemplo, busque "interpolación multiquárica inversa".