<NME> solver_qll.hpp
<BEF> ADDFILE
<MSG> put qll solver in its own file.
dispatch to each solver based on site types.

<DFF> @@ -0,0 +1,182 @@
+/*  
+ *  Copyright 2010-2011 Anders Wallin (anders.e.e.wallin "at" gmail.com)
+ * 
+ *  Idea and code for point/line/arc voronoi-vertex positioning code by
+ *  Andy Payne, andy "at" payne "dot" org, November, 2010
+ *  see: http://www.payne.org/index.php/Calculating_Voronoi_Nodes
+ * 
+ *  This file is part of OpenVoronoi.
+ *
+ *  OpenVoronoi is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation, either version 3 of the License, or
+ *  (at your option) any later version.
+ *
+ *  OpenVoronoi is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with OpenVoronoi.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef QLL_SOLVER_HPP
+#define QLL_SOLVER_HPP
+
+#include <qd/qd_real.h> // http://crd.lbl.gov/~dhbailey/mpdist/
+
+#include "point.hpp"
+#include "numeric.hpp"
+
+using namespace ovd::numeric; // sq() chop() quadratic_roots()
+
+namespace ovd {
+
+/// point-point-point vertex positioner based on Sugihara & Iri paper
+class QLLSolver : public Solver {
+public:
+
+int solve( Site* s1, double k1, 
+                Site* s2, double k2, 
+                Site* s3, double k3, std::vector<Solution>& solns ) {
+    std::vector< Eq<qd_real> > quads,lins; // equation-parameters, in quad-precision
+    boost::array<Site*,3> sites = {{s1,s2,s3}};
+    boost::array<double,3> kvals = {{k1,k2,k3}};
+    for (unsigned int i=0;i<3;i++) {
+        Eq<qd_real> eqn = sites[i]->eqp_qd( kvals[i] );
+        if (sites[i]->is_linear() ) // store site-equations in lins or quads
+            lins.push_back( eqn ); 
+        else
+            quads.push_back( eqn );
+    }
+    assert( !quads.empty() );
+    
+    if ( lins.size()==1 || lins.size() == 0 ) {
+        assert( quads.size() == 3 || quads.size() == 2 );
+        for (unsigned int i=1;i<quads.size();i++) {
+            quads[i] = quads[i] - quads[0]; // subtract the first quad from the other one(s), to create new linear eqn(s)
+            lins.push_back(quads[i]);
+        }
+    }
+    assert( lins.size() == 2);  // At this point, we should have exactly two linear equations.
+   
+    // TODO:  pick the solution appraoch with the best numerical stability.
+    // index shuffling determines if we solve:
+    // x and y in terms of t
+    // y and t in terms of x
+    // t and x in terms of y
+    /*
+    int scount = qll_solver( lins, 0, 1, 2, quads[0], kk3, solns);
+    if (scount <= 0) { // negative scount when discriminant is zero, so shuffle around coord-indexes:
+        scount = qll_solver(lins, 2, 0, 1, quads[0], kk3, solns);
+        if (scount <= 0) {
+            scount = qll_solver(lins, 1, 2, 0, quads[0], kk3, solns);
+        }
+    }*/
+    
+    // call all three permutations
+    qll_solver( lins, 0, 1, 2, quads[0], k3, solns);
+    qll_solver( lins, 2, 0, 1, quads[0], k3, solns);
+    qll_solver( lins, 1, 2, 0, quads[0], k3, solns);
+    
+    //std::cout << " solver() found " << scount << " roots\n";
+    return solns.size();
+}
+private:
+// l0 first linear eqn
+// l1 second linear eqn
+// xi,yi,ti  indexes to shuffle around
+// xk, yk, kk, rk = params of one ('last') quadratic site (point or arc)
+// solns = output solution triplets (x,y,t) or (u,v,t)
+// returns number of solutions found
+int qll_solver( const std::vector< Eq<qd_real> >& lins, int xi, int yi, int ti, 
+      const Eq<qd_real>& quad, qd_real k3, std::vector<Solution>& solns) { 
+    assert( lins.size() == 2 );
+    qd_real ai = lins[0][xi]; // first linear 
+    qd_real bi = lins[0][yi];
+    qd_real ki = lins[0][ti];
+    qd_real ci = lins[0].c;
+    
+    qd_real aj = lins[1][xi]; // second linear
+    qd_real bj = lins[1][yi];
+    qd_real kj = lins[1][ti];
+    qd_real cj = lins[1].c;
+    
+    qd_real d = chop( ai*bj - aj*bi ); // chop! (determinant for 2 linear eqns (?))
+    if (d == 0) // no solution can be found!
+        return -1;
+    // these are the w-equations for qll_solve()
+    // (2) u = a1 w + b1
+    // (3) v = a2 w + b2
+    qd_real a0 =  (bi*kj - bj*ki) / d;
+    qd_real a1 = -(ai*kj - aj*ki) / d;
+    qd_real b0 =  (bi*cj - bj*ci) / d;
+    qd_real b1 = -(ai*cj - aj*ci) / d;
+    // based on the 'last' quadratic of (s1,s2,s3)
+    qd_real aargs[3][2];
+    aargs[0][0] = 1.0;
+    aargs[0][1] = quad.a;
+    aargs[1][0] = 1.0;
+    aargs[1][1] = quad.b;
+    aargs[2][0] = -1.0;
+    aargs[2][1] = quad.k;
+    
+    qd_real isolns[2][3];
+    // this solves for w, and returns either 0, 1, or 2 triplets of (u,v,t) in isolns
+    // NOTE: indexes of aargs shuffled depending on (xi,yi,ti) !
+    int scount = qll_solve( aargs[xi][0], aargs[xi][1],
+                            aargs[yi][0], aargs[yi][1],
+                            aargs[ti][0], aargs[ti][1],
+                            quad.c, // xk*xk + yk*yk - rk*rk,
+                            a0, b0, 
+                            a1, b1, isolns);
+    double tsolns[2][3];
+    for (int i=0; i<scount; i++) {
+        tsolns[i][xi] = to_double(isolns[i][0]);       // u       x
+        tsolns[i][yi] = to_double(isolns[i][1]);       // v       y
+        tsolns[i][ti] = to_double(isolns[i][2]);       // t       t  chop!
+        solns.push_back( Solution( Point( tsolns[i][0], tsolns[i][1] ), 
+                         tsolns[i][2], to_double(k3) ) );
+    }
+    //std::cout << " k3="<<kk3<<" qqq_solve found " << scount << " roots\n";
+    return scount;
+}
+
+/// Solve a system of one quadratic equation, and two linear equations.
+/// 
+/// (1) a0 u^2 + b0 u + c0 v^2 + d0 v + e0 w^2 + f0 w + g0 = 0
+/// (2) u = a1 w + b1
+/// (3) v = a2 w + b2
+/// solve (1) for w (can have 0, 1, or 2 roots)
+/// then substitute into (2) and (3) to find (u, v, t)
+int qll_solve( qd_real a0, qd_real b0, qd_real c0, qd_real d0, 
+                      qd_real e0, qd_real f0, qd_real g0, 
+                      qd_real a1, qd_real b1, 
+                      qd_real a2, qd_real b2, 
+                      qd_real soln[][3])
+{
+    //std::cout << "qll_solver()\n";
+    // TODO:  optimize using abs(a0) == abs(c0) == abs(d0) == 1
+    qd_real a = chop( (a0*(a1*a1) + c0*(a2*a2) + e0) ); 
+    qd_real b = chop( (2*a0*a1*b1 + 2*a2*b2*c0 + a1*b0 + a2*d0 + f0) ); 
+    qd_real c = a0*(b1*b1) + c0*(b2*b2) + b0*b1 + b2*d0 + g0;
+    std::vector<qd_real> roots = quadratic_roots(a, b, c); // solves a*w^2 + b*w + c = 0
+    if ( roots.empty() ) { // No roots, no solutions
+        //std::cout << " qll_solve no w roots. no solutions.\n";
+        return 0;
+    }
+    for (unsigned int i=0; i<roots.size(); i++) {
+        qd_real w = roots[i];
+        soln[i][0] = a1*w + b1; // u
+        soln[i][1] = a2*w + b2; // v
+        soln[i][2] = w;         // t
+    }
+    return roots.size();
+}
+
+};
+
+
+} // ovd
+#endif

