1
$\begingroup$

Please, how is the equation system below named exactly (to search further literature)? Does it have an analytical solution? If it doesn't, then what could be the fastest numerical method for it (preferrably, with some available C++ implementation)? All the big letters (A, ... , I) are known values.

$(A*x-B*y)^{2}+(C*x-D*y)^{2}+(x-y)^{2}=G$ $(A*x-E*z)^{2}+(C*x-F*z)^{2}+(x-z)^{2}=H$ $(E*z-B*y)^{2}+(F*z-D*y)^{2}+(z-y)^{2}=I$

BTW it is related to inverse-projecting a 3D triangle based on the screen image + knowing the triangle's edges. Intuitively (maybe I'm wrong), it should have 2 answers (x,y,z). And if it helps somehow, I actually only need the values of $(x-y)/(C*x-D*y)$

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I'm not sure such equations have a name, other than "intersections of three quadrics". For generic $A,B,\ldots,I$, this will have only finitely many solutions. It fact it will have at most $8$ solutions (there might actually be less due to multiple solutions or solutions at infinity). Have you tried calculating a Gröbner basis? It might do the trick. $\endgroup$
    – Daniel Loughran
    Commented Oct 17, 2012 at 13:24
  • 1
    $\begingroup$ The system does have solution in terms of radicals. Note that if $(x,y,z)$ is a solution, then $(-x,-y,-z)$ is also a solution. This means that if you look at the equations $(Ax-By)^{2}+(Cx-Dy)^{2}+(x-y)^{2}-G=0$ $(Ax-Ez)^{2}+(Cx-Fz)^{2}+(x-z)^{2}-H=0$ $(Ez-By)^{2}+(Fz-Dy)^{2}+(z-y)^{2}-I=0$ and elimiate the variables $y$ and $z$, this is going to give you a polynomial of degree 4 in $x^2$. Likewise, eliminating $x$ and $z$ (resp. $x$ and $y$) will give you a polynomial of degree 4 in $y^2$ (resp. degree 2 in $z^2$). Maple and Mathematica or any CAS with Grobner basis can do this easily. $\endgroup$
    – J.C. Ottem
    Commented Oct 17, 2012 at 21:52
  • $\begingroup$ Thanks Daniel and Mr Ottem! I can see the elimination works (tried with Maple). Solving it takes huge amount of steps, so I can't use it in practice most likely (will lose the precision long before done), but this is my intro to quadrics I guess. PS I can assume (x, y, z) are all positive - they are z-distances from camera to 3 points $\endgroup$
    – AndresN
    Commented Oct 18, 2012 at 14:12
  • $\begingroup$ AndresN, did you try Newton's method? Since the equations are quadrics, this should be pretty straightforward to implement and the iteration should converge pretty fast. $\endgroup$
    – J.C. Ottem
    Commented Oct 18, 2012 at 15:10
  • $\begingroup$ this is perhaps the only realistic way indeed, thanks! $\endgroup$
    – AndresN
    Commented Oct 22, 2012 at 9:40

0

Reset to default

You must log in to answer this question.