Ponto Sequence interpolação

Question

Dada uma seqüência arbitrária de pontos no espaço, como você produzir uma interpolação suave e contínuo entre eles?

soluções 2D e 3D são bem-vindos. Soluções que produzem uma lista de pontos na granularidade arbitrária e soluções que os pontos de controle produzir para curvas bezier também são apreciados.

Além disso, seria legal ver uma solução iterativa que poderia aproximar seções iniciais da curva, uma vez que recebeu os pontos, então você pode desenhar com ele.

Answer 1

O Catmull-Rom ranhura é garantido para passar através de todos os pontos de controle. Eu acho que isso seja mais acessível do que tentando ajustar os pontos de controle intermediários para outros tipos de estrias.

Este PDF por Christopher Twigg tem um breve introdução agradável para a matemática da spline. A melhor frase resumo é:

estrias Catmull-Rom tem C1 continuidade, controle local, e interpolação, mas não se encontram dentro o casco convexo de seu controle pontos.

Dito de outra forma, se os pontos indicam uma curva acentuada para a direita, o spline vai margem esquerda antes de virar para a direita (há uma imagem exemplo nesse documento). A tensão dessas voltas em controlável, neste caso usando o parâmetro tau no exemplo da matriz.

Aqui está outro exemplo com algum código DirectX download.

Answer 2

Uma maneira é Lagrange polinominal , que é um método para produzir um polinômio que vai através de todos os pontos de dados fornecidos.

Durante o meu primeiro ano na universidade, eu escrevi uma pequena ferramenta para fazer isso em 2D, e você pode encontrá-lo neste página , é chamado de Lagrange solver. página do Wikipedia também tem uma implementação de exemplo.

Como funciona é assim: você tem um polinômio de ordem n, p(x), onde n é o número de pontos que você tem. Tem a forma a_n x^n + a_(n-1) x^(n-1) + ...+ a_0, onde _ é subscrito, ^ é potência. Você, então, transformar isso em um conjunto de equações simultâneas:

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

Você converter o acima em uma matriz aumentada, e resolver para o a_0 ... a_n coeficientes. Então você tem um polinômio que passa por todos os pontos, e agora você pode interpolar entre os pontos.

Nota no entanto, isso pode não atender a sua finalidade, uma vez que não oferece nenhuma forma de ajustar a curvatura etc -. Você está preso com uma única solução que não pode ser mudado

Answer 3

Você deve dar uma olhada B-splines . Sua vantagem sobre curvas de Bezier é que cada parte é somente dependente pontos locais. Então, movendo-se um ponto não tem efeito sobre as partes da curva que estão longe, onde "longe" é determinada por um parâmetro do spline.

O problema com o polinômio Langrange é que a adição de um ponto pode ter efeitos extremos em partes aparentemente arbitrárias da curva; não há "localness", como descrito acima.

Answer 4

Você olhou para o Unix ranhura de comando? que pode ser coagido a fazer o que você quer?

Answer 5

Existem vários algoritmos para interpolação (e exrapolating) entre um aribtrary (mas final) conjunto de pontos. Você deve verificar se numérica receitas , eles também incluem implementações destes algoritmos C ++.

Answer 6

Infelizmente, o Lagrange ou outras formas de interpolação polinomial não vai funcionar em um conjunto arbitrário de pontos. Eles só funcionam em um conjunto, onde em uma dimensão por exemplo x

x _i i + 1

Para um conjunto arbitrário de pontos, por exemplo, um caminho de vôo de avião, onde cada ponto é um par (longitude, latitude), você vai ser melhor fora simplesmente modelando a viagem do avião com longitude atual & latitude e velocidade. Ao ajustar a velocidade com que o avião pode virar (sua velocidade angular) dependendo de como próximo é para o próximo waypoint, você pode conseguir uma curva suave.

A curva resultante não seria matematicamente significativa nem dar-lhe pontos de controle de Bezier. No entanto, o algoritmo seria computacionalmente simples, independentemente do número de pontos de passagem e poderia produzir uma lista interpolada de pontos na granularidade arbitrária. Também não seria necessário que você fornecer o conjunto completo de pontos na frente, você pode simplesmente adicionar pontos de passagem para a final do conjunto, conforme necessário.

Answer 7

Eu vim com o mesmo problema e implementou com alguns amigos no outro dia. Eu gostaria de compartilhar o projeto de exemplo no github.

https://github.com/johnjohndoe/PathInterpolation
Sinta-se livre para forquilha-lo.

Answer 8

Google "regressão ortogonal".

Considerando que as técnicas de mínimos quadrados para tentar minimizar a distância vertical entre a linha de ajuste e cada f (x), de regressão ortogonal minimiza as distâncias perpendiculares.

Adenda

Na presença de dados ruidosos, o venerável RANSAC algoritmo é vale a pena conferir também.

Answer 9

No mundo gráficos 3D, NURBS são populares. Mais informações é facilmente pesquisei.