CODEWITHSUNDEEP
mathgeometrytransformationaffinetransform
kazimpal
kazimpal

Reputation: 300

Similarity transform between two triangles

I have two 2D triangles (ie. they both lie in the plane), and would like to find the similarity transform (rotation + scale + translation) that maps one of them most closely onto the other one.

The two triangles are NOT actually similar so I just want the transformation to align them as best as possible.

I know I can create an affine transform between the two triangles which will map one exactly onto the other, but I don't want the shearing effect which is present in affine transforms. I want my transform to be composed only of translations, rotations, and scaling.

Any idea how to do this?

Upvotes: 5

Views: 1824

Answers (2)

Alec Jacobson
Alec Jacobson

Reputation: 6264

Suppose you have corners of two triangles with centroids at the origin in correspondence vᵢ,uᵢ∈ℝ² for i=1,2,3.

You'd like to find a similarity transform that minimizes the squared differences between the corresponding corners:

min ½ ∑ᵢ ‖ [a -b;b a] vᵢ - uᵢ ‖² a,b

we can rewrite this as

min ½ ∑ᵢ ‖ a I vᵢ + b R vᵢ - uᵢ ‖² a,b

where R=[0 -1;1 0] is the 90° rotation matrix

Expanding this out we have:

min ∑ᵢ ½ a²‖vᵢ‖² + ½ b²‖Rvᵢ‖² + abvᵢᵀR vᵢ - avᵢᵀuᵢ + bvᵢᵀRᵀuᵢ + const a,b

Subtituting RᵀR = I, we see that the squared terms share the same coefficient ∑ᵢ ‖vᵢ‖² and we can drop the cross term because xᵀRx=0 for any x.

min ½ ∑ᵢ ‖vᵢ‖² a² + ½ ∑ᵢ ‖vᵢ‖² b² - a ∑ᵢ vᵢᵀuᵢ - b ∑ᵢ vᵢᵀRᵀuᵢ a,b

Differentiating with respect to a and b and setting to zero, we have

a = ∑ᵢ vᵢᵀuᵢ / ∑ᵢ ‖vᵢ‖² b = ∑ᵢ vᵢᵀRᵀuᵢ / ∑ᵢ ‖vᵢ‖²

If the centroids are not at the origin then we can find an optimal translation t assuming we know the optimal a,b:

min ½ ∑ᵢ ‖ [a -b;b a] vᵢ + t - uᵢ ‖² t

t = ∑ᵢuᵢ / 3 - ∑ᵢ [a -b;b a] vᵢ / 3

Plugging this back in, we can find a,b as above but working with vectors of each triangles centroid instead of the corners.

While we're at it, the optimal rotation [cos(θ) sin(θ);-sin(θ) cos(θ)] is given by simply stripping off the scale of the optimal similarity transform:

tan(θ) = (∑ᵢ vᵢᵀRᵀuᵢ) / (∑ᵢ vᵢᵀuᵢ)

which we can compute robustly using atan2.

Finally, I guess if you don't know the correspondences you could just try all 6 combinations and take the best one.

Upvotes: 1

Shahbaz
Shahbaz

Reputation: 47493

Defining similarity is not an easy task, but here are a few ideas you can play with. Say you want to transform triangle A (almost) to triangle B

  • Scale: Scale triangle A by area(B)/area(A)
  • Transformation: Transform triangle A by such a vector that makes both triangle centroids to match.
  • Rotation: Use an optimization method to choose a value in range [0, 360) for rotation that meets your personal similarity criteria.

The rotation part is probably the most difficult. A simple yet effective idea would be to apply hill climbing starting from three points and taking the best. The three points are the amount of rotation needed to put one of the points of A on each of the points of B.

The similarity criterion itself is also not easy. One thing that comes to mind is the amount of overlapping surface after the transformation. Computing this is not easy or at least is cumbersome.

Upvotes: 2

Related Questions