Neste artigo, falarei sobre uma fórmula incomum que permite examinar um novo ângulo sobre transformações afins e, especialmente, sobre os problemas inversos que surgem em conexão com essas transformações. Vou chamar problemas inversos que exigem o cálculo da matriz inversa: encontrar a transformação por pontos, resolver um sistema de equações lineares, transformar coordenadas ao alterar a base etc. Farei uma reserva imediatamente de que não haverá descobertas fundamentais no artigo, nem uma redução na complexidade algorítmica - mostrarei simplesmente uma fórmula simétrica e fácil de lembrar com a qual você pode resolver inesperadamente muitos problemas em execução. Para os amantes do rigor matemático, há uma apresentação mais formalizada aqui [1] (orientada para os alunos) e um pequeno livro de problemas aqui [2] .

A transformação afim é geralmente definida pela matriz $$$A$ e vetor de tradução e atua no argumento do vetor pela fórmula

$$

$$\ mathcal {A} (\ vec {x}) = \ hat {A} \ vec {x} + \ vec {t}.$$

No entanto, você pode fazer sem $$$\ vec {t}$ se você usar a matriz aumentada e as coordenadas uniformes para o argumento (como é bem conhecido dos usuários do OpenGL). Entretanto, além dessas formas de escrita, você também pode usar o determinante de uma matriz especial, que contém as coordenadas do argumento e os parâmetros que determinam a transformação. O fato é que o determinante tem a propriedade de linearidade sobre os elementos de qualquer linha ou coluna, e isso permite que ele seja usado para representar transformações afins. Aqui, de fato, como expressar a ação da transformação afim em um vetor arbitrário $$$\ vec {x}$ :


Não se apresse em fugir com horror - primeiro, aqui está escrita uma transformação que atua em espaços de dimensão arbitrária (existem tantas coisas daqui) e, segundo, embora a fórmula pareça complicada, ela é simplesmente lembrada e usada. Para começar, destacarei os elementos logicamente relacionados com quadros e cores


Então vemos que a ação de qualquer transformação afim $$$\ mathcal {A}$ por vetor pode ser representado como a razão de dois determinantes, com o argumento do vetor inserindo apenas a parte superior e a parte inferior é apenas uma constante, dependendo apenas dos parâmetros.

Vetor destacado azul $$$\ vec {x}$ É um argumento, o vetor no qual a transformação afim atua $$$\ mathcal {A}$ . A seguir, os subscritos denotam o componente do vetor. Na matriz superior dos componentes $$$\ vec {x}$ ocupam quase a primeira coluna inteira, exceto por eles nesta coluna apenas zero (em cima) e um (embaixo). Todos os outros elementos da matriz são vetores de parâmetros (eles são numerados pelo sobrescrito, entre colchetes para não confundir com o grau) e unidades na última linha. Entre o conjunto de todas as transformações afins, os parâmetros distinguem o que precisamos. A conveniência e a beleza da fórmula é que o significado desses parâmetros é muito simples: eles definem uma transformação afim que traduz vetores $$$\ vec {x} ^ {\, (i)}$ em $$$\ vec {X} ^ {(i)}$ . Portanto vetores $$$\ vec {x} ^ {\, (1)}, \ pontos, \ vec {x} ^ {\, (n + 1)}$ , chamaremos de "entrada" (eles são cercados por retângulos na matriz) - cada um deles é escrito componente-componente em sua própria coluna, uma unidade é anexada abaixo. Os parâmetros de "saída" são escritos de cima (destacados em vermelho) $$$\ vec {X} ^ {(1)}, \ pontos, \ vec {X} ^ {(n + 1)}$ , mas agora não componente a componente, mas como uma entidade inteira.

Se alguém for surpreendido por esse registro, lembre-se do produto vetorial

$$$$ display $$ [\ vec {a} \ times \ vec {b}] = \ det \ begin {pmatrix} \ vec {e} _1 & \ vec {e} _2 & \ vec {e} _3 \\ a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ \ end {pmatrix}, $$ display $$

