Calculating a 2D Transformation Matrix from an Initial and Resultant 2D Matrix

Question

I by no means profess to be a genius when it comes to programming and my current problem has me stumped.

I have found this question Trying to derive a 2D transformation matrix using only the images that seems to at least partially answer my question but the image that should show the solution is no longer available :S

I'm working in C# and not using WPF as neither my input or output needs to be displayed graphically.

In my program I have 2 quadrilaterals, lets call them an input and an output quadrilateral.

The input quad has the co-ords of (2,1),(2,3),(4,4),(3,1) from bottom left clockwise.

The output quad can have any co-ords and will be again listed in order from bottom left clockwise.

Given these 8 co-ordinate pairs, is it possible to calculate a transformation matrix that I could apply to any single co-ordinate pair?

I'm not too hot on Matrices but I am willing to learn if pointed in the right direction.

Many Thanks

Josh

Answer 1

A quick google or a hop, skip and a google found this. I think it will definitely solve your problem.

As I mentioned in comment, you are asking for an isomorphic function to project a single point within a quadrilateral to a point in a second quadrilateral. Rather than work it out manually I've found the below algorithm.

Posting the algorithm here for posterity:

Let p00, p10, p11,and p01 be the vertices of the first quadrilateral listed in counterclockwise order.

Let q00, q10, q11,and q01 be the vertices of the second quadrilateral listed in counterclockwise order.

Define P10 = p10-p00, P11 = p11-p00, P01 = p01-p00, Q10 = q10-q00, Q11 = q11-q00, and Q01 = q01-q00.

Compute a and b so that Q11 = aQ10 + bQ01.

This is a set of two linear equations in two unknowns.

Similarly, compute c and d so that P11 = cP10 + dP01.

It turns out that a >= 0, b >= 0, a + b> 1, c >= 0, d >= 0,and c + d> 1.

Any point p in the quadrilateral can be written as p =(1-x-y)p00 + xp10 + yp01 where x = 0, y = 0,(1 - d)x + c(y - 1) = 0, and d(x - 1)+(1 - c)y = 0.

Any point q in the quadrilateral can be written as q =(1-u-v)q00 + uq10 + vq01 where u = 0, v = 0,(1 - b)u + a(v -1) = 0, and b(u - 1) + (1 - a)v = 0.

The perspective mapping relating (u,v) to (x,y) is u = m0x n0 + n1x + n2y and v = m1y n0 + n1x + n2y where m0 = ad(1 - c - d), m1 = bc(1 - c - d), n0 = cd(1 - a - b), n1 = d(a - c + bc - ad),and n2 = c(b - d - bc + ad).

Effectively the p-quadrilateral is mapped to a “standard” one, <(0, 0),(1, 0),(0, 1),(c,d)>

and the q-quadrilateral is mapped to <(0, 0),(1, 0), (0, 1), (a,b)>.

The (x,y) to (u,v) mapping relates these two.

You can verify that

• (x,y)=(0, 0) is mapped to (u,v)=(0, 0)

• (x,y)=(1, 0) is mapped to (u,v)=(1, 0)

• (x,y)=(0, 1) is mapped to (u,v)=(0, 1)

• (x,y)=(c,d) is mapped to (u,v)=(a,b)

I'm going to give another answer that describes how I'd solve the example in the comments - this answer is getting too long.