Minimize vertices distance between triangles

[Spiderman]

If I have two triangles in three dimensions with vertices a1,b1,c1 and a2,b2,c2, and want to overlay them such that the distance between corresponding verticies is minimized, i.e. such that the total distance between the sum of the distances between the vertices a1-a2, b1-b2 and c1-c2 are minimized, is there a way to do this other than least-squares? I need a fast method as I'm going to be doing this thousands of times in a program but I can't think of a solution that works.

 

[0rthodontist]

Are you allowed to rotate the triangles?

 

[Spiderman]

Oh yes. I want to rotate and translate one triangle so that it fits as best as possible over the other. I know ways of doing this, but they all involve too much in the way of computation. I'm sure there is a quick way but my brain won't come up with it.

 

[0rthodontist]

Well, if you're only doing it a few thousand times then speed should be a minor concern. I don't know what methods you have in mind but if you've figured out how to use least squares on this then that should be plenty fast. Do you need an exact solution or just an approximate one, something that "looks like" an okay fit? One thing is that if you can rotate the triangles, you can put them in the same plane and then use translation/rotation/reflection within the plane. If you only need an approximate solution you could make the centroids match up and then optimize by rotation/reflection about the centroid.

 

[Spiderman]

Thanks for the suggestions. I've used those techniques and they are too slow. I say a few thousand, but I suppose in actuality I mean something on the order or billions or more. Each instance of the program will currently take about 5 seconds, with maybe 10,000 triangles overlays amongst other things. If I was only running the program once, this would be sufficient, but I'm going to need to run it thousands of times. So every second I can save on a single instance would be very useful.

Currently I can use an exact method, which is slow, and an approximate method, which is pretty fast. I would like an exact method that is as fast or faster than what I have.

 

[Spiderman]

Alright. I figured it out.

for new point a_1^n

1. calculate the difference between vertices

d_1=|a_1b_1|-|a_2b_2|
d_2=|a_1c_1|-|a_2c_2|

2. a_1^n=a_2+(d_1/2*\vec{u_1})+(d_2/2*\vec{u_2})

where \vec{u_1}=a2-b2 and \vec{u_2}=a2-c2

3. repeat for other two points of triangle.