onde havia uma estrutura muito semelhante e a primeira linha da mesma maneira era ocupada por vetores. Além disso, não é necessário que as dimensões dos vetores $$$\ vec {X} ^ {(i)}$ e $$$\ vec {x} ^ {(i)}$ coincidiu. Todos os determinantes são considerados como de costume e permitem os "truques" comuns, por exemplo, você pode adicionar outra coluna a qualquer coluna.

Com a matriz inferior, tudo é extremamente simples - é obtido a partir do topo excluindo a primeira linha e a primeira coluna. A desvantagem de (1) é que você precisa levar os determinantes; no entanto, se você transferir essa tarefa de rotina para um computador, a pessoa precisará preencher apenas as matrizes corretamente com os números de sua tarefa. Ao mesmo tempo, usando uma fórmula, você pode resolver alguns problemas comuns da prática:

• encontrar uma transformação afim por pontos;
• cálculo de coordenadas baricêntricas;
• interpolação multilinear;
• problemas de transformação linear (sem tradução):
  
  • inversão matricial;
  • A regra de Cramer em uma fórmula (não, o que você viu não está em uma fórmula);
  • recálculo das coordenadas do vetor quando a base muda;
  • interpolação por polinômios de Lagrange.

Transformação afim de três pontos em um plano

Sob a influência de uma transformação afiada desconhecida, três pontos no avião passaram para os outros três pontos. Encontre esta transformação afim.
Por definição, deixe nossos pontos de entrada


e o resultado da transformação

Encontre a transformação afim $$$\ mathcal {A}$ .

De fato, esse problema pode ser resolvido de diferentes maneiras: usando um sistema de equações lineares, coordenadas baricêntricas ... mas seguiremos nosso próprio caminho. Eu acho que pela notação usada, você pode adivinhar o que eu estou falando: tomamos a equação (1) para a dimensão $$$n = 2$ e substituto $$$\ vec {x} ^ {\, (i)}$ como parâmetros de entrada e $$$\ vec {X} ^ {\, (i)}$ - como um fim de semana


e então resta apenas calcular os determinantes


Um olho treinado detectará facilmente uma ligação $$$30 ^ {\ circ}$ e transmitido em $$$((3 + \ sqrt {3}) / 2, 2) ^ {\ mathsf {T}}$ .

Quando a fórmula é aplicável?

Os vetores de entrada e saída podem ter dimensões diferentes - a fórmula é aplicável a transformações afins que atuam em espaços de qualquer dimensão. No entanto, deve haver pontos de entrada suficientes e eles não devem "ficar juntos": se a transformação afiada agir de $$$n$ tridimensional - os pontos devem formar um simplex não degenerado de $$$n + 1$ pontos. Se essa condição não for atendida, é impossível restaurar inequivocamente a transformação (por qualquer método, não apenas isso) - a fórmula avisará sobre isso por zero no denominador.

Por que restaurar uma transformação afim em um programador?

Muitas vezes, você precisa encontrar uma transformação entre duas fotos (para calcular a posição da câmera, por exemplo). Se tivermos alguns pontos especiais confiáveis ​​(recursos) nessas imagens, ou se você simplesmente não quiser começar imediatamente com ranzaks e lutar com gastos, essa fórmula pode ser usada.

Outro exemplo é a texturização . Cortar um triângulo de uma textura e puxá-lo para um triângulo em algum lugar de um avião ou no espaço é uma tarefa típica para aplicar a transformação afim em pontos de um espaço de textura, convertendo-os no espaço onde os modelos vivem. E, muitas vezes, é fácil para nós indicar quais pontos da textura correspondem aos vértices do triângulo do modelo, mas estabelecer para onde vão os pontos que não são de canto pode exigir alguma reflexão. Com a mesma fórmula, basta inserir os números nas células corretas e haverá tanta beleza.

