How to transform arbitrary rectangle into specific parallelogram?

Question

I have a rectangle $S$ in $(u,v)$ coordinates. $S = [a,b] \times [c,d]$.

I want to find the transformation that yields a parallelogram given by $(0,0),(-2,1),(2,4),(4,3)$. I have deduced this is equivalent to

$$\bigg\lbrace (x,y) \bigg | \text{area bounded by } y = -\frac{1}{2}x, y = \frac{3}{4} x ,y = \frac{3}{4} x + \frac{5}{2}, y = -\frac{1}{2}x + 5\bigg\rbrace$$

I'm sure I'm doing this the hard way. But my intinct was there are four steps to do it.

1. Translate the rectangle to the origin
2. Resize the edges
3. Shear it
4. Rotate it

So if $$\begin{bmatrix} u \\ v \\ \end{bmatrix} \in S$$

Translation: $$T = \begin{bmatrix} -a \\ -c \\ \end{bmatrix}$$

Rescale:

$$A_1 = \begin{bmatrix} \frac{\gamma}{b-a} & 0 \\ & \frac{5}{d-c} \end{bmatrix}$$

Shear: $$A_2 = \begin{bmatrix} 1 & -\frac{1}{2} \\ 0 & 1 \end{bmatrix}$$

Rotation: $$R = \begin{bmatrix} 4/5 & -3/5 \\ 3/5 & 4/5 \end{bmatrix}$$

So then the transformation would look like

$$ \begin{bmatrix} x \\ y \\ \end{bmatrix} = RA_2A_1\bigg(\begin{bmatrix} u \\ v \\ \end{bmatrix} +T\bigg)$$

However, I can't figure out what $\gamma$ should be for the rescaling. Can anyone help?

Answer 1

After trial and error, I found that

Translation: $$T = \begin{bmatrix} -a \\ -c \\ \end{bmatrix}$$

Rescale:

$$A_1 = \begin{bmatrix} \frac{5}{b-a} & 0 \\ & \frac{2}{d-c} \end{bmatrix}$$

Shear: $$A_2 = \begin{bmatrix} 1 & -\frac{1}{2} \\ 0 & 1 \end{bmatrix}$$

Rotation: $$R = \begin{bmatrix} 4/5 & -3/5 \\ 3/5 & 4/5 \end{bmatrix}$$

Example

$S = [10,20] \times [0,2]$ and suppose we consider the point $ \begin{bmatrix} 20 \\ 2 \\ \end{bmatrix}$

$$\begin{bmatrix} 2 \\ 4 \\ \end{bmatrix} = R A_2 A_1 \bigg ( \begin{bmatrix} 20 \\ 2 \\ \end{bmatrix} + \begin{bmatrix} -10 \\ 0 \\ \end{bmatrix}\bigg )$$

Answer 2

To answer your immediate question, $\gamma = 2$. You’re scaling the translated rectangle so that it has the same shape as the desheared parallelogram. Since you’ll be shearing parallel to the $x$-axis, you want the width of the scaled rectangle to equal the length of the paralellogram’s base, and the rectangle’s height should be equal to the paralellogram’s height (not its other edge length). [Note that you’ve gotten these two dilation factors swapped in your question, but corrected that in your own answer.] A simple way to compute this latter distance is to divide its area by its base length: $$\gamma = {\begin{vmatrix}4&3\\-2&1\end{vmatrix}\over\sqrt{4^2+3^2}} = \frac{10}5 = 2.$$

That aside, it’s convenient when working with affine transformations to use homogeneous coordinates so that translations can be included in the now $3\times3$ transformation matrix. (Depending on one’s point of view, this is either a cheap mathematical trick or reflects an important connection between the projective plane and Euclidian three-dimensional space.) The matrix that corresponds to the translation is, in block form, $$\left[ \begin{array}{c|c} I_2 & T \\ \hline 0&1 \end{array} \right]$$ and the complete transformation is $$\begin{bmatrix}x\\y\\1\end{bmatrix} \left[ \begin{array}{c|c} RA_2A_1 & RA_2A_1T \\ \hline 0&1 \end{array} \right] = \begin{bmatrix}u\\v\\1\end{bmatrix}.$$ This may not seem like much of an advantage over $2\times2$ matrices and a separate vector for the translation, but by turning an affine transformation of the plane into a linear transformation of 3-D space, this representation allows you to compute the complete transformation entirely mechanically in the following way:

