Algoritmo para Interpolación 2D

Question

Tengo dos formas que son secciones transversales de un canal. Quiero calcular la sección transversal de un punto intermedio entre los dos puntos definidos. ¿Cuál es el algoritmo más simple (relativamente simple?) Para usar en esta situación?

P.S .: Me encontré con varios algoritmos como el vecino natural y poisson, que parecía complejo. Estoy buscando una solución simple, que pueda implementarse rápidamente.

EDIT: He quitado la palabra "más simple" del título, ya que podría ser engañoso

Answer 1

Esto es simple:

1. En cada sección transversal dibujar N puntos a intervalos uniformemente espaciados a lo largo de la frontera de la sección transversal.
2. dibujar líneas rectas desde el punto n-ésimo en sección transversal 1 hasta el punto n-ésimo en sección transversal 2.
3. Quítate la sección transversal nuevo a la distancia deseada entre las viejas secciones transversales.

Más simple aún:

1. Utilice una de las secciones transversales existentes sin modificaciones.

Supongo que esta segunda sugerencia es demasiado simple, pero apuesto a que nadie sugiere una más simple.

EDITAR siguiente comentario de OP: (demasiado para una re-comentario)

Bueno, pediste un método sencillo! No estoy seguro de ver el mismo problema con el primer método que tú. Si las secciones transversales no son demasiado extrañas (probablemente sea mejor si son polígonos convexos) y no hace nada extraño, como mapear el lado izquierdo de una sección transversal al lado derecho del otro (forzando así muchas líneas cruzadas)) entonces el método debería producir algún tipo de sección transversal sensible. En el caso de que sugiera un triángulo y un rectángulo, supongamos que el triángulo está sentado en su base, un vértice en la parte superior. Haga un mapa que señale, por ejemplo, la esquina superior izquierda del rectángulo, luego proceda en la misma dirección (en sentido horario o antihorario) alrededor de los límites de ambas secciones transversales uniendo los puntos correspondientes. No veo ninguna línea de cruce, y veo una forma bien definida a cualquier distancia entre las dos secciones transversales.

Answer 2

Tenga en cuenta que hay algunas ambigüedades sobre las respuestas de High Performance Mark que probablemente necesitará abordar y definirá la calidad de la salida de su método. El más importante es que, al dibujar los puntos n en ambas secciones transversales, qué tipo de correspondencia determinas entre ellos, es decir, si lo haces de esa forma sugirió High Performance Mark, entonces el orden de etiquetado de los puntos se vuelve importante .

Sugiero un plano rotativo (ortogonal) simultáneamente a través de ambas secciones transversales, entonces el conjunto de puntos que cruzan ese plano en una sección transversal solo necesita coincidir con el conjunto de puntos que intersectan ese plano en la otra sección transversal. Hipotéticamente, no hay límite en el número de puntos en estos conjuntos, pero ciertamente reduce la complejidad del problema de correspondencia en la situación original.

Answer 3

Aquí hay otro intento en el problema, que creo que es un intento mucho mejor.

Dadas las dos secciones transversales C_1, C_2

Coloque cada C_i en un marco de referencia global con el sistema de coordenadas (x,y) de modo que la forma en que están situados relativamente tiene sentido. Divida cada C_i en una curva superior e inferior U_i y L_i. La idea será que desee deformar continuamente la curva U_1 a U_2 y L_1 a L_2. (Nota se puede extender este método para dividir cada C_i en m curvas si lo desea.)

La manera de hacer esto es como sigue. Para cada T_i = U_i, or L_i muestra n puntos, y determine el polinomio de interpolación P{T_i}(x). Como se señala debidamente a continuación, los polinomios de interpolación son susceptibles de oscilación, especialmente en los puntos extremos. En lugar del polinomio de interpolación, uno puede usar el polinomio de ajuste de mínimos cuadrados que sería mucho más robusto. A continuación, defina la deformación del polinomio P{U_1}(x) = a_0 + a_1 * x + ... + a_n * x^n-P{U_2}(x) = b_0 + b_1 * x + ... + b_n * x^n como Q{P{U_1},P{U_2}}(x, t) = (t * a_0 + (1 - t) b_0) + ... + (t * a_n + (1-t) * b_n) * x^n donde la deformación Q se define sobre 0<=t<=1 donde t define momento en el que la deformación es al (es decir, en t=0 estamos en U_2 y en t=1 estamos en U_1 y en cualquier otro t estamos en alguna deformación continua de los dos.) Lo mismo ocurre con Q{P{L_1},P{L_2}}(x, t). Estas dos deformaciones le construyen una representación continua entre las dos secciones transversales que puede muestrear en cualquier t.

Tenga en cuenta que todo lo que realmente se hace es interpolar linealmente los coeficientes de los polinomios de interpolación de las dos piezas de ambas secciones transversales. Tenga en cuenta también que, al dividir las secciones transversales, probablemente debería poner la restricción de que deben dividirse en los puntos finales que coinciden, de lo contrario, puede tener "agujeros" en su deformación.

Espero que eso esté claro.

edición: se abordó la cuestión de la oscilación en polinomios de interpolación.