Pelo que tive de enfrentar pessoalmente: a rede neural fornece as coordenadas dos cantos do marcador e queremos “complementar a realidade” com um objeto virtual localizado no marcador.
Obviamente, ao mover o marcador, o objeto deve repetir todos os seus movimentos. E aqui a fórmula (1) é muito útil - ela nos ajudará a mover o objeto após o marcador.

Ou outro exemplo: você precisa programar a rotação de vários objetos no palco usando a ferramenta gizmo. Para fazer isso, precisamos poder rotacionar o modelo selecionado em torno de três eixos paralelos aos eixos de coordenadas e passando pelo centro do objeto. A figura mostra o caso de rotação do modelo em torno de um eixo paralelo ao $$$Oz$ .

Em última análise, tudo se resume ao problema bidimensional de rotação em torno de um ponto arbitrário. Vamos até resolvê-lo para um caso simples, digamos, ativando $$$90 ^ \ circ$ anti-horário ao redor $$$(a; b)$ (o caso geral é resolvido da mesma maneira, não quero desorganizar os cálculos com senos e cossenos). Obviamente, você pode seguir o caminho do samurai e multiplicar três matrizes (translação do ponto de rotação para zero, na verdade rotação e translação de volta), ou também pode encontrar as coordenadas de quaisquer três pontos antes e depois da rotação e usar a fórmula. O primeiro ponto é fácil - já sabemos que $$$(a; b)$ entra em si mesmo. Vamos olhar para o ponto um à direita, pois é verdade $$$(a + 1; b) \ mapsto (a; b + 1)$ . Bem, e mais um abaixo, é óbvio que $$$(a; b-1) \ mapsto (a + 1; b)$ . Então tudo é simples

Coordenadas bariêntricas

Decompomos o determinante superior (1) ao longo da primeira linha, de acordo com a regra de Laplace. É claro que, como resultado, obtemos uma soma ponderada de vetores $$$\ vec {X} ^ {(i)}$ . Acontece que os coeficientes nessa soma são as coordenadas barentêntricas do argumento $$$\ vec {x}$ em relação ao simplex dado $$$\ vec {x} ^ {\, (i)}$ (para provas ver [1] ). Se estivermos interessados ​​apenas nas coordenadas baricêntricas de um ponto, podemos trapacear e preencher a primeira linha com orts unitários - depois de calcular os determinantes, obtemos um vetor cujos componentes coincidem com as coordenadas baricêntricas $$$\ vec {x}$ . Graficamente, essa conversão $$$\ mathcal {B}$ traduzir um ponto no espaço de suas coordenadas baricêntricas terá a seguinte aparência


Vamos tentar esta "receita" na prática. Tarefa: encontre as coordenadas baricêntricas de um ponto em relação a um determinado triângulo. Que seja um ponto de certeza $$$(2,2) ^ \ mathsf {T}$ e pegue os vértices de um triângulo


O ponto é pequeno - leve (1) para $$$n = 2$ , coloque corretamente os dados da tarefa e calcule os determinantes


Aqui está a solução: coordenadas barricêntricas $$$(2,2) ^ \ mathsf {T}$ em relação a um dado triângulo existe $$ , $$$0,3$ e $$$0,1$ . Na programação, o cálculo das coordenadas barcentricadas geralmente surge no contexto de verificar se um ponto está dentro de um simplex (todas as coordenadas baricêntricas são mais que zero e menos que a unidade), bem como para várias interpolações, que discutiremos agora.

Observe que a fórmula (1) possui uma agradável dualidade: se expandirmos o determinante na primeira coluna, obtemos a notação padrão para a função afim e, na primeira linha, obtemos a combinação afim de vetores de saída.

Interpolação multilinear

Assim, descobrimos que a transformação afim pesa os vetores de saída com coeficientes iguais às coordenadas barentêntricas do argumento. É natural usar essa propriedade para interpolação multilinear.

Interpolação de cores

