I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if you know anyone who could answer this question, please send it to them. I really need the solution as I have been trying to figure it out for quite long time :| Many thanks!

enter image description here

As can be seen in the picture, I have more than 200 lines in 3D. They consist of 3 different groups of lines, and the common property of the lines in each group is that they pass close to the same point. However, in this problem, we don't know which line belongs to which group. What is given are only the 3D coordinates $(x,y,z)$ of the 2 ends of all the lines.

My job is to find an algorithm to match/fit/register a triangle (a rigid body) to those lines such that the sum of the sum of distances between 3 vertexes of the triangle and their corresponding lines is minimized. In some cases, one vertex may be the closest point in a group, but the other vertexes would be dragged further away from their corresponding lines (because they are in a rigid body), thus this sum will not be minimal. What I need is the best positions of the 3 vertexes (the best fit of the triangle) to minimize the global sum.

In conclusion, given more than 200 sets of $(x_1,y_1,z_1,x_2,y_2,z_2)$ (which are coordinates of 2 ends of a line), I need to find the best positions of 3 vertexes of a triangle to fit in those lines (given the relative distance between the 3 vertexes).

Without the rigid-body condition, I have successfully determined the positions of the 3 independent points using the Expectation-Maximization (EM) clustering algorithm. However, sometimes 2 or 3 points are assigned to the same position. Then, I realized I had forgotten the "rigid-body" condition. With this added condition, this error will not occur. In the EM algorithm, I can derive the formula for each repositioning step for each point. But when it comes to a rigid-body, I don't know how to figure out the translation and rotation matrix to fit the triangle to the lines.

Thank you for reading this post. Your help would be greatly appreciated!

  • $\begingroup$ you seem to have a modelling problem rather than an algorithms problem. In other words, what's wrong with the following approach: use $k$-means with k=3 to find the centers, and then use the standard SVD trick to find the rigid transformation that matches the triangle to the three centers. In particular, what role are the edges of the triangle playing in this problem ? $\endgroup$ – Suresh Venkat Aug 30 '12 at 16:00
  • $\begingroup$ cross-posted on MO and MSE $\endgroup$ – Kaveh Aug 30 '12 at 21:42
  • $\begingroup$ It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). $\endgroup$ – Kaveh Aug 30 '12 at 21:43