Como mapear um ponto dentro de uma grade deformada

Question

Digamos que você tenha uma coleção de pontos com coordenadas em um sistema de coordenadas cartesianas.

Você quer traçar um outro ponto, e você sabe suas coordenadas no mesmo sistema de coordenadas cartesianas.

No entanto, o enredo que você está aproveitando está distorcida do original. Imagine tomar o avião original, imprimi-lo em uma folha de borracha, e esticá-lo em alguns lugares e beliscar-lo nos outros, de forma assimétrica (sem sobreposição ou algo complexo).

( fonte )

Você conhece as coordenadas esticadas e não esticados de cada um de seu conjunto de pontos, mas não a função de estiramento subjacente. Você conhece as coordenadas não esticados de um novo ponto.

Como você pode estimar onde traçar o novo ponto nas coordenadas esticadas baseados nas posições esticadas de pontos próximos? Ele não precisa ser exato, desde que você não pode determinar a função trecho real de um conjunto de pontos remapeadas menos que você tenha mais informações.

outras palavras-chave possíveis: deformado avião malha grade distorcida coordenar unwarp

Answer 1

Ok, então isso soa como deformação da imagem. Isto é o que você deve fazer:

1. Criar um Delaunay triangulação de sua grade unwarped e usar seu conhecimento do correspondências entre o deformado e grade unwarped para criar a triangulação para a rede deformado. Agora você sabe os triângulos correspondentes em cada imagem e já que não há sobreposição, você deve ser capaz de realizar o próximo passo sem muita dificuldade.

2. Agora, para encontrar o A ponto correspondente, na imagem distorcida:

   1. Encontre as mentiras triângulo A em e usar a transformação entre o triângulo na grade unwarped ea grade transportado para descobrir a nova posição.

Isto é explicado de forma explícita em detalhes aqui .

Outro método (muito mais complicado) é o fina Placa Spline (que também é explicado nas lâminas acima).

Answer 2

Eu entendi que você tem correspondência de um-para-um entre os pontos da grade embrulhadas e desembrulhadas. E suponho que a deformação não é tão extrema que você pode ter que se cruzam as linhas de grade (como a imagem que mostram).

A estratégia é exatamente o que Jacob sugere: Triangulate a duas grades de tal forma que há uma correspondência de um-para-um entre triângulos, localize o ponto a ser mapeada na triangulação e, em seguida, usar coordenadas baricêntricas no triângulo correspondente para calcular o nova localização do ponto.

Preprocess

1. Gerar o Delaunay triangulação dos pontos da grade embrulhado, vamos chamá-lo WT.
2. Para cada triângulo no WT adicionar um triângulo entre os vértices correspondentes na grade desembrulhados. Isto dá uma UWT triangulação dos pontos desembrulhados.

Mapear uma p ponto na rede embrulhado

1. Encontre o T(p1,p2,p3) triângulo no UWT que contém p.
2. Calcule o barycentric coordenadas (b1,b2,b3) de p em T(p1,p2,p3)
3. Let Tw(q1,q2,q3) ser o triângulo no WT correspondente a T(p1,p2,p3). A nova posição é
   b1 * q1 + b2 * q2 + b3 * q3.

Observações Isto dá uma função de deformação como uma linear ranhura . Para mais suave comportamento pode-se usar o mesmo triangulação, mas fazê maior aproximação ordem o que levaria a um pouco de computação mais complicado em vez das coordenadas baricêntricas.

Answer 3

As outras respostas são grandes. A única coisa que eu gostaria de acrescentar é que você pode querer dar uma olhada livre forma deformação como um modo de descrever as deformações.

Se isso for útil, então é bem possível para caber uma grade de deformação / rede a seus pares conhecidos, e então você tem um método muito rápido de deformar pontos futuras.

Answer 4

Muita coisa depende de quantos pontos já existentes que você tem. Se você tiver apenas um, não há realmente muito que você pode fazer com ele - você pode compensar o segundo ponto pela mesma quantidade no mesmo sentido, mas você não tem dados suficientes para realmente fazer melhor do que isso.

Se você tem um bom número de pontos existentes, você pode fazer um ajuste de superfície através desses pontos, e usar isso para aproximar a posição adequada do novo ponto. N pontos dadas, você sempre pode obter um ajuste perfeito usando uma ordem N polinomial, mas você raramente querem fazer isso - em vez disso, você geralmente acho que a função de estiramento é uma função bastante baixa ordem (por exemplo, quadrática ou cúbica) e ajuste uma superfície para os pontos nessa base. Você, então, colocar o seu novo ponto baseada na função para a sua superfície equipada.