Por exemplo, vamos calcular o GL padrão - o “olá mundo” - um triângulo colorido. Obviamente, o OpenGL sabe perfeitamente como interpolar cores e também faz isso usando coordenadas baricêntricas , mas hoje faremos isso sozinhos.

Tarefa: nos vértices do triângulo, as cores são definidas para interpolar as cores dentro do triângulo. Por definição, deixe que os vértices de nosso triângulo tenham coordenadas


Atribuímos a eles cores: amarelo, ciano e magenta


Os triplos numéricos são os componentes RGB de uma cor. Pegue (1) e organize corretamente os dados de entrada


Aqui estão os componentes $$$\ mathcal {C} (x; y)$ indicar como pintar um ponto $$$(x, y)$ em termos de RGB. Vamos ver o que aconteceu.

Podemos dizer que acabamos de fazer uma transformação afim do espaço bidimensional de uma imagem em espaço tridimensional de cores (RGB).

Interpolação normal (sombreamento Phong)

Podemos colocar uma variedade de significados nos vetores que interpolamos, incluindo aqueles que podem ser vetores normais. Além disso, é exatamente isso que o sombreamento Phong faz, somente após a interpolação os vetores precisam ser normalizados. O porquê dessa interpolação é necessária é bem ilustrado pela imagem a seguir (extraída da Wikipedia commons.wikimedia.org/w/index.php?curid=1556366 ).

Acho que não vale mais a pena fazer cálculos - todos os detalhes são discutidos em [2] , mas mostrarei uma imagem com o resultado.

Os vetores nele não são únicos e, para uso no sombreamento de Phong, devem primeiro ser normalizados e, para maior clareza, são direcionados em direções muito diferentes, o que raramente é o caso na prática.

Encontrar avião $$$z = z (x, y)$ em três pontos

Considere outro exemplo incomum da aplicação da transformação afim.
Três pontos são dados

Encontramos a equação do avião passando por eles na forma $$$z = z (x, y)$ . E faremos isso com a ajuda de transformações afins: afinal, sabe-se que elas traduzem aviões em planos. Para começar, projetamos todos os pontos no avião $$$Xy$ isso é fácil. E agora vamos estabelecer uma transformação afim que traduz as projeções dos pontos nos pontos tridimensionais originais


e que "pega" junto com os pontos e o avião inteiro $$$Xy$ tanto que, após a transformação, passará pelos pontos de interesse para nós.

Como sempre, só precisamos distribuir os números entre os elementos das matrizes


Reescreva a última expressão na forma usual


e desenhe o que aconteceu.

Transformações lineares

Apesar da importância prática das transformações afins, muitas vezes é preciso lidar com as lineares. Obviamente, transformações lineares são um caso especial de transformações afins, deixando um ponto no lugar $$$\ vec {0}$ . Isso nos permite simplificar um pouco a fórmula (afinal, uma das colunas consistirá em quase apenas zeros e você poderá expandir o determinante)


Como você pode ver, a última linha com unidades e uma coluna está ausente na fórmula. Esse resultado é completamente consistente com nossas idéias de que, para especificar uma transformação linear, basta indicar seu efeito sobre $$$n$ elementos linearmente independentes.

Transformação linear de três pontos

Vamos resolver o problema para ver como tudo funciona. Problema: sabe-se que sob a ação de alguma transformação linear


Encontramos essa transformação linear.

Adotamos uma fórmula simplificada e colocamos os números corretos nos lugares certos:


Feito!

Encontrando a Transformação Inversa

Lembre-se de que a matriz de transformação linear


contém imagens de vetores de unidades em suas colunas:


Então, atuando como uma matriz nos vetores unitários, obtemos suas colunas. E a transformação inversa (digamos que exista)? Faz tudo "vice-versa":


Espere um minuto, porque acabamos de encontrar as imagens de três pontos sob a influência de uma transformação linear - o suficiente para restaurar a própria transformação!


