Transform a triangle to another triangle

Question

Hi i am trying to create the affine transform that will allow me to transform a triangle into another one. What i have are the coordinates for the 2 triangles. Can you help me?

Following the answer by Adam Rosenfield i came up with this code in case anyone is bored to solve the equation himself :

public static AffineTransform createTransform(ThreePointSystem source,
            ThreePointSystem dest) {        
    double x11 = source.point1.getX();
    double x12 = source.point1.getY();
    double x21 = source.point2.getX();
    double x22 = source.point2.getY();
    double x31 = source.point3.getX();
    double x32 = source.point3.getY();
    double y11 = dest.point1.getX();
    double y12 = dest.point1.getY();
    double y21 = dest.point2.getX();
    double y22 = dest.point2.getY();
    double y31 = dest.point3.getX();
    double y32 = dest.point3.getY();

    double a1 = ((y11-y21)*(x12-x32)-(y11-y31)*(x12-x22))/
                ((x11-x21)*(x12-x32)-(x11-x31)*(x12-x22));
    double a2 = ((y11-y21)*(x11-x31)-(y11-y31)*(x11-x21))/
                ((x12-x22)*(x11-x31)-(x12-x32)*(x11-x21));
    double a3 = y11-a1*x11-a2*x12;
    double a4 = ((y12-y22)*(x12-x32)-(y12-y32)*(x12-x22))/
                ((x11-x21)*(x12-x32)-(x11-x31)*(x12-x22));
    double a5 = ((y12-y22)*(x11-x31)-(y12-y32)*(x11-x21))/
                ((x12-x22)*(x11-x31)-(x12-x32)*(x11-x21));
    double a6 = y12-a4*x11-a5*x12;
    return new AffineTransform(a1, a4, a2, a5, a3, a6);
}

Answer 1

I'm going to assume you're talking about 2D here. An affine transformation matrix has 9 values in it:

    | a1 a2 a3 |
A = | a4 a5 a6 |
    | a7 a8 a9 |

There are 3 input vertices x1, x2, and x3, which when transformed should become y1, y2, y3. However, since we're working in homogeneous coordinates, applying A to x1 doesn't necessarily give y1 -- it gives a multiple of y1. So, we also have the unknown multipliers k1, k2, and k3, with the equations:

A*x1 = k1*y1
A*x2 = k2*y2
A*x3 = k3*y3

Each of those is a vector, so we really have 9 equations in 12 unknowns, so the solution is going to be underconstrained. If we require that a7=0, a8=0, and a9=1, then the solution will be unique (this choice is natural, since it means if the input point is (x, y, 1), then the output point will always have homogeneous coordinate 1, so the resulting transform is just a 2x2 transform plus a translation).

Hence, this reduces the equations to:

a1*x11 + a2*x12 + a3 = k1*y11
a4*x11 + a5*x12 + a6 = k1*y12
                   1 = k1
a1*x21 + a2*x22 + a3 = k2*y21
a4*x21 + a5*x22 + a6 = k2*y22
                   1 = k2
a1*x31 + a2*x32 + a3 = k3*y31
a4*x31 + a5*x32 + a6 = k3*y32
                   1 = k3

So, k1 = k2 = k3 = 1. Plugging these in and converting to matrix form yields:

| x11 x12   1   0   0   0 |   | a1 |   | y11 |
| x21 x22   1   0   0   0 |   | a2 |   | y21 |
| x31 x32   1   0   0   0 | * | a3 | = | y31 |
|   0   0   0 x11 x12   1 |   | a4 |   | y12 |
|   0   0   0 x21 x22   1 |   | a5 |   | y22 |
|   0   0   0 x31 x32   1 |   | a6 |   | y32 |

Solving this 6x6 system of equations yields you your affine transformation matrix A. It will have a unique solution if and only if the 3 points of your source triangle are not collinear.

Answer 2

Hey, guys, Without Loss of Generality, make the two triangles have the origin as one vertex (you can tack on the affine shift later), so they're defined by the points 0, a, b, c, d then multiply your points x by the matrix NM

where

M = inverse(a b) <--- this is 2x2 matrix with the points a and b as its columns

and

N = (c d)

That should do it.

Answer 3

If I understand this correctly, your triangles have the same size and angles, so you should be able to tranform them so that they have (at least) one point in common. After this, they should only differ in rotation or could be mirrored, so you could f.e. get the angles between the triangle lines and try these for rotation and could mirror one of the triangles if none of the angles works.

EDIT: OK, that's not enough, affine transformations also can contain shear and scaling... Scaling could be done easily, just divide the length of the lines, this will also give you some information about corresponding lines of the triangles, but shearing will be harder...

OTOH, couldn't you just solve some equation system for this? After all, there should be a transformation matrix and 3 points (new and old)...

Answer 4

Just formule the problem as a set of equations and then solve it:

P1 * M = P1'
P2 * M = P2'
P3 * M = P3'

M is a 3x3 matrix like:

[m00, m01, m02;
 m10, m11, m12;
 0  ,   0,   1]

And P_i is a tuple [k*x_i, k*y_i, k] (homogeneous coordinates)...

You can now try to expand the 3 matricial equations shown above and make a new system, with the m_ij as incognits and solve it, but if I'm not missing something (and maybe I am), you need one point more to specify completely the transformation, or otherwise you'll have an extra degree of freedom (and of course you can fix it).