For any pairing of the vertices of two triangles in the plane, there is a unique affine transformation that maps between them. Thus, we only need to consider three of the four vertex pairs here; linearity of the map ensures that the fourth pair will be mapped correctly. A linear transformation is completely determined by its action on a basis. In fact, relative to that basis the columns of its matrix are the images of the basis vectors. Therefore, if $\mathbf p_1$, $\mathbf p_2$ and $\mathbf p_3$ are the homogeneous coordinates of three of the rectangle’s vertices and $\mathbf q_1$, $\mathbf q_2$, $\mathbf q_3$ the corresponding parallelogram vertices, the required mapping is $$\begin{bmatrix}\mathbf q_1 & \mathbf q_2 & \mathbf q_3\end{bmatrix} \begin{bmatrix} \mathbf p_1 & \mathbf p_2 & \mathbf p_3 \end{bmatrix}^{-1}.$$ The left-hand matrix maps from the standard basis to the parallelogram, and the right-hand matrix maps from the rectangle to the standard basis. If neither the rectangle nor the parallelogram is degenerate, then both of these matrices are nonsingular. For the example in your answer, this is $$\begin{bmatrix}0 & 4 & -2 \\ 0 & 3 & 1 \\ 1&1&1 \end{bmatrix} \begin{bmatrix} 10 & 20 & 10 \\ 0 & 0 & 2\\ 1&1&1 \end{bmatrix}^{-1} = \begin{bmatrix} \frac25 & -1 & -4 \\ \frac3{10} & \frac12 & -3 \\ 0&0& 1 \end{bmatrix},$$ which corresponds to the mapping $$\begin{bmatrix}x\\y\end{bmatrix} = \begin{bmatrix}\frac25&-1\\\frac3{10}&\frac12\end{bmatrix}\begin{bmatrix}u\\v\end{bmatrix}-\begin{bmatrix}4\\3\end{bmatrix}.$$

Of course, you could skip all of this matrix stuff and work out an affine mapping directly as it’s just bilinear interpolation. Let $\lambda = (u-a)/(b-a)$ and $\mu = (v-c)/(d-c)$. Then $(x,y)^T = (1-\lambda-\mu)\mathbf P_1+\lambda\mathbf P_2+\mu\mathbf P_3$, where $\mathbf P_1\mathbf P_2$ is the side of the paralellogram that is the image of the lower edge of the rectangle and $\mathbf P_1\mathbf P_3$ is the image of the left side. This corresponds to a different decomposition of the full transformation matrix: $$\begin{bmatrix}\mathbf P_2-\mathbf P_1 & \mathbf P_3-\mathbf P_1 & \mathbf P_1 \\ 0&0&1\end{bmatrix} \begin{bmatrix}(b-a)^{-1}&0&0\\0&(d-c)^{-1}&0\\0&0&1\end{bmatrix} \begin{bmatrix}1&0&-a\\0&1&-c\\0&0&1\end{bmatrix}.$$ Computing this will likely be more efficient than the matrix inversion above. Comparing this to your decomposition, the stretch of the unit square to match the paralellogram, the shear and the rotation have been consolidated into a single matrix that maps the unit square onto the paralellogram. The product of the other two matrices maps the source rectangle onto the unit square, which you can verify be setting $\mathbf P_1=(0,0)^T$, $\mathbf P_2 = (1,0)^T$ and $\mathbf P_3=(0,1)^T$ (which makes the left-hand matrix the identity).

Note that this isn’t the only affine map of the rectangle to the parallelogram. There are eight possible such maps, four that preserve orientation and four that change it.