onde $$$\ vec {e} _1 = (1; 0; 0) ^ \ mathsf {T}$ , $$$\ vec {e} _2 = (0; 1; 0) ^ \ mathsf {T}$ e $$$\ vec {e} _3 = (0; 0; 1) ^ \ mathsf {T}$ .

Não nos limitaremos ao espaço tridimensional e reescreveremos a fórmula anterior de uma forma mais geral

Como você pode ver, precisamos atribuir à matriz à esquerda uma coluna com os componentes do argumento do vetor, no topo - uma linha com vetores de coordenadas e, então, é apenas a capacidade de tomar determinantes.

Problema de Transformação Inversa

Vamos tentar o método fornecido na prática. Tarefa: inverter a matriz


Usamos (2) para $$$n = 3$


É imediatamente claro que

Regra de Cramer em uma fórmula

Desde a escola, somos confrontados com equações da forma


Se a matriz $$$\ hat {A}$ degenerado, a solução pode ser escrita como


Hmm ... não é na seção anterior que eu vi a mesma expressão, mas sim $$$b$ foi outra carta? Nós vamos usá-lo.

Isso não é outro senão a regra de Cramer . Isso pode ser facilmente verificado expandindo o determinante na primeira linha: cálculo $$$x_i$ apenas assume que atravessamos a coluna com $$$\ vec {e} _i$ e com isso $$$i$ Coluna Matrix $$$\ hat {A}$ . Agora, se você reorganizar a coluna $$$b$ em vez da remota, obtemos a regra "inserir coluna $$$b$ no lugar $$$i$ Th coluna e encontre o determinante. " E sim, com os sinais, está tudo bem: sozinho $$$\ pm$ geramos ao expandir ao longo da linha, enquanto outros ao reorganizar - como resultado, eles se cancelam.

Observando com mais atenção a equação obtida, percebe-se sua semelhança com a equação para encontrar coordenadas bariêntricas: resolver um sistema de equações lineares é encontrar as coordenadas bariêntricas de um ponto $$$\ vec {b}$ em relação a um simplex, um dos vértices dos quais $$$\ vec {0}$ e o restante é definido pelas colunas da matriz $$$\ hat {A}$ .

Solução de um sistema de equações lineares

Resolvemos o sistema de equações lineares


Em forma de matriz, parece com isso


Usamos a fórmula resultante


de onde vem a resposta $$$x = 1/25$ , $$$y = 14/25$ e $$$z = 2/5$ .

Transformação de coordenadas de vetor ao alterar a base

Suponha que escolhemos uma nova base (mudamos para um sistema de coordenadas diferente). Sabe-se que as novas coordenadas dos vetores são expressas através da antiga linearmente. Portanto, não é de surpreender que possamos usar nossas ferramentas para mudar a base. Como fazer isso, vou mostrar com um exemplo.

Então, vamos passar da base padrão $$$\ {\ vec {e} _x, \ vec {e} _y \}$ para uma base que consiste em vetores


Na base antiga, um vetor é especificado $$$\ vec {x} = (3,4) ^ \ mathsf {T}$ . Encontre as coordenadas deste vetor em uma nova base. No novo sistema de coordenadas, os vetores da nova base se tornarão orts e terão coordenadas


a seguir, os traços próximos às colunas significam que as coordenadas nelas se referem a uma nova base. É fácil adivinhar que uma transformação linear que traduz


também converte as coordenadas do nosso vetor, conforme necessário. Resta apenas aplicar a fórmula


A solução do problema da maneira usual requer inversão de matriz (que, no entanto, também consiste principalmente no cálculo de determinantes) e multiplicação


Acabamos de compilar essas etapas em uma fórmula.

Por que a fórmula funciona para problemas inversos?

A eficácia da fórmula na solução de problemas inversos é explicada pela seguinte igualdade (a prova está em [1] )


