Solving an irregular tetrahedron given 3 angles and 3 lengths

[murrdpirate0]

Here's a picture of an irregular tetrahedron, for reference:

The base triangle (ABC) is completely known (lengths AB, AC, BC, and the angles between them are all known). The 3 angles at vertex P are also known (APB, APC, and BPC).

I believe that is enough information to completely solve the rest of the lengths and angles. I used the law of sines and the 180 degree constraint for each of the 3 unknown triangles. With a bit of algebra I can get 3 equations with 3 unknowns, but they're too messy for me to solve.

If anyone can figure this out, I'd greatly appreciate it.

 

[haruspex]

The obvious equations are the cosine rule, producing 3 quadratic equations in the three unknowns. Eliminating one unknown between two of these produces a quartic. Eliminating the second gives an 8th power polynomial. Is that what you did?
I doubt there's an easier way.

 

[murrdpirate0]

I actually was using the sine rule instead of the cosine rule, but the cosine rule seems like it might be a more direct way to go about this. I can get an equation with a single unknown pretty easily, however it seems very difficult to actually write this equation in terms of the unknown, as shown below:

The variable bp is the unknown. Any idea how to do this?

 

[haruspex]

That looks even worse than the 8th power polynomial I was expecting. Can't remember how I deduced that. But even if you got to that, you would only be able to solve it numerically. So you might as well do that with the equation you have.
Is there a practical end to this, or is it just theory?

 

[murrdpirate0]

There is indeed a practical end to this; I'm working on some triangulation-based positioning. This will be a calculation that is constantly repeated on a microcontroller, perhaps every second, so an analytic solution would have been nice, but it is not required.

Haruspex, I do appreciate your replies even if I can't get an analytic solution. I'm not a mathematician, so it's given me confidence to drop the attempt at an analytic solution and just get the iterative approach done. Thanks!

 

[torchfire]

I'm facing exactly the same mathematical problem now. I've been trying so long but I haven't been able to find the analytical solution so far. I need the solution for a practical use, for position and orientation finding just as you needed it for.

Have you ever found the analytical solution?

Please, let me know.

 

[murrdpirate0]

Sort of. It is helpful to know that the problem is called the 'three dimensional resection problem.' You'll find much more information with that term.

I've read that analytical solutions do exist, but they take just as long or longer than iterative techniques. Applying the Newton-Raphson iteration method to the 3 Law of Cosines equations seems to work pretty well. Note that while 3 known points works over 99% of the time, there are some instances where two solutions are possible. You will need either a 4th point to guarantee a single correct solution or some other means to obtain both solutions and choose the correct one.

Can I ask what your application is?

 

[torchfire]

Awesome! Thank you so much!

I'm involved in a project in which we build a head-tracking system for a visualisation laboratory. There are infrared cameras placed on the ceiling, forming a grid. The spectator of the screen is wearing 3 LEDs on her/his head, the LEDs are forming a known triangle. It's always ensured that 1 camera sees the LEDs. Maybe we will apply a 4th LED to gain a single solution.

Can you give me titles of books dealing with this problem or webpage links?

 

[murrdpirate0]

I'm glad to help. For the insane amount of time I spent on this, it's nice to at least get some use of it it. That sounds like a cool project.

I did encounter a method that wasn't quite suited for my application, but sounds like it could be exactly what you need. It's called the POSIT algorithm. It's for finding the position and orientation of an object within a camera's filed of view. Do you have any experience with OpenCV? Apparently the POSIT algorithm is available there. You can read about the OpenCV implementation here, which also includes a link to the paper describing the algorithm: http://opencv.willowgarage.com/wiki/Posit

Apparently it does require 4 non-coplanar points, but that doesn't sound like it should be an issue for you.

 

[torchfire]

I'm counting the pure time spent on the problem in days :) I've used tons of pages trying to solve the problem from different approaches.

I have never used OpenCL before but I'm very happy that an algorithm I could use is already implemented in an open program library. I haven't read yet the whole article DeMenthon & Davis wrote. But I've seen they are using somekind of iterations.

Maybe I will never use an analytical solution, but it's unbearable for me to not knowing about one. Please if you remember where you read about analytical solutions, let me know the source.
Of course I could also search on the 'three dimensional resection problem', but I think I wouldn't find very quickly what I'm searching for. I mean I mainly want to know the solution for this irregular tetrahedron problem.

Thanks in advance!

 

[murrdpirate0]

I believe a book called 'Algebraic Geodesy and Geoinformatics' describes a few analytic approaches. However I have to say I don't think there are any benefits in going with an analytic approach. The iterative approach I used can be accurate to like 10 decimal places and it takes less than a millisecond to calculate on my laptop. From what I've read, the analytic solutions are actually slower. The angles to the LEDs that you measure with the cameras will have far more error than the errors produced by an iterative solution. Seriously, don't go down the analytic route! Save yourself before it's too late!

OpenCV is a very popular computer vision library. You might find other useful functions there. But I have seen C++ code for the POSIT algorithm if you don't want to jump into OpenCV yet. Can't remember where I saw it, but I'm sure you could find it pretty easily.

 

[torchfire]

I'm grateful for showing me the way and giving advices. Maybe your answers will help for other people too.

I will write about my experiences as soon as possible.

 

[murrdpirate0]

No problem. I would definitely like to hear how your project goes. Best of luck.

 

[torchfire]

I'm wondering how you found out that maximum 2 solutions are possible. Can you give me an insight? I haven't found anyting about the number of solutions on the net or in the 'Algebraic Geodesy and Geoinformatics' book.
However I built a paper modell before to visualise the problem and I was never able to find more than 2 solutions for a given set of angles.

 

[murrdpirate0]

Well, I think your problem is slightly different from mine. Mine is the resection problem, where you calculate your position based on the angles you measure from your unknown location to known points.

I think your problem might be more accurately described as the triangulation problem, where you measure the position of points away from you, based on the angles you measure from a known position. Perhaps you won't ever have 2 solutions with three angles in this case, I'm not sure. But the fact that the POSIT algorithm requires 4 points makes me think that you could have 2 solutions otherwise.

The existence of a second solution may not be obvious. I drew many sketches in AutoCAD trying to figure how there could be two solutions, and it didn't seem like there could be. But when I actually went about calculating, I did find that ~0.03% of the time there were two solutions. They seemed to only occur when the position was very close to a known point, and the calculation would end up saying I was next to the known point at the opposite end.

 

[torchfire]

Now I think we both need to reconstruct the tetrahedron from the same known data. Maybe later I will realize that there's a difference indeed.

I have found something about the number of solutions in the 'Algebraic Geodesy and Geoinformatics' book after all. On page 233 it's written, that

x2 + y2 - 2 xy cos(\alpha) = Konst1
y2 + z2 - 2 yz cos(\beta) = Konst2
z2 + x2 - 2 zx cos(\gamma) = Konst3

system of equations has at most four positive solutions if x > 0, y>0, z > 0 (I hope there's nothing wrong with my interpretation. I haven't used the same notations as the book used).

But I think that the problem can have more than 2 solutions only in very special cases (2 measured angles are equivalent, the base triangle is isoscale - maybe even this case hasn't got 4 solutions, I just imagined it).

Thanks a lot for sharing your experiences. 0.03% is low enough.