Cómo mapear un punto en una cuadrícula deformada

Question

Supongamos que tiene una colección de puntos con coordenadas en un sistema de coordenadas cartesiano.

Desea trazar otro punto y conoce sus coordenadas en el mismo sistema de coordenadas cartesianas.

Sin embargo, la trama que está dibujando está distorsionada del original. Imagine tomar el plano original, imprimirlo en una lámina de goma, estirarlo en algunos lugares y pellizcarlo en otros, de forma asimétrica (sin superposición o algo complejo).

( fuente )

Usted conoce las coordenadas estiradas y no estiradas de cada uno de sus conjuntos de puntos, pero no la función de estiramiento subyacente. Conoces las coordenadas sin estirar de un nuevo punto.

¿Cómo puede estimar dónde trazar el nuevo punto en las coordenadas estiradas en función de las posiciones estiradas de los puntos cercanos? No es necesario que sea exacto, ya que no puede determinar la función de estiramiento real a partir de un conjunto de puntos reasignados a menos que tenga más información.

otras palabras clave posibles: deformado deformado malla malla plano coordenada no deformado

Answer 1

Ok, entonces esto suena como distorsión de imagen. Esto es lo que debes hacer:

1. Cree una triangulación de Delaunay de su cuadrícula sin envergadura y utilice su conocimiento de la correspondencias entre la cuadrícula deformada y no deformada para crear la triangulación para la cuadrícula deformada. Ahora conoce los triángulos correspondientes en cada imagen y, dado que no hay superposición, debería poder realizar el siguiente paso sin mucha dificultad.

2. Ahora, para encontrar el punto correspondiente A , en la imagen deformada:

   1. Encuentre el triángulo A y use la transformación entre el triángulo en la cuadrícula sin distorsión y la cuadrícula combada para averiguar la nueva posición.

Esto se explica explícitamente en detalle aquí .

Otro método (mucho más complicado) es el Splin Plate Spline (que también se explica en las diapositivas de arriba).

Answer 2

Comprendí que tienes una correspondencia uno a uno entre los puntos de la cuadrícula envueltos y sin envolver. Y asumo que la deformación no es tan extrema como para que pueda tener líneas de cuadrícula que se cruzan (como la imagen que muestra).

La estrategia es exactamente lo que sugiere Jacob: Triangule las dos cuadrículas de modo que haya una correspondencia uno a uno entre los triángulos, ubique el punto a ser mapeado en la triangulación y luego use las coordenadas baricéntricas en el triángulo correspondiente para calcular el nueva ubicación del punto.

Preproceso

1. Genere la Delaunay triangulation de los puntos de la cuadrícula envuelta, llamémosla WT .
2. Para cada triángulo en WT , agregue un triángulo entre los vértices correspondientes en la cuadrícula desenvuelta. Esto le da una triangulación UWT de los puntos no envueltos.

Asigne un punto p a la cuadrícula envuelta

1. Encuentre el triángulo T (p1, p2, p3) en el UWT que contiene p .
2. Calcule las coordenadas barcéntricas (b1, b2, b3) de p en T(p1,p2,p3)
3. Sea Tw (q1, q2, q3) el triángulo en WT correspondiente a T (p1, p2, p3) . La nueva posición es
   b1 * q1 + b2 * q2 + b3 * q3 .

Comentarios Esto proporciona una función de deformación como spline lineal . Para un comportamiento más suave, se podría usar la misma triangulación, pero hacer una aproximación de orden superior que llevaría a un cálculo un poco más complicado en lugar de las coordenadas baricéntricas.

Answer 3

Las otras respuestas son geniales. Lo único que agregaría es que es posible que desee echar un vistazo a Deformación de forma libre como una forma de describir las deformaciones.

Si eso es útil, entonces es muy posible ajustar una rejilla / enrejado de deformación a tus pares conocidos, y luego tienes un método muy rápido de deformar puntos futuros.

Answer 4

Mucho depende de cuántos puntos existentes tengas. Si solo tiene uno, no hay mucho que pueda hacer con él: puede compensar el segundo punto por la misma cantidad en la misma dirección, pero no tiene suficientes datos para hacerlo mejor que eso.

Si tiene un buen número de puntos existentes, puede hacer un ajuste superficial a través de esos puntos, y usarlo para aproximarse a la posición correcta del nuevo punto. Dados N puntos, siempre puede obtener un ajuste perfecto utilizando un polinomio de orden N, pero rara vez desea hacerlo; en cambio, generalmente adivina que la función de estiramiento es una función de orden bastante bajo (por ejemplo, cuadrática o cúbica) y se ajusta una superficie a los puntos sobre esa base. Luego, coloque su nuevo punto en función de la función para su superficie ajustada.