Assim, a fórmula oculta em si a matriz inversa e a multiplicação por outra matriz em adição. Essa expressão é a solução padrão para o problema de encontrar uma transformação linear por pontos. Observe que, ao criar a segunda matriz na identidade do produto, obtemos apenas a matriz inversa. Com sua ajuda, um sistema de equações lineares e os problemas que podem ser reduzidos são resolvidos: encontrando coordenadas baricêntricas, interpolação por polinômios de Lagrange, etc. No entanto, a representação na forma de um produto de duas matrizes não nos permite obter os "dois olhares" associados à expansão na primeira linha e na primeira coluna.

Interpolação de Lagrange e suas propriedades

Deixe-me lembrá-lo de que a interpolação de Lagrange está encontrando o menor número de polinômios que passam pelos pontos $$$(a_0; b_0)$ , $$$(a_1; b_1)$ , $$$\ dots$ , $$$(a_n; b_n)$ . Não que fosse uma tarefa comum na prática de programadores, mas vejamos de qualquer maneira.

Como os polinômios e as transformações lineares estão relacionados?

O fato é que o polinômio


pode ser considerado como uma transformação linear que exibe o vetor $$$(x ^ n; x ^ {n-1}; \ pontos; 1) ^ T$ em $$$\ mathbb {R}$ . Então o problema de interpolação de pontos $$$(a_0; b_0)$ , $$$(a_1; b_1)$ , $$$\ dots$ , $$$(a_n; b_n)$ reduz a encontrar uma transformação tão linear que


e somos capazes de fazer isso. Substitua as letras corretas nas células corretas e obtenha a fórmula


A prova de que esse será o polinômio de Lagrange (e não de outra pessoa) pode ser encontrada em [1] . A propósito, a expressão no denominador é o identificador de Vandermonde. Sabendo disso e expandindo o determinante no numerador ao longo da primeira linha, chegamos a uma fórmula mais familiar para o polinômio de Lagrange.

Problema no polinômio de Lagrange

É difícil de usar? Vamos tentar as forças do problema: encontre o polinômio de Lagrange passando pelos pontos $$$(- 1; 2)$ , $$$(3; 4)$ e $$$(2; 7)$ .

Substitua esses pontos na fórmula


No gráfico, tudo ficará assim.

Propriedades do polinômio de Lagrange

Tendo apresentado o determinante superior na primeira linha e na primeira coluna, observamos o polinômio de Lagrange de dois lados diferentes. No primeiro caso, obtemos a fórmula clássica da Wikipedia e, no segundo, escrevemos o polinômio na forma da soma dos monômios $$$\ alpha_i x ^ i$ onde


E agora podemos provar com relativa facilidade declarações bastante complexas. Por exemplo, em [2] foi provado em uma linha que a soma dos polinômios básicos de Lagrange é igual a um e que o polinômio de Lagrange interpola $$$(a_0; a_0 ^ {n + 1})$ , $$$\ dots$ , $$$(a_n; a_n ^ {n + 1})$ tem valor zero $$$(- 1) ^ {n} a_0 \ cdot \ cdots \ cdot a_n$ . Bem, nem um único Lagrange - uma abordagem semelhante pode ser aplicada à interpolação por seno-cossenos ou algumas outras funções.

Conclusão

Obrigado a todos que leram até o fim. Neste artigo, resolvemos problemas padrão usando uma fórmula não padrão. Eu gostei porque, em primeiro lugar, mostra que transformações afins (lineares), coordenadas baricêntricas, interpolação e até polinômios de Lagrange estão intimamente relacionados. Afinal, quando as soluções para os problemas são escritas da mesma maneira, o pensamento de sua afinidade surge por si só. Em segundo lugar, na maioria das vezes, simplesmente organizamos os dados de entrada nas células corretas, sem transformações adicionais.

As tarefas que consideramos também podem ser resolvidas por métodos bastante familiares. No entanto, para problemas de pequena dimensão ou tarefas educacionais, a fórmula pode ser útil. Além disso, ela parece bonita para mim.

Referências

[ 1] Guia do iniciante para mapear simplexes com afinidade

[ 2] Pasta de trabalho sobre o mapeamento simplex de afins