[Math] Calculate corresponding coordinates

coordinate systems

I'll like to get assistance about calculating corresponding coordinates (x,y,z):
I have 2 similar shapes in the same space (shape A and shape B). The shapes contains several points on the same locations on the shape itself. I'm trying to find the corresponding coordinates between those shapes. What I have in hand is only one coordinate that I know that corresponds to each other.

For example:

In the image below we got two similar shapes in different orientations on the same space. We know that the red points (x,y,z) are corresponding to each other. The goal is to find for each other green coordinate from shape A, there corresponding coordinate from shape B.

Demonstrates the problem I'm trying to solve

Is it possible?
If not – If I'll have two "Red points" will it be possible than? How?

Thanks!

Best Answer

It looks like you're looking for an affine transformation, i.e. a function $\varphi: \Bbb R^3 \to \Bbb R^3$ such that

$$\varphi(x) = Ax + b = \begin{pmatrix} a_{11} &a_{12} &a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33} \end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} + \begin{pmatrix}b_1\\b_2\\b_3\end{pmatrix} $$

that maps every point $(x,y,z)$. Roughly speaking, matrix $A$ is responsible for rotations and scaling, and the column vector $b$ is responsible for transformations. For instance, the affine transformation that would move your shape up one unit along the $z$ axis corresponds to

$$\varphi: x \to x + \begin{pmatrix}0\\0\\1\end{pmatrix}$$

so in this case $A = I_3$ and $b = (0,0,1)^T$. The affine transformation that rotates about the $z$ axis corresponds to

$$ \varphi: x \to \begin{pmatrix}\cos(\theta)&-\sin(\theta)&0\\\sin(\theta)&\cos(\theta)&0\\0&0&1 \end{pmatrix}x. $$

Here, $b = (0,0,0)^T$.

In your case, you are given a number of inputs $(x_1,x_2,x_3)^T$ and outputs $\varphi((x_1,x_2,x_3)^T)$. You actually don't have to worry about figuring out what component of the transformation is rotation, translation or scaling. You just have to have enough given points on your shape so that you can find unique values of $A$ and $b$ that solve your problem.

Assuming a solution exists (which it should, given the nature of your problem), you will need $4$ given points to solve the problem. Call these points $w = (w_1,w_2,w_3)$, $x = (x_1,x_2,x_3)$, $y = (y_1,y_2,y_3)$ and $z = (z_1,z_2,z_3)$. Similarly, let $\varphi(w) = (w_1',w_2',w_3')$ et cetera. Multiplying the equation $\varphi(x) = Ax+b$ out, we see that

$$\tag{1} \begin{pmatrix} w_1'\\w_2'\\w_3' \end{pmatrix} = \begin{pmatrix} a_{11} &a_{12} &a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33} \end{pmatrix}\begin{pmatrix}w_1\\w_2\\w_3\end{pmatrix} + \begin{pmatrix}b_1\\b_2\\b_3\end{pmatrix} $$

This gives a system of three simultaneous equations, one in each row. The equation given by just looking at the first row looks like this:

$$ w_1' = a_{11}w_1 + a_{12}w_2 + a_{13}w_3 + b_1$$

When we plug the other three points $x$, $y$, and $z$ into the equation $\varphi(x) = Ax + b$ and just look at the first row, we get similar equations:

$$ x_1' = a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + b_1$$ $$ y_1' = a_{11}y_1 + a_{12}y_2 + a_{13}y_3 + b_1$$ $$ z_1' = a_{11}z_1 + a_{12}z_2 + a_{13}z_3 + b_1$$

Now it should be clear why we needed $4$ points. There are four unknowns: $a_{11}, a_{12}, a_{13}$ and $b_1$. The values of $x$, $y$, $z$ and $w$ (and their images $x'$, $y'$, $z'$ and $w'$) are given. So we need four linear equations in these four unknowns to find a solution. To actually find the solution, notice that this is a system of equations in four variables of the form

$$ \begin{pmatrix}w_1'\\x_1'\\y_1'\\z_1'\end{pmatrix} = \begin{pmatrix} w_1&w_2&w_3&1\\x_1&x_2&x_3&1\\y_1&y_2&y_3&1\\z_1&z_2&z_3&1\end{pmatrix}\begin{pmatrix}a_{11}\\a_{12}\\a_{13}\\b_1 \end{pmatrix} $$

which you should be able to solve for $(a_{11},a_{12},a_{13},b_1)^T$ using typical methods. If you do the same thing for the other two rows of the original matrix equation $(1)$, you can similarly find $(a_{21},a_{22},a_{23},b_2)^T$ and $(a_{31},a_{32},a_{33},b_3)^T$ . That gives you the entire affine transformation $Ax + b$.

Related Question