Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving an irregular tetrahedron given 3 angles and 3 lengths

  1. May 24, 2012 #1
    Here's a picture of an irregular tetrahedron, for reference:

    Y626c.png

    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.
     
    Last edited: May 24, 2012
  2. jcsd
  3. May 25, 2012 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  4. May 29, 2012 #3
    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:

    7MAvp.png

    The variable bp is the unknown. Any idea how to do this?
     
  5. May 29, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  6. May 29, 2012 #5
    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!
     
  7. Sep 26, 2012 #6
    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.
     
  8. Sep 26, 2012 #7
    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?
     
  9. Sep 26, 2012 #8
    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?
     
  10. Sep 26, 2012 #9
    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.
     
  11. Sep 26, 2012 #10
    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!
     
  12. Sep 26, 2012 #11
    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.
     
  13. Sep 26, 2012 #12
    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.
     
  14. Sep 26, 2012 #13
    No problem. I would definitely like to hear how your project goes. Best of luck.
     
  15. Sep 27, 2012 #14
    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.
     
  16. Sep 27, 2012 #15
    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.
     
  17. Sep 27, 2012 #16
    Now I think we both need to reconstruct the tetrahedron from the same known data. Maybe later I will realise 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving an irregular tetrahedron given 3 angles and 3 lengths
  1. Deg 1 map S^3 -> RP(3) ? (Replies: 20)

Loading...