Minimize vertices distance between triangles

  • Context: Graduate 
  • Thread starter Thread starter Spiderman
  • Start date Start date
  • Tags Tags
    Triangles
Click For Summary

Discussion Overview

The discussion revolves around minimizing the distance between corresponding vertices of two triangles in three-dimensional space through rotation and translation. Participants explore methods for achieving this minimization efficiently, particularly in the context of a program that requires rapid computations for potentially billions of triangle overlays.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant inquires about methods to minimize the distance between triangle vertices beyond least-squares, emphasizing the need for speed due to high computational demands.
  • Another participant asks whether rotation of the triangles is permitted, which is confirmed by the original poster.
  • The original poster expresses familiarity with existing methods but finds them computationally intensive, seeking a faster alternative.
  • A suggestion is made to consider approximate solutions, such as aligning centroids and optimizing through rotation or reflection, but the original poster indicates these methods are still too slow for their needs.
  • The original poster clarifies that they currently have both an exact but slow method and a faster approximate method, expressing a desire for a faster exact method.
  • A later post presents a proposed method involving calculating differences between vertices and adjusting the positions of the triangle's vertices based on these differences.

Areas of Agreement / Disagreement

Participants do not reach a consensus on a specific method for minimizing vertex distances, and multiple approaches are discussed without resolution on which is optimal for the stated requirements.

Contextual Notes

The discussion highlights the trade-off between computational speed and the accuracy of the vertex alignment methods, with participants acknowledging the need for efficiency in the context of large-scale computations.

Spiderman
Messages
7
Reaction score
0
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.
 
Mathematics news on Phys.org
Are you allowed to rotate the triangles?
 
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.
 
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.
 
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.
 
Alright. I figured it out.

for new point [tex]a_1^n[/tex]

1. calculate the difference between vertices

[tex]d_1=|a_1b_1|-|a_2b_2|[/tex]
[tex]d_2=|a_1c_1|-|a_2c_2|[/tex]

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

where [tex]\vec{u_1}=a2-b2[/tex] and [tex]\vec{u_2}=a2-c2[/tex]

3. repeat for other two points of triangle.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 1 ·
Replies
1
Views
4K
  • · Replies 14 ·
Replies
14
Views
3K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 6 ·
Replies
6
Views
4K
  • · Replies 1 ·
Replies
1
Views
2K