Affine transformation

I am trying to solve the below problem. I don't have much knowledge in Affine transformations. Could someone help me answer this q开发者_C百科uestion:

Find a 3x3 matrix representing a 2D affine transformation of homogeneous coordinates (i.e. every point [x,y] is represented as a column vector [x, y, 1]), which transforms a square [0,0],[1,0],[1,1],[0,1] into a parallelogram [0,1],[1,1],[2,2],[1,2].

---

Things I spotted about this question
1) You need to understand homogeneous co-ordinates
2) You need to know the difference between row and column major - read here
3) You need to know the basic affine transformations - rotate, scale/shear and translate and how to represent them in a matrix - read this page

Interestingly, I think the answer only needs a translate and a shear ( no rotation ).
Looking at the source and dest points, it looks like all dest points are translated +1 in y and sheared by 1 in X ( to give the parallelogram, probably best to draw it out to see what I mean )

So start with a 3 * 3 identity matrix which is

1 0 0
0 1 0
0 0 1

The shear will be
1 1 0
0 1 0
0 0 1

The translate will be
1 0 0
0 1 1
0 0 1

So putting it all together should be

1 1 0
0 1 1
0 0 1

I don't normally use column major so probably worth double checking!

Hope that helps

---

An affine transformation is a transformation of the form x ⟼ Ax + b, where x and b are vectors, and A is a square matrix. Geometrically, affine transformations map parallelograms to parallelograms and preserve relative distances along lines.

To solve a problem like this, we first note that for the origin, we have 0 ⟼ A0 + b = b. Since the problem tells us that [0,0] ⟼ [0,1], we know that b = [0,1].

Next we recall from linear algebra that multiplying a matrix by the standard basis vectors [0,1] and [1,0] simply extracts the first and second columns of the matrix, respectively:

[a b] [1] = [a],  [a b] [0] = [b].
[c d] [0]   [c]   [c d] [1]   [d]

We are given that [1,0] ⟼ [1,1] and [0,1] ⟼ [1,2]. From this we obtain

[1,1] = A[1,0] + b = [a,c] + [0,1] ⟹ [a,c] = [1,0],
[1,2] = A[0,1] + b = [b,d] + [0,1] ⟹ [b,d] = [1,1].

This gives us our affine transformation

Ax + b = [1 1] x + [0].
         [0 1]     [1]

Homogeneous coordinates are a trick which let us write affine transformations as matrices, just with one extra coordinate that is always set to 1. The matrix formula is

[A b] [x] = [Ax+b].
[0 1] [1]   [   1]

Here A is actually a 2×2 matrix, while b and x are 2-vectors, and the 0 in the bottom left is really [0 0]. So overall, we are dealing with a 3×3 matrix and 3-vectors.

So our solution is

[1 1 0]
[0 1 1],
[0 0 1]

and for good measure we check that it works properly for the final point:

[1 1 0] [1]   [2]
[0 1 1] [1] = [2].
[0 0 1] [1]   [1]

---

You'll have read the Wikipedia page on the subject, of course.

Once upon an aeon or so ago, I read Foley and van Dam in one of the predecessor versions (this would have been 1983 or 1984), and it covered techniques for manipulating 2D and 3D coordinates with augmented matrices and vectors as described in the question. However, enough time has lapsed since then that I've forgotten all the details (and no longer have the book--too many moves of house). There was also a book by Newman and Sproul, I seem to remember.

A = [ a  b  c ]    B = [ 0  1  1  0 ]   C = [ 0  1  2  1 ]
    [ d  e  f ]        [ 0  0  1  1 ]       [ 1  1  2  2 ]
    [ g  h  1 ]        [ 1  1  1  1 ]       [ 1  1  1  1 ]

The columns of B represent the corners of the square; the columns of C represent the corners of the parallelogram; and the matrix equation A x B = C has to be solved. IIRC, the matrix A has a 1 in the bottom right corner; it is possible that the values c, f, g, and h also have presecribed values (they'd probably be zeroes). The non-zero values apply a linear (affine) transform, scaling, shearing and rotating the input shape.

You'd need to look for similar information in a text book. Or in the Wiki page - I didn't look hard at it (the information above is working from ancient memory).

---

I just wanted to point out that four points over constrain a 2D affine transformation. In the comment of Jonathan Leffler, you can see this from the fact that you would need to invert a non-square matrix. So, either choose three of the points or set up a least-squares system. The over-constrained, least-squares solution could be solved with the following matrices

A = [ a  b  c ]    B = [ 0  1  1  0 ]   C = [ 0  1  2  1 ]
    [ d  e  f ]        [ 0  0  1  1 ]       [ 1  1  2  2 ]
    [ g  h  1 ]        [ 1  1  1  1 ]       [ 1  1  1  1 ]

so that solving using the normal equations gives

A B = C
(A B)^T = B^T A^T = C^T
B B^T A^T = B C^T
A^T = (B B^T)^-1 B C^T

undoing that transpose gives

A =  ((B B^T)^-1 B C^T)^T