{'commit': 'diff --git a/CMakeLists.txt b/CMakeLists.txt\nindex e5aef69..818b69b 100644\n--- a/CMakeLists.txt\n+++ b/CMakeLists.txt\n@@ -26,11 +26,12 @@ endif(NOT BUILD_PY_LIB)\n # thus we use now use -Wno-deprecated here.\n #\n if (CMAKE_BUILD_TOOL MATCHES "make")\n-    MESSAGE(STATUS "setting gcc options: -W -Wall -Wundef  -Wshadow -Winline -Wno-long-long -Wno-deprecated -Werror -pedantic-errors")\n+    MESSAGE(STATUS "setting gcc options: -W -Wall -Wundef  \n+    -Wshadow -Winline -Wno-long-long -Wno-deprecated -Werror -pedantic-errors")\n     \n     # -pedantic -W -Wall -Wundef -Wfloat-equal -Wshadow -Winline -Wno-long-long\n-    add_definitions( -W -Wall -Wundef  -Wshadow -Wno-long-long -Wno-deprecated -Werror -pedantic-errors)\n-    \n+    add_definitions( -W -Wall -Wundef  -Wshadow -Wno-long-long -Wno-deprecated  -pedantic-errors)\n+    add_definitions( -Wno-error=unused-variable )\n     # this gives warning when comparing float/double with != or ==\n     # -Wfloat-equal\n     \ndiff --git a/python_examples/voronoi_benchmark_3_lineseg.py b/python_examples/voronoi_benchmark_3_lineseg.py\nindex 923937b..87e9637 100644\n--- a/python_examples/voronoi_benchmark_3_lineseg.py\n+++ b/python_examples/voronoi_benchmark_3_lineseg.py\n@@ -21,7 +21,7 @@ def timeVoronoiPoints(Nmax):\n \n def timeVoronoiSegs(Nmax):\n     far = 1\n-    vd = ovd.VoronoiDiagram(far, int( math.floor( math.sqrt(2)*math.sqrt(Nmax) ) ) )\n+    vd = ovd.VoronoiDiagram(far, 10*int( math.floor( math.sqrt(2)*math.sqrt(Nmax) ) ) )\n     print "waiting for ",Nmax," segments..",\n     sys.stdout.flush()\n     segs = gens.randomSegments(far,Nmax)\n@@ -46,7 +46,7 @@ def timeVoronoiSegs(Nmax):\n     \n if __name__ == "__main__":  \n     far = 1\n-    Nmax_exp = 36\n+    Nmax_exp = 32\n     # 10 -> 32 linesites\n     # 14 -> 128\n     # 18 -> 512\ndiff --git a/solver_ppp.hpp b/solver_ppp.hpp\nindex f7f4fb0..6799e9e 100644\n--- a/solver_ppp.hpp\n+++ b/solver_ppp.hpp\n@@ -24,6 +24,9 @@\n #ifndef PPP_SOLVER_HPP\n #define PPP_SOLVER_HPP\n \n+#include <vector>\n+#include <cassert>\n+\n #include "point.hpp"\n #include "numeric.hpp"\n \n@@ -35,7 +38,7 @@ namespace ovd {\n class PPPSolver : public Solver {\n public:\n \n-int solve( Site* s1, double k1, \n+int solve(      Site* s1, double k1, \n                 Site* s2, double k2, \n                 Site* s3, double k3, std::vector<Solution>& slns ) {\n     assert( s1->isPoint() && s2->isPoint() && s3->isPoint() );\n@@ -56,11 +59,17 @@ int solve( Site* s1, double k1,\n     assert( !pi.is_right(pj,pk) );\n     assert( (pi - pj).norm() >=  (pj - pk).norm() );\n     assert( (pi - pj).norm() >=  (pk - pi).norm() );\n-    double J2 = (pi.y-pk.y)*( sq(pj.x-pk.x)+sq(pj.y-pk.y) )/2.0 - (pj.y-pk.y)*( sq(pi.x-pk.x)+sq(pi.y-pk.y) )/2.0;\n-    double J3 = (pi.x-pk.x)*( sq(pj.x-pk.x)+sq(pj.y-pk.y) )/2.0 - (pj.x-pk.x)*( sq(pi.x-pk.x)+sq(pi.y-pk.y) )/2.0;\n+    double J2 = (pi.y-pk.y)*( sq(pj.x-pk.x)+sq(pj.y-pk.y) )/2.0 - \n+                (pj.y-pk.y)*( sq(pi.x-pk.x)+sq(pi.y-pk.y) )/2.0;\n+    double J3 = (pi.x-pk.x)*( sq(pj.x-pk.x)+sq(pj.y-pk.y) )/2.0 - \n+                (pj.x-pk.x)*( sq(pi.x-pk.x)+sq(pi.y-pk.y) )/2.0;\n     double J4 = (pi.x-pk.x)*(pj.y-pk.y) - (pj.x-pk.x)*(pi.y-pk.y);\n     assert( J4 != 0.0 );\n-    slns.push_back( Solution( Point(-J2/J4 + pk.x, J3/J4 + pk.y) , k1+k2+k3 , 0) );\n+    if (J4==0.0)\n+        std::cout << " Warning divide-by-zero!!\\n";\n+    Point pt = Point(-J2/J4 + pk.x, J3/J4 + pk.y);\n+    double dist = (pt-pi).norm();\n+    slns.push_back( Solution(  pt , dist , +1) );\n     return 1;\n }\n \ndiff --git a/solver_qll.hpp b/solver_qll.hpp\nnew file mode 100644\nindex 0000000..4a1fc57\n--- /dev/null\n+++ b/solver_qll.hpp\n@@ -0,0 +1,182 @@\n+/*  \n+ *  Copyright 2010-2011 Anders Wallin (anders.e.e.wallin "at" gmail.com)\n+ * \n+ *  Idea and code for point/line/arc voronoi-vertex positioning code by\n+ *  Andy Payne, andy "at" payne "dot" org, November, 2010\n+ *  see: http://www.payne.org/index.php/Calculating_Voronoi_Nodes\n+ * \n+ *  This file is part of OpenVoronoi.\n+ *\n+ *  OpenVoronoi is free software: you can redistribute it and/or modify\n+ *  it under the terms of the GNU General Public License as published by\n+ *  the Free Software Foundation, either version 3 of the License, or\n+ *  (at your option) any later version.\n+ *\n+ *  OpenVoronoi is distributed in the hope that it will be useful,\n+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n+ *  GNU General Public License for more details.\n+ *\n+ *  You should have received a copy of the GNU General Public License\n+ *  along with OpenVoronoi.  If not, see <http://www.gnu.org/licenses/>.\n+*/\n+\n+#ifndef QLL_SOLVER_HPP\n+#define QLL_SOLVER_HPP\n+\n+#include <qd/qd_real.h> // http://crd.lbl.gov/~dhbailey/mpdist/\n+\n+#include "point.hpp"\n+#include "numeric.hpp"\n+\n+using namespace ovd::numeric; // sq() chop() quadratic_roots()\n+\n+namespace ovd {\n+\n+/// point-point-point vertex positioner based on Sugihara & Iri paper\n+class QLLSolver : public Solver {\n+public:\n+\n+int solve( Site* s1, double k1, \n+                Site* s2, double k2, \n+                Site* s3, double k3, std::vector<Solution>& solns ) {\n+    std::vector< Eq<qd_real> > quads,lins; // equation-parameters, in quad-precision\n+    boost::array<Site*,3> sites = {{s1,s2,s3}};\n+    boost::array<double,3> kvals = {{k1,k2,k3}};\n+    for (unsigned int i=0;i<3;i++) {\n+        Eq<qd_real> eqn = sites[i]->eqp_qd( kvals[i] );\n+        if (sites[i]->is_linear() ) // store site-equations in lins or quads\n+            lins.push_back( eqn ); \n+        else\n+            quads.push_back( eqn );\n+    }\n+    assert( !quads.empty() );\n+    \n+    if ( lins.size()==1 || lins.size() == 0 ) {\n+        assert( quads.size() == 3 || quads.size() == 2 );\n+        for (unsigned int i=1;i<quads.size();i++) {\n+            quads[i] = quads[i] - quads[0]; // subtract the first quad from the other one(s), to create new linear eqn(s)\n+            lins.push_back(quads[i]);\n+        }\n+    }\n+    assert( lins.size() == 2);  // At this point, we should have exactly two linear equations.\n+   \n+    // TODO:  pick the solution appraoch with the best numerical stability.\n+    // index shuffling determines if we solve:\n+    // x and y in terms of t\n+    // y and t in terms of x\n+    // t and x in terms of y\n+    /*\n+    int scount = qll_solver( lins, 0, 1, 2, quads[0], kk3, solns);\n+    if (scount <= 0) { // negative scount when discriminant is zero, so shuffle around coord-indexes:\n+        scount = qll_solver(lins, 2, 0, 1, quads[0], kk3, solns);\n+        if (scount <= 0) {\n+            scount = qll_solver(lins, 1, 2, 0, quads[0], kk3, solns);\n+        }\n+    }*/\n+    \n+    // call all three permutations\n+    qll_solver( lins, 0, 1, 2, quads[0], k3, solns);\n+    qll_solver( lins, 2, 0, 1, quads[0], k3, solns);\n+    qll_solver( lins, 1, 2, 0, quads[0], k3, solns);\n+    \n+    //std::cout << " solver() found " << scount << " roots\\n";\n+    return solns.size();\n+}\n+private:\n+// l0 first linear eqn\n+// l1 second linear eqn\n+// xi,yi,ti  indexes to shuffle around\n+// xk, yk, kk, rk = params of one (\'last\') quadratic site (point or arc)\n+// solns = output solution triplets (x,y,t) or (u,v,t)\n+// returns number of solutions found\n+int qll_solver( const std::vector< Eq<qd_real> >& lins, int xi, int yi, int ti, \n+      const Eq<qd_real>& quad, qd_real k3, std::vector<Solution>& solns) { \n+    assert( lins.size() == 2 );\n+    qd_real ai = lins[0][xi]; // first linear \n+    qd_real bi = lins[0][yi];\n+    qd_real ki = lins[0][ti];\n+    qd_real ci = lins[0].c;\n+    \n+    qd_real aj = lins[1][xi]; // second linear\n+    qd_real bj = lins[1][yi];\n+    qd_real kj = lins[1][ti];\n+    qd_real cj = lins[1].c;\n+    \n+    qd_real d = chop( ai*bj - aj*bi ); // chop! (determinant for 2 linear eqns (?))\n+    if (d == 0) // no solution can be found!\n+        return -1;\n+    // these are the w-equations for qll_solve()\n+    // (2) u = a1 w + b1\n+    // (3) v = a2 w + b2\n+    qd_real a0 =  (bi*kj - bj*ki) / d;\n+    qd_real a1 = -(ai*kj - aj*ki) / d;\n+    qd_real b0 =  (bi*cj - bj*ci) / d;\n+    qd_real b1 = -(ai*cj - aj*ci) / d;\n+    // based on the \'last\' quadratic of (s1,s2,s3)\n+    qd_real aargs[3][2];\n+    aargs[0][0] = 1.0;\n+    aargs[0][1] = quad.a;\n+    aargs[1][0] = 1.0;\n+    aargs[1][1] = quad.b;\n+    aargs[2][0] = -1.0;\n+    aargs[2][1] = quad.k;\n+    \n+    qd_real isolns[2][3];\n+    // this solves for w, and returns either 0, 1, or 2 triplets of (u,v,t) in isolns\n+    // NOTE: indexes of aargs shuffled depending on (xi,yi,ti) !\n+    int scount = qll_solve( aargs[xi][0], aargs[xi][1],\n+                            aargs[yi][0], aargs[yi][1],\n+                            aargs[ti][0], aargs[ti][1],\n+                            quad.c, // xk*xk + yk*yk - rk*rk,\n+                            a0, b0, \n+                            a1, b1, isolns);\n+    double tsolns[2][3];\n+    for (int i=0; i<scount; i++) {\n+        tsolns[i][xi] = to_double(isolns[i][0]);       // u       x\n+        tsolns[i][yi] = to_double(isolns[i][1]);       // v       y\n+        tsolns[i][ti] = to_double(isolns[i][2]);       // t       t  chop!\n+        solns.push_back( Solution( Point( tsolns[i][0], tsolns[i][1] ), \n+                         tsolns[i][2], to_double(k3) ) );\n+    }\n+    //std::cout << " k3="<<kk3<<" qqq_solve found " << scount << " roots\\n";\n+    return scount;\n+}\n+\n+/// Solve a system of one quadratic equation, and two linear equations.\n+/// \n+/// (1) a0 u^2 + b0 u + c0 v^2 + d0 v + e0 w^2 + f0 w + g0 = 0\n+/// (2) u = a1 w + b1\n+/// (3) v = a2 w + b2\n+/// solve (1) for w (can have 0, 1, or 2 roots)\n+/// then substitute into (2) and (3) to find (u, v, t)\n+int qll_solve( qd_real a0, qd_real b0, qd_real c0, qd_real d0, \n+                      qd_real e0, qd_real f0, qd_real g0, \n+                      qd_real a1, qd_real b1, \n+                      qd_real a2, qd_real b2, \n+                      qd_real soln[][3])\n+{\n+    //std::cout << "qll_solver()\\n";\n+    // TODO:  optimize using abs(a0) == abs(c0) == abs(d0) == 1\n+    qd_real a = chop( (a0*(a1*a1) + c0*(a2*a2) + e0) ); \n+    qd_real b = chop( (2*a0*a1*b1 + 2*a2*b2*c0 + a1*b0 + a2*d0 + f0) ); \n+    qd_real c = a0*(b1*b1) + c0*(b2*b2) + b0*b1 + b2*d0 + g0;\n+    std::vector<qd_real> roots = quadratic_roots(a, b, c); // solves a*w^2 + b*w + c = 0\n+    if ( roots.empty() ) { // No roots, no solutions\n+        //std::cout << " qll_solve no w roots. no solutions.\\n";\n+        return 0;\n+    }\n+    for (unsigned int i=0; i<roots.size(); i++) {\n+        qd_real w = roots[i];\n+        soln[i][0] = a1*w + b1; // u\n+        soln[i][1] = a2*w + b2; // v\n+        soln[i][2] = w;         // t\n+    }\n+    return roots.size();\n+}\n+\n+};\n+\n+\n+} // ovd\n+#endif\ndiff --git a/vertex_positioner.cpp b/vertex_positioner.cpp\nindex 49c3193..ff61121 100644\n--- a/vertex_positioner.cpp\n+++ b/vertex_positioner.cpp\n@@ -31,6 +31,7 @@\n \n #include "solver_ppp.hpp"\n #include "solver_lll.hpp"\n+#include "solver_qll.hpp"\n \n using namespace ovd::numeric; // sq() chop()\n \n@@ -39,12 +40,14 @@ namespace ovd {\n VertexPositioner::VertexPositioner(VoronoiDiagram* vodi): vd(vodi) {\n     ppp_solver = new PPPSolver();\n     lll_solver = new LLLSolver();\n+    qll_solver = new QLLSolver();\n     errstat.clear();\n }\n \n VertexPositioner::~VertexPositioner() {\n     delete ppp_solver;\n     delete lll_solver;\n+    delete qll_solver;\n }\n \n // calculate the position of a new vertex on the given edge e\n@@ -54,7 +57,7 @@ VertexPositioner::~VertexPositioner() {\n // - site to the left of HEEdge e\n // - site to the right of HEEdge e\n // - given new Site s\n-Point VertexPositioner::position(HEEdge e, Site* s) {\n+Solution VertexPositioner::position(HEEdge e, Site* s) {\n     edge = e;\n     HEFace face = vd->g[e].face;     \n     HEEdge twin = vd->g[e].twin;\n@@ -83,8 +86,8 @@ Point VertexPositioner::position(HEEdge e, Site* s) {\n     check_far_circle(sl.p);\n     //check_on_edge(e, p);\n     assert( check_dist(edge, sl, s) );\n-    k3 = sl.k3;\n-    return sl.p;\n+    \n+    return sl;\n }\n \n // find vertex that is equidistant from s1, s2, s3\n@@ -94,9 +97,9 @@ Solution VertexPositioner::position(Site* s1, double k1, Site* s2, double k2, Si\n     assert( (k1==1) || (k1 == -1) );\n     assert( (k2==1) || (k2 == -1) );\n     std::vector<Solution> solutions;\n-    solver(s1,k1,s2,k2,s3,+1, solutions);\n+    solver_dispatch(s1,k1,s2,k2,s3,+1, solutions);\n     if (!s3->isPoint()) // for points k3=+1 allways\n-        solver(s1,k1,s2,k2,s3,-1, solutions); // for lineSite or ArcSite we try k3=-1 also    \n+        solver_dispatch(s1,k1,s2,k2,s3,-1, solutions); // for lineSite or ArcSite we try k3=-1 also    \n \n     //std::cout << " solver() done \\n";\n     // choose only t_min < t < t_max solutions \n@@ -146,174 +149,16 @@ Solution VertexPositioner::position(Site* s1, double k1, Site* s2, double k2, Si\n     return Solution( Point(0,0), -1, 1 );\n }\n \n-int VertexPositioner::solver(Site* s1, double k1, Site* s2, double k2, Site* s3, double kk3, std::vector<Solution>& solns) {    \n-    std::vector< Eq<qd_real> > quads,lins; // equation-parameters, in quad-precision\n-    boost::array<Site*,3> sites = {{s1,s2,s3}};\n-    boost::array<double,3> kvals = {{k1,k2,kk3}};\n-    for (unsigned int i=0;i<3;i++) {\n-        Eq<qd_real> eqn = sites[i]->eqp_qd( kvals[i] );\n-        if (sites[i]->is_linear() ) // store site-equations in lins or quads\n-            lins.push_back( eqn ); \n-        else\n-            quads.push_back( eqn );\n-    }\n-    \n-    if (lins.size() == 3) // all lines.\n-        return lll_solver->solve( s1,k1,s2,k2,s3,kk3, solns); // kk3 just passes through, has no effect in lll_solver\n-    \n-    assert( !quads.empty() );\n-    \n-    if ( lins.size()==1 || lins.size() == 0 ) {\n-        assert( quads.size() == 3 || quads.size() == 2 );\n-        for (unsigned int i=1;i<quads.size();i++) {\n-            quads[i] = quads[i] - quads[0]; // subtract the first quad from the other one(s), to create new linear eqn(s)\n-            lins.push_back(quads[i]);\n-        }\n-    }\n-    assert( lins.size() == 2);  // At this point, we should have exactly two linear equations.\n-   \n-    // TODO:  pick the solution appraoch with the best numerical stability.\n-    // index shuffling determines if we solve:\n-    // x and y in terms of t\n-    // y and t in terms of x\n-    // t and x in terms of y\n-    /*\n-    int scount = qll_solver( lins, 0, 1, 2, quads[0], kk3, solns);\n-    if (scount <= 0) { // negative scount when discriminant is zero, so shuffle around coord-indexes:\n-        scount = qll_solver(lins, 2, 0, 1, quads[0], kk3, solns);\n-        if (scount <= 0) {\n-            scount = qll_solver(lins, 1, 2, 0, quads[0], kk3, solns);\n-        }\n-    }*/\n-    \n-    // call all three permutations\n-    qll_solver( lins, 0, 1, 2, quads[0], kk3, solns);\n-    qll_solver( lins, 2, 0, 1, quads[0], kk3, solns);\n-    qll_solver( lins, 1, 2, 0, quads[0], kk3, solns);\n-    \n-    //std::cout << " solver() found " << scount << " roots\\n";\n-    return solns.size();\n-}\n-\n-// l0 first linear eqn\n-// l1 second linear eqn\n-// xi,yi,ti  indexes to shuffle around\n-// xk, yk, kk, rk = params of one (\'last\') quadratic site (point or arc)\n-// solns = output solution triplets (x,y,t) or (u,v,t)\n-// returns number of solutions found\n-int VertexPositioner::qll_solver( const std::vector< Eq<qd_real> >& lins, int xi, int yi, int ti, \n-      const Eq<qd_real>& quad, qd_real kk3, std::vector<Solution>& solns) { \n-    assert( lins.size() == 2 );\n-    qd_real ai = lins[0][xi]; // first linear \n-    qd_real bi = lins[0][yi];\n-    qd_real ki = lins[0][ti];\n-    qd_real ci = lins[0].c;\n-    \n-    qd_real aj = lins[1][xi]; // second linear\n-    qd_real bj = lins[1][yi];\n-    qd_real kj = lins[1][ti];\n-    qd_real cj = lins[1].c;\n-    \n-    qd_real d = chop( ai*bj - aj*bi ); // chop! (determinant for 2 linear eqns (?))\n-    if (d == 0) // no solution can be found!\n-        return -1;\n-    // these are the w-equations for qll_solve()\n-    // (2) u = a1 w + b1\n-    // (3) v = a2 w + b2\n-    qd_real a0 =  (bi*kj - bj*ki) / d;\n-    qd_real a1 = -(ai*kj - aj*ki) / d;\n-    qd_real b0 =  (bi*cj - bj*ci) / d;\n-    qd_real b1 = -(ai*cj - aj*ci) / d;\n-    // based on the \'last\' quadratic of (s1,s2,s3)\n-    qd_real aargs[3][2];\n-    aargs[0][0] = 1.0;\n-    aargs[0][1] = quad.a;\n-    aargs[1][0] = 1.0;\n-    aargs[1][1] = quad.b;\n-    aargs[2][0] = -1.0;\n-    aargs[2][1] = quad.k;\n-    \n-    qd_real isolns[2][3];\n-    // this solves for w, and returns either 0, 1, or 2 triplets of (u,v,t) in isolns\n-    // NOTE: indexes of aargs shuffled depending on (xi,yi,ti) !\n-    int scount = qll_solve( aargs[xi][0], aargs[xi][1],\n-                            aargs[yi][0], aargs[yi][1],\n-                            aargs[ti][0], aargs[ti][1],\n-                            quad.c, // xk*xk + yk*yk - rk*rk,\n-                            a0, b0, \n-                            a1, b1, isolns);\n-    double tsolns[2][3];\n-    for (int i=0; i<scount; i++) {\n-        tsolns[i][xi] = to_double(isolns[i][0]);       // u       x\n-        tsolns[i][yi] = to_double(isolns[i][1]);       // v       y\n-        tsolns[i][ti] = to_double(isolns[i][2]);       // t       t  chop!\n-        solns.push_back( Solution( Point( tsolns[i][0], tsolns[i][1] ), tsolns[i][2], to_double(kk3) ) );\n-    }\n-    //std::cout << " k3="<<kk3<<" qqq_solve found " << scount << " roots\\n";\n-    return scount;\n-}\n-\n-/// Solve a system of one quadratic equation, and two linear equations.\n-/// \n-/// (1) a0 u^2 + b0 u + c0 v^2 + d0 v + e0 w^2 + f0 w + g0 = 0\n-/// (2) u = a1 w + b1\n-/// (3) v = a2 w + b2\n-/// solve (1) for w (can have 0, 1, or 2 roots)\n-/// then substitute into (2) and (3) to find (u, v, t)\n-int VertexPositioner::qll_solve( qd_real a0, qd_real b0, qd_real c0, qd_real d0, \n-                      qd_real e0, qd_real f0, qd_real g0, \n-                      qd_real a1, qd_real b1, \n-                      qd_real a2, qd_real b2, \n-                      qd_real soln[][3])\n-{\n-    //std::cout << "qll_solver()\\n";\n-    // TODO:  optimize using abs(a0) == abs(c0) == abs(d0) == 1\n-    qd_real a = chop( (a0*(a1*a1) + c0*(a2*a2) + e0) ); \n-    qd_real b = chop( (2*a0*a1*b1 + 2*a2*b2*c0 + a1*b0 + a2*d0 + f0) ); \n-    qd_real c = a0*(b1*b1) + c0*(b2*b2) + b0*b1 + b2*d0 + g0;\n-    std::vector<qd_real> roots = quadratic_roots(a, b, c); // solves a*w^2 + b*w + c = 0\n-    if ( roots.empty() ) { // No roots, no solutions\n-        //std::cout << " qll_solve no w roots. no solutions.\\n";\n-        return 0;\n-    }\n-    for (unsigned int i=0; i<roots.size(); i++) {\n-        qd_real w = roots[i];\n-        soln[i][0] = a1*w + b1; // u\n-        soln[i][1] = a2*w + b2; // v\n-        soln[i][2] = w;         // t\n-    }\n-    return roots.size();\n+int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2, Site* s3, double k3, std::vector<Solution>& solns) {    \n+    if ( s1->isLine() && s2->isLine() && s3->isLine() ) \n+        return lll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // all lines.\n+    //else if ( s1->isPoint() && s2->isPoint() && s3->isPoint() )\n+    //    return ppp_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // all points\n+    else\n+        return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver\n+ \n }\n \n-// all three sites are lines\n-/*\n-int VertexPositioner::lll_solver(std::vector< Eq<qd_real> >& eq, double kk3, std::vector<Solution>& slns ) {\n-    //std::cout << " lll_solver() k3= " << k3 << "\\n";\n-    unsigned int i = 0, j=1, k=2;\n-    qd_real d = chop( ( eq[i].a*eq[j].b - eq[j].a*eq[i].b)*eq[k].k + \n-                      (-eq[i].a*eq[k].b + eq[k].a*eq[i].b)*eq[j].k +  \n-                      ( eq[j].a*eq[k].b - eq[k].a*eq[j].b)*eq[i].k   ); // determinant\n-    if (d != 0) {\n-        qd_real t = ( (-eq[i].a*eq[j].b + eq[j].a*eq[i].b)*eq[k].c + \n-                      ( eq[i].a*eq[k].b - eq[k].a*eq[i].b)*eq[j].c + \n-                      (-eq[j].a*eq[k].b + eq[k].a*eq[j].b)*eq[i].c   )/d;\n-        if (t >= 0) {\n-            qd_real sol_x = ( ( eq[i].b*eq[j].c - eq[j].b*eq[i].c)*eq[k].k + \n-                              (-eq[i].b*eq[k].c + eq[k].b*eq[i].c)*eq[j].k + \n-                              ( eq[j].b*eq[k].c - eq[k].b*eq[j].c)*eq[i].k   )/d;\n-            qd_real sol_y = ( (-eq[i].a*eq[j].c + eq[j].a*eq[i].c)*eq[k].k + \n-                              ( eq[i].a*eq[k].c - eq[k].a*eq[i].c)*eq[j].k + \n-                              (-eq[j].a*eq[k].c + eq[k].a*eq[j].c)*eq[i].k   )/d;\n-            slns.push_back( Solution( Point( to_double(sol_x), to_double(sol_y) ), to_double(t), kk3 ) ); // kk3 just passes through without any effect!?\n-            return 1;\n-        }\n-    }\n-    return 0; // no solution if determinant zero, or t-value negative\n-}*/\n-\n-\n-\n-\n bool VertexPositioner::solution_on_edge(Solution& s) {\n     double err = edge_error(edge,s);\n     double limit = 9E-4;\ndiff --git a/vertex_positioner.hpp b/vertex_positioner.hpp\nindex 17f3a25..51caf93 100644\n--- a/vertex_positioner.hpp\n+++ b/vertex_positioner.hpp\n@@ -63,6 +63,7 @@ private:\n     Site* site_;\n };\n \n+// abstract base-class for vertex-solvers\n class Solver {\n public:\n     virtual int solve(Site* s1, double k1, \n@@ -78,16 +79,19 @@ public:\n     /// calculate the position of a new voronoi-vertex lying on the given edge.\n     /// The new vertex is equidistant to the two sites that defined the edge\n     /// and to the new site. \n-    Point position( HEEdge e, Site* s);\n-    double get_k3() const {return k3;}\n+    Solution position( HEEdge e, Site* s);\n+\n     std::vector<double> get_stat() {return errstat;}\n private:\n-    Solution position(Site* p1, double k1, Site* p2, double k2, Site* p3);\n-    \n-    int solver(Site* s1, double k1, Site* s2, double k2, Site* s3, double k3, std::vector<Solution>& slns ); \n+    Solution position(Site* s1, double k1, \n+                      Site* s2, double k2, \n+                      Site* s3);\n     \n-    //int lll_solver(std::vector< Eq<qd_real> >& eqns, double k3, std::vector<Solution>& slns ); // linear 3x3 system\n+    int solver_dispatch(Site* s1, double k1, \n+               Site* s2, double k2, \n+               Site* s3, double k3, std::vector<Solution>& slns ); \n     \n+    /*\n     int qll_solver( const std::vector< Eq<qd_real> >& lins, int xi, int yi, int ti, \n                     const Eq<qd_real>& quad, qd_real k3, std::vector<Solution>& slns );\n     \n@@ -96,7 +100,8 @@ private:\n                       qd_real a1, qd_real b1, \n                       qd_real a2, qd_real b2, \n                       qd_real soln[][3]);\n-\n+    */\n+    \n // geometry-checks\n     double edge_error(HEEdge e, Solution& s );\n     bool solution_on_edge(Solution& s);\n@@ -106,11 +111,11 @@ private:\n   \n     Solver* ppp_solver;\n     Solver* lll_solver;\n+    Solver* qll_solver;\n // DATA\n     VoronoiDiagram* vd;\n     double t_min;\n     double t_max;\n-    double k3; // the offset-direction to the new site\n     HEEdge edge;\n     std::vector<double> errstat;\n };\ndiff --git a/voronoidiagram.cpp b/voronoidiagram.cpp\nindex ea0978e..d1d72c5 100644\n--- a/voronoidiagram.cpp\n+++ b/voronoidiagram.cpp\n@@ -792,8 +792,9 @@ void VoronoiDiagram::add_vertices( Site* new_site ) {\n         std::cout << g[ g.target(q_edges[m])].index << "(t=" << g[ g.target(q_edges[m])].dist() << ")";\n         std::cout <<  " edge, type=" << g[q_edges[m]].type << "\\n";\n         */\n-        g[q].position = vpos->position( q_edges[m], new_site ); // set position\n-        g[q].k3 = vpos->get_k3();\n+        Solution sl = vpos->position( q_edges[m], new_site );\n+        g[q].position = sl.p; // set position\n+        g[q].k3 = sl.k3;\n         g[q].init_dist( new_site->apex_point( g[q].position ) ); // set initial clearance-disk\n         add_vertex_in_edge(q, q_edges[m] );\n     }\n', 'commit_subject': 'put qll solver in its own file. dispatch to each solver based on site types.', 'repo_name': 'aewallin/openvoronoi', 'committer': {'name': 'Anders Wallin', 'email': '46e6e0f6418f24468c511f428fbf311ae6ff961b@gmail.com', 'time_sec': '1321747100', 'tz_offset': '120', 'date': {'seconds': '1321747100'}}, 'commit_tree': 'd5d2f3eb583095af2dcf1f2ebeb482022ecee0b9', 'commit_message': 'put qll solver in its own file.\ndispatch to each solver based on site types.\n', 'language_name': 'Shell', 'license': 'lgpl-2.1', 'hunks': '@@ -0,0 +1,182 @@\n+/*  \n+ *  Copyright 2010-2011 Anders Wallin (anders.e.e.wallin "at" gmail.com)\n+ * \n+ *  Idea and code for point/line/arc voronoi-vertex positioning code by\n+ *  Andy Payne, andy "at" payne "dot" org, November, 2010\n+ *  see: http://www.payne.org/index.php/Calculating_Voronoi_Nodes\n+ * \n+ *  This file is part of OpenVoronoi.\n+ *\n+ *  OpenVoronoi is free software: you can redistribute it and/or modify\n+ *  it under the terms of the GNU General Public License as published by\n+ *  the Free Software Foundation, either version 3 of the License, or\n+ *  (at your option) any later version.\n+ *\n+ *  OpenVoronoi is distributed in the hope that it will be useful,\n+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n+ *  GNU General Public License for more details.\n+ *\n+ *  You should have received a copy of the GNU General Public License\n+ *  along with OpenVoronoi.  If not, see <http://www.gnu.org/licenses/>.\n+*/\n+\n+#ifndef QLL_SOLVER_HPP\n+#define QLL_SOLVER_HPP\n+\n+#include <qd/qd_real.h> // http://crd.lbl.gov/~dhbailey/mpdist/\n+\n+#include "point.hpp"\n+#include "numeric.hpp"\n+\n+using namespace ovd::numeric; // sq() chop() quadratic_roots()\n+\n+namespace ovd {\n+\n+/// point-point-point vertex positioner based on Sugihara & Iri paper\n+class QLLSolver : public Solver {\n+public:\n+\n+int solve( Site* s1, double k1, \n+                Site* s2, double k2, \n+                Site* s3, double k3, std::vector<Solution>& solns ) {\n+    std::vector< Eq<qd_real> > quads,lins; // equation-parameters, in quad-precision\n+    boost::array<Site*,3> sites = {{s1,s2,s3}};\n+    boost::array<double,3> kvals = {{k1,k2,k3}};\n+    for (unsigned int i=0;i<3;i++) {\n+        Eq<qd_real> eqn = sites[i]->eqp_qd( kvals[i] );\n+        if (sites[i]->is_linear() ) // store site-equations in lins or quads\n+            lins.push_back( eqn ); \n+        else\n+            quads.push_back( eqn );\n+    }\n+    assert( !quads.empty() );\n+    \n+    if ( lins.size()==1 || lins.size() == 0 ) {\n+        assert( quads.size() == 3 || quads.size() == 2 );\n+        for (unsigned int i=1;i<quads.size();i++) {\n+            quads[i] = quads[i] - quads[0]; // subtract the first quad from the other one(s), to create new linear eqn(s)\n+            lins.push_back(quads[i]);\n+        }\n+    }\n+    assert( lins.size() == 2);  // At this point, we should have exactly two linear equations.\n+   \n+    // TODO:  pick the solution appraoch with the best numerical stability.\n+    // index shuffling determines if we solve:\n+    // x and y in terms of t\n+    // y and t in terms of x\n+    // t and x in terms of y\n+    /*\n+    int scount = qll_solver( lins, 0, 1, 2, quads[0], kk3, solns);\n+    if (scount <= 0) { // negative scount when discriminant is zero, so shuffle around coord-indexes:\n+        scount = qll_solver(lins, 2, 0, 1, quads[0], kk3, solns);\n+        if (scount <= 0) {\n+            scount = qll_solver(lins, 1, 2, 0, quads[0], kk3, solns);\n+        }\n+    }*/\n+    \n+    // call all three permutations\n+    qll_solver( lins, 0, 1, 2, quads[0], k3, solns);\n+    qll_solver( lins, 2, 0, 1, quads[0], k3, solns);\n+    qll_solver( lins, 1, 2, 0, quads[0], k3, solns);\n+    \n+    //std::cout << " solver() found " << scount << " roots\\n";\n+    return solns.size();\n+}\n+private:\n+// l0 first linear eqn\n+// l1 second linear eqn\n+// xi,yi,ti  indexes to shuffle around\n+// xk, yk, kk, rk = params of one (\'last\') quadratic site (point or arc)\n+// solns = output solution triplets (x,y,t) or (u,v,t)\n+// returns number of solutions found\n+int qll_solver( const std::vector< Eq<qd_real> >& lins, int xi, int yi, int ti, \n+      const Eq<qd_real>& quad, qd_real k3, std::vector<Solution>& solns) { \n+    assert( lins.size() == 2 );\n+    qd_real ai = lins[0][xi]; // first linear \n+    qd_real bi = lins[0][yi];\n+    qd_real ki = lins[0][ti];\n+    qd_real ci = lins[0].c;\n+    \n+    qd_real aj = lins[1][xi]; // second linear\n+    qd_real bj = lins[1][yi];\n+    qd_real kj = lins[1][ti];\n+    qd_real cj = lins[1].c;\n+    \n+    qd_real d = chop( ai*bj - aj*bi ); // chop! (determinant for 2 linear eqns (?))\n+    if (d == 0) // no solution can be found!\n+        return -1;\n+    // these are the w-equations for qll_solve()\n+    // (2) u = a1 w + b1\n+    // (3) v = a2 w + b2\n+    qd_real a0 =  (bi*kj - bj*ki) / d;\n+    qd_real a1 = -(ai*kj - aj*ki) / d;\n+    qd_real b0 =  (bi*cj - bj*ci) / d;\n+    qd_real b1 = -(ai*cj - aj*ci) / d;\n+    // based on the \'last\' quadratic of (s1,s2,s3)\n+    qd_real aargs[3][2];\n+    aargs[0][0] = 1.0;\n+    aargs[0][1] = quad.a;\n+    aargs[1][0] = 1.0;\n+    aargs[1][1] = quad.b;\n+    aargs[2][0] = -1.0;\n+    aargs[2][1] = quad.k;\n+    \n+    qd_real isolns[2][3];\n+    // this solves for w, and returns either 0, 1, or 2 triplets of (u,v,t) in isolns\n+    // NOTE: indexes of aargs shuffled depending on (xi,yi,ti) !\n+    int scount = qll_solve( aargs[xi][0], aargs[xi][1],\n+                            aargs[yi][0], aargs[yi][1],\n+                            aargs[ti][0], aargs[ti][1],\n+                            quad.c, // xk*xk + yk*yk - rk*rk,\n+                            a0, b0, \n+                            a1, b1, isolns);\n+    double tsolns[2][3];\n+    for (int i=0; i<scount; i++) {\n+        tsolns[i][xi] = to_double(isolns[i][0]);       // u       x\n+        tsolns[i][yi] = to_double(isolns[i][1]);       // v       y\n+        tsolns[i][ti] = to_double(isolns[i][2]);       // t       t  chop!\n+        solns.push_back( Solution( Point( tsolns[i][0], tsolns[i][1] ), \n+                         tsolns[i][2], to_double(k3) ) );\n+    }\n+    //std::cout << " k3="<<kk3<<" qqq_solve found " << scount << " roots\\n";\n+    return scount;\n+}\n+\n+/// Solve a system of one quadratic equation, and two linear equations.\n+/// \n+/// (1) a0 u^2 + b0 u + c0 v^2 + d0 v + e0 w^2 + f0 w + g0 = 0\n+/// (2) u = a1 w + b1\n+/// (3) v = a2 w + b2\n+/// solve (1) for w (can have 0, 1, or 2 roots)\n+/// then substitute into (2) and (3) to find (u, v, t)\n+int qll_solve( qd_real a0, qd_real b0, qd_real c0, qd_real d0, \n+                      qd_real e0, qd_real f0, qd_real g0, \n+                      qd_real a1, qd_real b1, \n+                      qd_real a2, qd_real b2, \n+                      qd_real soln[][3])\n+{\n+    //std::cout << "qll_solver()\\n";\n+    // TODO:  optimize using abs(a0) == abs(c0) == abs(d0) == 1\n+    qd_real a = chop( (a0*(a1*a1) + c0*(a2*a2) + e0) ); \n+    qd_real b = chop( (2*a0*a1*b1 + 2*a2*b2*c0 + a1*b0 + a2*d0 + f0) ); \n+    qd_real c = a0*(b1*b1) + c0*(b2*b2) + b0*b1 + b2*d0 + g0;\n+    std::vector<qd_real> roots = quadratic_roots(a, b, c); // solves a*w^2 + b*w + c = 0\n+    if ( roots.empty() ) { // No roots, no solutions\n+        //std::cout << " qll_solve no w roots. no solutions.\\n";\n+        return 0;\n+    }\n+    for (unsigned int i=0; i<roots.size(); i++) {\n+        qd_real w = roots[i];\n+        soln[i][0] = a1*w + b1; // u\n+        soln[i][1] = a2*w + b2; // v\n+        soln[i][2] = w;         // t\n+    }\n+    return roots.size();\n+}\n+\n+};\n+\n+\n+} // ovd\n+#endif\n', 'addition_count': 182, 'deletion_count': 0, 'src_file': '/dev/null', 'tgt_file': 'b/solver_qll.hpp', 'file_extension': '.hpp', 'before_file': 'ADDFILE', 'message': 'put qll solver in its own file.\ndispatch to each solver based on site types.\n', 'author_name': 'Anders Wallin', 'lang': 'hpp'}