<NME> vertex_positioner.cpp
<BEF> /*
 *  Copyright (c) 2010-2012 Anders Wallin (anders.e.e.wallin "at" gmail.com).
 *  
 *  This file is part of Openvoronoi 
 *  (see https://github.com/aewallin/openvoronoi).
 *  
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 2.1 of the License, or
 *  (at your option) any later version.
 *  
 *  This program 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 Lesser General Public License for more details.
 *  
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include <algorithm> // std::erase()

#include <boost/array.hpp>
#include <boost/math/tools/minima.hpp> // brent_find_minima

#include "vertex_positioner.hpp"
#include "voronoidiagram.hpp"
#include "common/numeric.hpp"

#include "solvers/solver_ppp.hpp"
#include "solvers/solver_lll.hpp"
#include "solvers/solver_lll_para.hpp"

#include "solvers/solver_qll.hpp"
#include "solvers/solver_sep.hpp"

namespace ovd {

#define ALT_SEP

VertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {
    ppp_solver = new PPPSolver<qd_real>();
/// create positioner, set graph.
    lll_solver = new LLLSolver();
    qll_solver = new QLLSolver();
    sep_solver = new SEPSolver();
#ifdef ALT_SEP
    alt_sep_solver = new ALTSEPSolver();
#endif
    errstat.clear();
}

VertexPositioner::~VertexPositioner() {
    std::cout << "~VertexPositioner()..";
    delete ppp_solver;
    delete lll_solver;
    delete qll_solver;
    delete sep_solver;
#ifdef ALT_SEP
    delete alt_sep_solver;
#endif
    errstat.clear();
    std::cout << "DONE.\n";
}

// calculate the position of a new vertex on the given edge e
    delete alt_sep_solver;
    delete lll_para_solver;

    errstat.clear();
}

/// \brief position a new vertex on given HEEdge \a e when inserting the new Site \a s3
///
/// calculate the position of a new voronoi-vertex lying on the given edge.
/// The new vertex is equidistant to the two sites that defined the edge
/// and to the new site. 
/// The HEEdge e holds information about which HEFace it belongs to.
/// each HEFace holds information about which Site created it
/// so the three sites defining the position of the vertex are:
/// - site to the left of HEEdge e
/// - site to the right of HEEdge e
/// - the given new Site s
solvers::Solution VertexPositioner::position(HEEdge e, Site* s3) {
    edge = e;
    HEFace face = g[e].face;     
    HEEdge twin = g[e].twin;
    HEFace twin_face = g[twin].face;

    HEVertex src = g.source(e);
    HEVertex trg = g.target(e);
    double t_src = g[src].dist();
    double t_trg = g[trg].dist();
    t_min = std::min( t_src, t_trg ); // the solution we seek must have t_min<t<t_max
    t_max = std::max( t_src, t_trg );

    Site* s1 = g[face     ].site;
    Site* s2 = g[twin_face].site;

    solvers::Solution sl = position(  s1 , g[e].k, s2, g[twin].k, s3 );

    assert( solution_on_edge(sl) );
    //assert( check_far_circle(sl) );
    assert( check_dist(edge, sl, s3) );
    
    // error logging (FIXME: make optional, for max performance?)
    #ifndef NDEBUG
    {
        errstat.push_back( dist_error(edge, sl, s3) );
        if ( dist_error(edge, sl, s3) > 1e-6 ) {
            // 2012-02-04: 1e-9 passes 79/79 tests
            //             1e-10 passes 79/79
            //             1e-12 passes 79/79
            //             1e-13  17 FAILED out of 79
            //             1e-14  38 FAILED out of 79
            std::cout << " VertexPositioner::position() WARNING; large dist_error = " << dist_error(edge,  sl, s3) << "\n";
            double s1_dist = (sl.p - s1->apex_point(sl.p)).norm();
            double s2_dist = (sl.p - s2->apex_point(sl.p)).norm();
            double s3_dist = (sl.p - s3->apex_point(sl.p)).norm();
            std::cout << " s1 dist = " << s1_dist << "\n";
            std::cout << " s2 dist = " << s2_dist << "\n";
            std::cout << " s3 dist = " << s3_dist << "\n";
            std::cout << " t       = " << sl.t << "\n";
            exit(-1);
            //return fabs(t-s3_dist);
        }
    }
    #endif
    
    return sl;
}

/// position a new voronoi vertex
/// find vertex that is equidistant from s1, s2, s3
/// should lie on the k1 side of s1, k2 side of s2
/// we try both k3=-1 and k3=+1 for s3
solvers::Solution VertexPositioner::position(Site* s1, double k1, Site* s2, double k2, Site* s3) {
    assert( (k1==1) || (k1 == -1) );
    assert( (k2==1) || (k2 == -1) );
    std::vector<solvers::Solution> solutions;
        
    solver_dispatch(s1,k1,s2,k2,s3,+1, solutions); // a single k3=+1 call for s3->isPoint()
    
    if (!s3->isPoint()) 
        solver_dispatch(s1,k1,s2,k2,s3,-1, solutions); // for lineSite or ArcSite we try k3=-1 also    
    
    if ( solutions.size() == 1 && (t_min<=solutions[0].t) && (t_max>=solutions[0].t) && (s3->in_region( solutions[0].p)) )
        return solutions[0];
            
    if (solutions.empty() && !silent ) 
        std::cout << "WARNING empty solution set!!\n";
    
    // choose only in_region() solutions
    solutions.erase( std::remove_if(solutions.begin(),solutions.end(), in_region_filter(s3) ), solutions.end() );
    if (solutions.empty() && !silent ) 
        std::cout << "WARNING in_region_filter() results in empty solution set!!\n";
    
    
    // choose only t_min < t < t_max solutions 
    solutions.erase( std::remove_if(solutions.begin(),solutions.end(), t_filter(t_min,t_max) ), solutions.end() );
    if (solutions.empty() && !silent ) 
        std::cout << "WARNING t_filter() results in empty solution set!!\n";

    if ( solutions.size() == 1) // if only one solution is found, return that.
        return solutions[0];
    
    if (solutions.size()>1) {
        std::vector<solvers::Solution> equidistant_solutions;
        // If s3 is a linesite or arcsite, we look for a solution in both halfspaces delimited by s3
        // Usually, the t_min / t_max should take care of filtering out the invalid solution, but in some
        // cases, t remains nearly constant (e.g. if s1 and s2 are nearly parallel) and the out-of-region solution slips through. 
        // Therefore, we remove any solutions which deviate from the equidistance constraint by more than 1%.
        for (std::size_t i = 0; i < solutions.size(); i++) {
            const solvers::Solution& s = solutions[i];
            double d1 = (s.p - s1->apex_point(s.p)).norm();
            double d2 = (s.p - s2->apex_point(s.p)).norm();
            double d3 = (s.p - s3->apex_point(s.p)).norm();
            double err = std::max(std::abs(d1-d2), std::max(std::abs(d2-d3), std::abs(d3-d1)));
            double mindist = std::min(d1, std::min(d2, d3));
            if (err/mindist > 0.01) {
                std::cout << "VertexPositioner::position() Warning:\n";
                std::cout << " Solution "<<i<<" violates equidistance constraint. Distances of solution were:\n";
                std::cout << "  p-s1: "<<sqrt(d1)<<"\n";
                std::cout << "  p-s2: "<<sqrt(d2)<<"\n";
                std::cout << "  p-s3: "<<sqrt(d3)<<"\n";
            }
            else {
                equidistant_solutions.push_back(s);
            }
        }
        solutions = equidistant_solutions;
    }
    if ( solutions.size() == 1) // if only one solution is found, return that.
        return solutions[0];

    if (solutions.size()>1) {
        // two or more points remain so we must further filter here!
        // filter further using edge_error
        double min_error=100;
        solvers::Solution min_solution(Point(0,0),0,0);
        //std::cout << " edge_error filter: \n";
        BOOST_FOREACH(solvers::Solution s, solutions) {
            double err = edge_error(s); //g[edge].error(s);
            //std::cout << s.p << " k3=" << s.k3 << " t=" <<  s.t << " err=" << err << "\n";
            if ( err < min_error) {
                min_solution = s;
                min_error = err;
            }
        }
        if (min_error >= 1e-6) {
            /*
            std::cout << "WARNING: EDGE ERROR TOO LARGE\n";
            std::cout << " s1 = " << s1->str2() << " k1= " << k1 << "\n";
            std::cout << " s2 = " << s2->str2() << " k2= " << k2 << "\n";
            std::cout << " s3 = " << s3->str2() << "\n";
            std::cout << " sln=" << min_solution.p << " err=" << min_error << "\n";
            std::cout << " edge: " << g[ g.source(edge) ].position << " - " << g[ g.target(edge) ].position;
            std::cout << " edge-point(t="<<min_solution.t << ")= " << g[edge].point(min_solution.t) << "\n";
            */
            //assert(0);
        }
        //assert( min_error < 1e-6 );
        return min_solution;
    }
    

    // either 0, or >= 2 solutions found. This is an error.
    // std::cout << " None, or too many solutions found! solutions.size()=" << solutions.size() << "\n";
     
    if ( !silent) {
        std::cout << " solution edge: " << g[ g.source(edge) ].position << "[" << g[ g.source(edge) ].type << "](t=" << g[ g.source(edge) ].dist() << ")";
        std::cout << " - " << g[ g.target(edge) ].position << "[" << g[ g.target(edge) ].type << "](t=" << g[ g.target(edge) ].dist() << ") \n";
        std::cout << " solution edge: " << g[ g.source(edge) ].index << "[" << g[ g.source(edge) ].type<<"]{" << g[ g.source(edge) ].status<<"}";
        std::cout << " -[" << g[edge].type << "]- ";
        std::cout << g[ g.target(edge) ].index << "[" << g[ g.target(edge) ].type << "]{" << g[ g.target(edge) ].status<<"}\n";
        //std::cout << " t-vals t_min= " << t_min << " t_max= " << t_max << "\n";
        //std::cout << "  sites: " << s1->str() << "(k="<< k1<< ") " << s2->str() << "(k="<< k2 << ") new= " << s3->str() << "\n";
        std::cout << " s1= " << s1->str2() << "(k=" << k1<< ")\n";
        std::cout << " s2= " << s2->str2() << "(k=" << k2<< ")\n";
        std::cout << " s3= " << s3->str2() << "\n";
        
        std::cout << "Running solvers again: \n";
    }
    solver_debug(true);
    // run the solver(s) one more time in order to print out un-filtered solution points for debugging
    std::vector<solvers::Solution> solutions2;
    solver_dispatch(s1,k1,s2,k2,s3,+1, solutions2);
    if (!s3->isPoint()) // for points k3=+1 always
        solver_dispatch(s1,k1,s2,k2,s3,-1, solutions2); // for lineSite or ArcSite we try k3=-1 also    
    solver_debug(false);
    
    if ( !silent) { 
        if ( !solutions2.empty() ) {
            std::cout << "The failing " << solutions2.size() << " solutions are: \n";
            BOOST_FOREACH(solvers::Solution s, solutions2 ) {
                std::cout << s.p << " t=" << s.t << " k3=" << s.k3  << " e_err=" << edge_error(s) <<"\n";
                std::cout << " min<t<max=" << ((s.t>=t_min) && (s.t<=t_max));
                std::cout << " s3.in_region=" << s3->in_region(s.p);
                std::cout <<  " region-t=" << s3->in_region_t(s.p) << "\n";
                std::cout <<  " t - t_min= " << s.t - t_min << "\n";
                std::cout <<  " t_max - t= " << t_max - s.t << "\n";
                std::cout <<  " edge type : " << g[edge].type << "\n"; //std::scientific;
            }   
        } else {
            std::cout << "No solutions found by solvers!\n";
    lll_solver->set_debug(b);
    qll_solver->set_debug(b);
    sep_solver->set_debug(b);
#ifdef ALT_SEP
    alt_sep_solver->set_debug(b);
#endif
}

int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2, Site* s3, double k3, std::vector<Solution>& solns) {
    VertexError s1_err_functor(g, edge, s1);
    VertexError s2_err_functor(g, edge, s2);
    VertexError s3_err_functor(g, edge, s3);
    
    if ( !silent) { 
        return lll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // all lines.
    else if ( s1->isPoint() && s2->isPoint() && s3->isPoint() )
        return ppp_solver->solve( s1,s2,s3, solns ); // all points, no need to specify k1,k2,k3, they are all +1
#ifdef ALT_SEP
    else if ( (s3->isLine() && s1->isPoint() ) || 
              (s1->isLine() && s3->isPoint() ) ||
              (s3->isLine() && s2->isPoint() ) ||
    //exit(-1);
    return desp;
}

/// search numerically for a desperate solution along the solution-edge
solvers::Solution VertexPositioner::desperate_solution(Site* s3) {
    VertexError err_functor(g, edge, s3);
    //HEFace face = g[edge].face;     
    //HEEdge twin = g[edge].twin;
    //HEFace twin_face = g[twin].face;
    //Site* s1 =  g[face].site;
    //Site* s2 = g[twin_face].site;
    HEVertex src = g.source(edge);
    HEVertex trg = g.target(edge);
    Point src_p = g[src].position;
    Point trg_p = g[trg].position;
            }
        }
    } 
#endif
    
    // if we didn't dispatch to a solver above, we try the general solver
    return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver
    
    /*
    if (s1->isLine() && s2->isLine() ) {
        std::cout << s1->str2() << "\n";
        std::cout << s2->str2() << "\n";
        std::cout << s3->str2() << "\n";
    }
    boost::array<double,8> x = g[edge].x;
    boost::array<double,8> y = g[edge].y;
    for (unsigned int n=0 ; n < 8 ; n++ ) {
        std::cout << n << "  " << x[n] << "  " << y[n] << "\n";
    }
    
    for (int n=0 ; n < 20 ; n++ ) {
        VertexError s1_err_functor(g, edge, s1);
        VertexError s2_err_functor(g, edge, s2);
        double ts = t_min + ((t_max-t_min)/(20-1))*n;
        std::cout << n << " ts=" << ts << " s3_error= " << err_functor(ts) << " p="<< g[edge].point(ts) << "\n";
        std::cout << "     s1_err=" << s1_err_functor(ts) << " s2_err=" << s2_err_functor(ts) << "\n";

    }
    */
    
    typedef std::pair<double, double> Result;
    Result r = boost::math::tools::brent_find_minima( err_functor, t_min, t_max, 64);
    double t_sln = r.first;
    //Point p_sln = g[edge].point(t_sln);
    Point p_sln = err_functor.edge_point(t_sln); //g[edge].point(t_sln);
    double desp_k3(0);
    if (s3->isPoint())
        desp_k3 = 1;
    else if ( s3->isLine() ) {
        // find out on which side the desperate solution lies
        Point src_se = s3->start();
        Point trg_se = s3->end();
        Point left = 0.5*(src_se+trg_se) + (trg_se-src_se).xy_perp(); 
        if (p_sln.is_right(src_se,trg_se)) {
            desp_k3 = (s3->k()==1) ? -1 : 1;
        } else {
            desp_k3 = (s3->k()==1) ? 1 : -1;
        }
    }
    solvers::Solution desp( p_sln, t_sln, desp_k3 ); 
    return desp;
}

/// set debug output true/false
void VertexPositioner::solver_debug(bool b) {
    ppp_solver->set_debug(b);
    lll_solver->set_debug(b);
    qll_solver->set_debug(b);
    sep_solver->set_debug(b);
    alt_sep_solver->set_debug(b);
    lll_para_solver->set_debug(b);
}

void VertexPositioner::set_silent(bool b) {
    silent=b;
    ppp_solver->set_silent(b);
    lll_solver->set_silent(b);
    lll_para_solver->set_silent(b);
    qll_solver->set_silent(b);
    sep_solver->set_silent(b);
    alt_sep_solver->set_silent(b);
}
    
/// dispatch to the correct solver based on the sites
int VertexPositioner::solver_dispatch(Site* s1, double k1, 
                                      Site* s2, double k2, 
                                      Site* s3, double k3, 
                    std::vector<solvers::Solution>& solns) {


    if ( g[edge].type == SEPARATOR ) {
        // this is a SEPARATOR edge with two LineSites adjacent.
        // find the PointSite that defines the SEPARATOR, so that one LineSite and one PointSite
        // can be submitted to the Solver.
        if ( s1->isLine() && s2->isLine() ) {
            // the parallel lineseg case      v0 --s1 --> pt -- s2 --> v1
            // find t
            if ( g[edge].has_null_face ) {
                s2 = g[ g[edge].null_face ].site;
                assert( s2->isPoint() ); // the sites of null-faces are allwais PointSite
                k2 = +1;
            } else if ( g[ g[edge].twin ].has_null_face ) {
                s2 = g[ g[ g[edge].twin ].null_face ].site;
                assert( s2->isPoint() );
                k2 = +1;
            }
        } else if ( s1->isPoint() && s2->isLine() ) {
            // a normal SEPARATOR edge, defined by a PointSite and a LineSite 
            // swap sites, so SEPSolver can assume s1=line s2=point
            Site* tmp = s1;
            double k_tmp = k1;
            s1 = s2;
            s2 = tmp;
            k1 = k2;
            k2 = k_tmp;
            assert( s1->isLine() );
            assert( s2->isPoint() );
        }
        assert( s1->isLine() && s2->isPoint() ); // we have previously set s1(line) s2(point)
        return sep_solver->solve(s1,k1,s2,k2,s3,k3,solns); 
    } else if ( g[edge].type == PARA_LINELINE  && s3->isLine() ) { // an edge betwee parallel LineSites
        //std::cout << " para lineline! \n";
        return lll_para_solver->solve( s1,k1,s2,k2,s3,k3, solns );
    } else if ( s1->isLine() && s2->isLine() && s3->isLine() ) 
        return lll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // all lines.
    else if ( s1->isPoint() && s2->isPoint() && s3->isPoint() )
        return ppp_solver->solve( s1,1,s2,1,s3,1, solns ); // all points, no need to specify k1,k2,k3, they are all +1
    else if ( (s3->isLine() && s1->isPoint() ) || 
              (s1->isLine() && s3->isPoint() ) ||
              (s3->isLine() && s2->isPoint() ) ||
              (s2->isLine() && s3->isPoint() ) // bad coverage for this line?
            ) {
        // if s1/s2 form a SEPARATOR-edge, this is dispatched automatically to sep-solver
        // here we detect for a separator case between
        // s1/s3
        // s2/s3
        if (s3->isLine() && s1->isPoint() ) {
            if ( detect_sep_case(s3,s1) ) {
                alt_sep_solver->set_type(0);
                return alt_sep_solver->solve(s1, k1, s2, k2, s3, k3, solns );
            }
        }
        if (s3->isLine() && s2->isPoint() ) {
            if ( detect_sep_case(s3,s2) ) {
                alt_sep_solver->set_type(1);
                return alt_sep_solver->solve(s1, k1, s2, k2, s3, k3, solns );
            }
        }
    } 
    
    // if we didn't dispatch to a solver above, we try the general solver
    return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver
    
}

/// detect separator-case, so we can dispatch to the correct Solver
bool VertexPositioner::detect_sep_case(Site* lsite, Site* psite) {
    HEEdge le = lsite->edge();
    HEVertex src = g.source(le);
    HEVertex trg = g.target(le);
    //std::cout << " detect_sep_case() Linesite from " << g[src].index << " to " << g[trg].index << "\n";
    // now from segment end-points get the null-vertex
    HEEdge src_out;
    BOOST_FOREACH(HEEdge e, g.out_edge_itr(src) ) {
        if ( g[e].type == NULLEDGE )
            src_out = e;
    }
    HEEdge trg_out;
    BOOST_FOREACH(HEEdge e, g.out_edge_itr(trg) ) {
        if ( g[e].type == NULLEDGE )
            trg_out = e;
    }
    //std::cout << " detect_sep_case() src null-edge "; g.print_edge(src_out); // << g[src].index << " to " << g[trg].index << "\n";
    //std::cout << " detect_sep_case() trg null-edge "; g.print_edge(trg_out);
    
    HEFace src_null_face = g[src_out].face;
    if (g[src_null_face].null == false ) {
        // take twin face instead
        HEEdge src_out_twin = g[src_out].twin;
        src_null_face = g[src_out_twin].face;
    }
    
    HEFace trg_null_face = g[trg_out].face;
    if ( g[trg_null_face].null == false ) {
        HEEdge trg_out_twin = g[trg_out].twin;
        trg_null_face = g[trg_out_twin].face;
    }
    assert( g[src_null_face].null && g[trg_null_face].null );
        
    // do we want src_out face??
    // OR src_out_twin face??
    // we want the null-face !
        
    //std::cout << " detect_sep_case() src null-face " << src_null_face << "\n";
    //g.print_face(src_null_face);
    //std::cout << " detect_sep_case() trg null-face " << trg_null_face << "\n";
    //g.print_face(trg_null_face);
    
    Site* src_site = g[src_null_face].site;
    Site* trg_site = g[trg_null_face].site;
    if (src_site == NULL || trg_site == NULL ) {
        exit(-1);
    }
    if ( !src_site->isPoint() || !trg_site->isPoint() ) {
        exit(-1);
    }
    //std::cout << " detect_sep_case() src PointSite is "  << src_site->str() << "\n"; // << src_site->vertex();
    //std::cout << " detect_sep_case() trg PointSite is "  << trg_site->str() << "\n";
    HEVertex src_vertex = src_site->vertex();
    HEVertex trg_vertex = trg_site->vertex();
    //std::cout << " detect_sep_case() 1st end-point vertex is " << g[src_vertex].index << "\n";
    //std::cout << " detect_sep_case() 2nd end-point vertex is " << g[trg_vertex].index << "\n";
    //std::cout << " detect_sep_case() psite is " << psite->str() << "\n";
    //std::cout << " detect_sep_case() psite is " << g[psite->vertex()].index << "\n"; // g[ psite->vertex()].index << "\n";
    if ( src_vertex == psite->vertex() ) {
        //std::cout << " detect_sep_case(): src separator case!\n";
        //std::cout << " detect_sep_case(): line is " << g[src].index << " - " << g[trg].index << " with psites " << g[src_vertex].index << " - " << g[trg_vertex].index << "\n";
        //std::cout << " detect_sep_case(): psite vertex is " << g[ psite->vertex() ].index << "\n";
        return true;
    }
    if ( trg_vertex == psite->vertex() ) {
        //std::cout << " detect_sep_case(): trg separator case!\n";
        //std::cout << " detect_sep_case(): line is " << g[src].index << " - " << g[trg].index << " with psites " << g[src_vertex].index << " - " << g[trg_vertex].index << "\n";
        //std::cout << " detect_sep_case(): psite vertex is " << g[ psite->vertex() ].index << "\n";

        return true;
    }
    //std::cout << " detect_sep_case()   NOT a separator case.\n";
    return false;
}

/// error from solution to corresponding point on the edge
double VertexPositioner::edge_error(solvers::Solution& sl) {
    Point p;
    if (g[edge].type==PARA_LINELINE) {
        p = projection_point( sl );
    } else {
        p = g[edge].point( sl.t );
    }
    return (p-sl.p).norm();
}

/// when the edge is not parametrized by t-value as normal edges
/// so we need a projection of sl onto the edge instead
Point VertexPositioner::projection_point(solvers::Solution& sl) {
    assert( g[edge].type == PARA_LINELINE );
    // edge given by
    // p = p0 + t * (p1-p0)   with t in [0,1]
    Point p0( g[ g.source(edge) ].position );
    Point p1( g[ g.target(edge) ].position ); 
    //std::cout << " edge is  " << p0 << " - " << p1 << "\n";
    //std::cout << " edge direction: " << v << "\n";
    Point v = p1-p0;
    
    double t = (sl.p - p0).dot(v) / v.dot(v);
    // clamp to [0,1]
    if ( t>1)
        t=1;
    else if (t<0)
        t=0;
    //std::cout << " projection of solution " << sl.p << " is " << (p0+v*t) << "\n";
    return (p0+v*t);
}

/// check that the new solution lies on the edge
bool VertexPositioner::solution_on_edge(solvers::Solution& s) {
    double err = edge_error(s);
    double limit = 9E-4;
    if ( err>=limit ) {
        std::cout << "solution_on_edge() ERROR err= " << err << "\n";
        std::cout << " solution edge: " << g[ g.source(edge) ].index << "[" << g[ g.source(edge) ].type<<"]{" << g[ g.source(edge) ].status<<"}";
        std::cout << " -[" << g[edge].type << "]- ";
        std::cout << g[ g.target(edge) ].index << "[" << g[ g.target(edge) ].type << "]{" << g[ g.target(edge) ].status<<"}\n";


        std::cout << " edge: " << g[ g.source(edge) ].index << "(t=" << g[ g.source(edge) ].dist() << ")"; 
        std::cout << " - " << g[ g.target(edge) ].index << "(t=" << g[ g.target(edge) ].dist() << ")\n";
        std::cout << " edge: " << g[ g.source(edge) ].position << " - " << g[ g.target(edge) ].position << "\n";
        std::cout << " solution: " << s.p << " t=" << s.t << "\n";
    }
    return (err<limit);
}

// calculate the distance from the solution-point to the corresponding point on the edge.
/*
double VertexPositioner::edge_error(HEEdge e, Solution& s) {
    Point ep = g[e].point( s.t, s );
    return (ep-s.p).norm();
}*/

/// new vertices should lie within the far_radius
bool VertexPositioner::check_far_circle(solvers::Solution& s) {
    if (!(s.p.norm() < 18*1)) {
        std::cout << "WARNING check_far_circle() new vertex outside far_radius! \n";
        std::cout << s.p << " norm=" << s.p.norm() << " far_radius=" << 1 << "\n"; 
        return false;
    }
    return true;
}

/// distance sanity check
// all vertices should be of degree three, i.e. three adjacent faces/sites
// distance to the three adjacent sites should be equal
bool VertexPositioner::check_dist(HEEdge e, const solvers::Solution& sl, Site* s3) {
    HEFace face = g[e].face;     
    HEEdge tw_edge = g[e].twin;
    HEFace twin_face = g[tw_edge].face;      
    
    Site* s1 = g[face].site;
    Site* s2 = g[twin_face].site;
    
    double d1 = (sl.p - s1->apex_point(sl.p) ).norm();
    double d2 = (sl.p - s2->apex_point(sl.p) ).norm();  
    double d3 = (sl.p - s3->apex_point(sl.p) ).norm(); 
    
    double maxd = std::max( std::max( fabs(sl.t-d1),fabs(sl.t-d2)) , fabs(sl.t-d3));
    errstat.push_back(maxd);
        
    if ( !equal(d1,d2) || !equal(d1,d3) || !equal(d2,d3) ||
         !equal(sl.t,d1) || !equal(sl.t,d2) || !equal(sl.t,d3) ) {
        std::cout << "WARNING check_dist() ! \n";
        std::cout << "  sl.t= " << sl.t << "\n";
        std::cout << "  d1= " << d1 << "\n"; 
        std::cout << "  d2= " << d2 << "\n";
        std::cout << "  d3= " << d3 << "\n";
        std::cout << " solution edge: " << g[ g.source(edge) ].index << "[" << g[ g.source(edge) ].type<<"]{" << g[ g.source(edge) ].status<<"}";
        std::cout << " -[" << g[edge].type << "]- ";
        std::cout << g[ g.target(edge) ].index << "[" << g[ g.target(edge) ].type << "]{" << g[ g.target(edge) ].status<<"}\n";
    
        return false;
    }
    return true;
}

/// distance-error
// new vertices should be equidistant to the three adjacent sites that define the vertex
// we here calculate the distances d1, d2, d3 from the Solution to the three sites s1, s2, s3
// and return the max deviation from the solution t-value.
// this works as a sanity check for the solver.
// a high error value here is also an indication of numerical instability in the solver
double VertexPositioner::dist_error(HEEdge e, const solvers::Solution& sl, Site* s3) {
    HEFace face = g[e].face;     
    HEEdge tw_edge = g[e].twin;
    HEFace twin_face = g[tw_edge].face;      
    
    Site* s1 = g[face].site;
    Site* s2 = g[twin_face].site;
    
    double d1 = (sl.p - s1->apex_point(sl.p) ).norm();
    double d2 = (sl.p - s2->apex_point(sl.p) ).norm();  
    double d3 = (sl.p - s3->apex_point(sl.p) ).norm(); 
    
    return std::max( std::max( fabs(sl.t-d1),fabs(sl.t-d2)) , fabs(sl.t-d3));

}

/// are \a d1 and \a d2 roughly equal?
bool VertexPositioner::equal(double d1, double d2) {
    double tol = 1e-3;
    if ( fabs(d1-d2) < 1e-15 )
        return true;
    if ( fabs(d1-d2) > tol*std::max(d1,d2) )
        return false;
    return true;
}
    
    
} // end namespace

<MSG> have svg colors match VTK colors roughly

<DFF> @@ -35,7 +35,6 @@ using namespace ovd::numeric; // sq() chop()
 
 namespace ovd {
 
-#define ALT_SEP
 
 VertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {
     ppp_solver = new PPPSolver<qd_real>();
@@ -43,23 +42,19 @@ VertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {
     lll_solver = new LLLSolver();
     qll_solver = new QLLSolver();
     sep_solver = new SEPSolver();
-#ifdef ALT_SEP
     alt_sep_solver = new ALTSEPSolver();
-#endif
     errstat.clear();
 }
 
 VertexPositioner::~VertexPositioner() {
-    std::cout << "~VertexPositioner()..";
+    //std::cout << "~VertexPositioner()..";
     delete ppp_solver;
     delete lll_solver;
     delete qll_solver;
     delete sep_solver;
-#ifdef ALT_SEP
     delete alt_sep_solver;
-#endif
     errstat.clear();
-    std::cout << "DONE.\n";
+    //std::cout << "DONE.\n";
 }
 
 // calculate the position of a new vertex on the given edge e
@@ -265,9 +260,7 @@ void VertexPositioner::solver_debug(bool b) {
     lll_solver->set_debug(b);
     qll_solver->set_debug(b);
     sep_solver->set_debug(b);
-#ifdef ALT_SEP
     alt_sep_solver->set_debug(b);
-#endif
 }
 
 int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2, Site* s3, double k3, std::vector<Solution>& solns) {
@@ -279,7 +272,6 @@ int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2,
         return lll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // all lines.
     else if ( s1->isPoint() && s2->isPoint() && s3->isPoint() )
         return ppp_solver->solve( s1,s2,s3, solns ); // all points, no need to specify k1,k2,k3, they are all +1
-#ifdef ALT_SEP
     else if ( (s3->isLine() && s1->isPoint() ) || 
               (s1->isLine() && s3->isPoint() ) ||
               (s3->isLine() && s2->isPoint() ) ||
@@ -302,7 +294,6 @@ int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2,
             }
         }
     } 
-#endif
     
     // if we didn't dispatch to a solver above, we try the general solver
     return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver

{'commit': 'diff --git a/src/common/halfedgediagram.hpp b/src/common/halfedgediagram.hpp\nindex 42b6df1..3f0c680 100644\n--- a/src/common/halfedgediagram.hpp\n+++ b/src/common/halfedgediagram.hpp\n@@ -132,7 +132,7 @@ public:\n \n virtual ~half_edge_diagram(){\n     // sites are associated with faces. go through all faces and delete the site\n-    std::cout << "~half_edge_diagram()...";\n+    //std::cout << "~half_edge_diagram()...";\n     /*\n     BOOST_FOREACH( TFaceProperties fprop, faces ) {\n         if (fprop.site)\n@@ -140,7 +140,7 @@ virtual ~half_edge_diagram(){\n     }\n     g.clear();\n     */\n-    std::cout << "DONE.";\n+    //std::cout << "DONE.";\n }\n \n // One-liner wrappers around boost-graph-library functions:\ndiff --git a/src/utility/vd2svg.hpp b/src/utility/vd2svg.hpp\nindex 67865c7..6fad63a 100644\n--- a/src/utility/vd2svg.hpp\n+++ b/src/utility/vd2svg.hpp\n@@ -46,7 +46,9 @@ svg::Color get_edge_color(ovd::HEGraph& g, ovd::HEEdge e) {\n     if ( g[e].type == ovd::LINESITE )\n         return svg::Color::Yellow;\n     if ( g[e].type == ovd::PARABOLA )\n-        return svg::Color::Green;\n+        return svg::Color::Cyan;\n+    if ( g[e].type == ovd::SEPARATOR )\n+        return svg::Color::Magenta;\n     return svg::Color::Blue;\n }\n \ndiff --git a/src/vertex_positioner.cpp b/src/vertex_positioner.cpp\nindex e34c211..e1d7f2d 100644\n--- a/src/vertex_positioner.cpp\n+++ b/src/vertex_positioner.cpp\n@@ -35,7 +35,6 @@ using namespace ovd::numeric; // sq() chop()\n \n namespace ovd {\n \n-#define ALT_SEP\n \n VertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {\n     ppp_solver = new PPPSolver<qd_real>();\n@@ -43,23 +42,19 @@ VertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {\n     lll_solver = new LLLSolver();\n     qll_solver = new QLLSolver();\n     sep_solver = new SEPSolver();\n-#ifdef ALT_SEP\n     alt_sep_solver = new ALTSEPSolver();\n-#endif\n     errstat.clear();\n }\n \n VertexPositioner::~VertexPositioner() {\n-    std::cout << "~VertexPositioner()..";\n+    //std::cout << "~VertexPositioner()..";\n     delete ppp_solver;\n     delete lll_solver;\n     delete qll_solver;\n     delete sep_solver;\n-#ifdef ALT_SEP\n     delete alt_sep_solver;\n-#endif\n     errstat.clear();\n-    std::cout << "DONE.\\n";\n+    //std::cout << "DONE.\\n";\n }\n \n // calculate the position of a new vertex on the given edge e\n@@ -265,9 +260,7 @@ void VertexPositioner::solver_debug(bool b) {\n     lll_solver->set_debug(b);\n     qll_solver->set_debug(b);\n     sep_solver->set_debug(b);\n-#ifdef ALT_SEP\n     alt_sep_solver->set_debug(b);\n-#endif\n }\n \n int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2, Site* s3, double k3, std::vector<Solution>& solns) {\n@@ -279,7 +272,6 @@ int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2,\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,s2,s3, solns ); // all points, no need to specify k1,k2,k3, they are all +1\n-#ifdef ALT_SEP\n     else if ( (s3->isLine() && s1->isPoint() ) || \n               (s1->isLine() && s3->isPoint() ) ||\n               (s3->isLine() && s2->isPoint() ) ||\n@@ -302,7 +294,6 @@ int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2,\n             }\n         }\n     } \n-#endif\n     \n     // if we didn\'t dispatch to a solver above, we try the general solver\n     return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver\n', 'commit_subject': 'have svg colors match VTK colors roughly', 'repo_name': 'aewallin/openvoronoi', 'committer': {'name': 'Anders Wallin', 'email': '46e6e0f6418f24468c511f428fbf311ae6ff961b@gmail.com', 'time_sec': '1328304483', 'tz_offset': '120', 'date': {'seconds': '1328304483'}}, 'commit_tree': '9b94ec4a63ac3dedee51e307d25dac1a1b8be2cf', 'commit_message': 'have svg colors match VTK colors roughly\n', 'language_name': 'Shell', 'license': 'lgpl-2.1', 'hunks': '@@ -35,7 +35,6 @@ using namespace ovd::numeric; // sq() chop()\n \n namespace ovd {\n \n-#define ALT_SEP\n \n VertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {\n     ppp_solver = new PPPSolver<qd_real>();\n@@ -43,23 +42,19 @@ VertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {\n     lll_solver = new LLLSolver();\n     qll_solver = new QLLSolver();\n     sep_solver = new SEPSolver();\n-#ifdef ALT_SEP\n     alt_sep_solver = new ALTSEPSolver();\n-#endif\n     errstat.clear();\n }\n \n VertexPositioner::~VertexPositioner() {\n-    std::cout << "~VertexPositioner()..";\n+    //std::cout << "~VertexPositioner()..";\n     delete ppp_solver;\n     delete lll_solver;\n     delete qll_solver;\n     delete sep_solver;\n-#ifdef ALT_SEP\n     delete alt_sep_solver;\n-#endif\n     errstat.clear();\n-    std::cout << "DONE.\\n";\n+    //std::cout << "DONE.\\n";\n }\n \n // calculate the position of a new vertex on the given edge e\n@@ -265,9 +260,7 @@ void VertexPositioner::solver_debug(bool b) {\n     lll_solver->set_debug(b);\n     qll_solver->set_debug(b);\n     sep_solver->set_debug(b);\n-#ifdef ALT_SEP\n     alt_sep_solver->set_debug(b);\n-#endif\n }\n \n int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2, Site* s3, double k3, std::vector<Solution>& solns) {\n@@ -279,7 +272,6 @@ int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2,\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,s2,s3, solns ); // all points, no need to specify k1,k2,k3, they are all +1\n-#ifdef ALT_SEP\n     else if ( (s3->isLine() && s1->isPoint() ) || \n               (s1->isLine() && s3->isPoint() ) ||\n               (s3->isLine() && s2->isPoint() ) ||\n@@ -302,7 +294,6 @@ int VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2,\n             }\n         }\n     } \n-#endif\n     \n     // if we didn\'t dispatch to a solver above, we try the general solver\n     return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver\n', 'addition_count': 2, 'deletion_count': 11, 'src_file': 'a/src/vertex_positioner.cpp', 'tgt_file': 'b/src/vertex_positioner.cpp', 'file_extension': '.cpp', 'before_file': '/*\n *  Copyright (c) 2010-2012 Anders Wallin (anders.e.e.wallin "at" gmail.com).\n *  \n *  This file is part of Openvoronoi \n *  (see https://github.com/aewallin/openvoronoi).\n *  \n *  This program is free software: you can redistribute it and/or modify\n *  it under the terms of the GNU Lesser General Public License as published by\n *  the Free Software Foundation, either version 2.1 of the License, or\n *  (at your option) any later version.\n *  \n *  This program 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 Lesser General Public License for more details.\n *  \n *  You should have received a copy of the GNU Lesser General Public License\n *  along with this program. If not, see <http://www.gnu.org/licenses/>.\n*/\n#include <algorithm> // std::erase()\n\n#include <boost/array.hpp>\n#include <boost/math/tools/minima.hpp> // brent_find_minima\n\n#include "vertex_positioner.hpp"\n#include "voronoidiagram.hpp"\n#include "common/numeric.hpp"\n\n#include "solvers/solver_ppp.hpp"\n#include "solvers/solver_lll.hpp"\n#include "solvers/solver_lll_para.hpp"\n\n#include "solvers/solver_qll.hpp"\n#include "solvers/solver_sep.hpp"\n\nnamespace ovd {\n\n#define ALT_SEP\n\nVertexPositioner::VertexPositioner(HEGraph& gi): g(gi) {\n    ppp_solver = new PPPSolver<qd_real>();\n/// create positioner, set graph.\n    lll_solver = new LLLSolver();\n    qll_solver = new QLLSolver();\n    sep_solver = new SEPSolver();\n#ifdef ALT_SEP\n    alt_sep_solver = new ALTSEPSolver();\n#endif\n    errstat.clear();\n}\n\nVertexPositioner::~VertexPositioner() {\n    std::cout << "~VertexPositioner()..";\n    delete ppp_solver;\n    delete lll_solver;\n    delete qll_solver;\n    delete sep_solver;\n#ifdef ALT_SEP\n    delete alt_sep_solver;\n#endif\n    errstat.clear();\n    std::cout << "DONE.\\n";\n}\n\n// calculate the position of a new vertex on the given edge e\n    delete alt_sep_solver;\n    delete lll_para_solver;\n\n    errstat.clear();\n}\n\n/// \\brief position a new vertex on given HEEdge \\a e when inserting the new Site \\a s3\n///\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/// The HEEdge e holds information about which HEFace it belongs to.\n/// each HEFace holds information about which Site created it\n/// so the three sites defining the position of the vertex are:\n/// - site to the left of HEEdge e\n/// - site to the right of HEEdge e\n/// - the given new Site s\nsolvers::Solution VertexPositioner::position(HEEdge e, Site* s3) {\n    edge = e;\n    HEFace face = g[e].face;     \n    HEEdge twin = g[e].twin;\n    HEFace twin_face = g[twin].face;\n\n    HEVertex src = g.source(e);\n    HEVertex trg = g.target(e);\n    double t_src = g[src].dist();\n    double t_trg = g[trg].dist();\n    t_min = std::min( t_src, t_trg ); // the solution we seek must have t_min<t<t_max\n    t_max = std::max( t_src, t_trg );\n\n    Site* s1 = g[face     ].site;\n    Site* s2 = g[twin_face].site;\n\n    solvers::Solution sl = position(  s1 , g[e].k, s2, g[twin].k, s3 );\n\n    assert( solution_on_edge(sl) );\n    //assert( check_far_circle(sl) );\n    assert( check_dist(edge, sl, s3) );\n    \n    // error logging (FIXME: make optional, for max performance?)\n    #ifndef NDEBUG\n    {\n        errstat.push_back( dist_error(edge, sl, s3) );\n        if ( dist_error(edge, sl, s3) > 1e-6 ) {\n            // 2012-02-04: 1e-9 passes 79/79 tests\n            //             1e-10 passes 79/79\n            //             1e-12 passes 79/79\n            //             1e-13  17 FAILED out of 79\n            //             1e-14  38 FAILED out of 79\n            std::cout << " VertexPositioner::position() WARNING; large dist_error = " << dist_error(edge,  sl, s3) << "\\n";\n            double s1_dist = (sl.p - s1->apex_point(sl.p)).norm();\n            double s2_dist = (sl.p - s2->apex_point(sl.p)).norm();\n            double s3_dist = (sl.p - s3->apex_point(sl.p)).norm();\n            std::cout << " s1 dist = " << s1_dist << "\\n";\n            std::cout << " s2 dist = " << s2_dist << "\\n";\n            std::cout << " s3 dist = " << s3_dist << "\\n";\n            std::cout << " t       = " << sl.t << "\\n";\n            exit(-1);\n            //return fabs(t-s3_dist);\n        }\n    }\n    #endif\n    \n    return sl;\n}\n\n/// position a new voronoi vertex\n/// find vertex that is equidistant from s1, s2, s3\n/// should lie on the k1 side of s1, k2 side of s2\n/// we try both k3=-1 and k3=+1 for s3\nsolvers::Solution VertexPositioner::position(Site* s1, double k1, Site* s2, double k2, Site* s3) {\n    assert( (k1==1) || (k1 == -1) );\n    assert( (k2==1) || (k2 == -1) );\n    std::vector<solvers::Solution> solutions;\n        \n    solver_dispatch(s1,k1,s2,k2,s3,+1, solutions); // a single k3=+1 call for s3->isPoint()\n    \n    if (!s3->isPoint()) \n        solver_dispatch(s1,k1,s2,k2,s3,-1, solutions); // for lineSite or ArcSite we try k3=-1 also    \n    \n    if ( solutions.size() == 1 && (t_min<=solutions[0].t) && (t_max>=solutions[0].t) && (s3->in_region( solutions[0].p)) )\n        return solutions[0];\n            \n    if (solutions.empty() && !silent ) \n        std::cout << "WARNING empty solution set!!\\n";\n    \n    // choose only in_region() solutions\n    solutions.erase( std::remove_if(solutions.begin(),solutions.end(), in_region_filter(s3) ), solutions.end() );\n    if (solutions.empty() && !silent ) \n        std::cout << "WARNING in_region_filter() results in empty solution set!!\\n";\n    \n    \n    // choose only t_min < t < t_max solutions \n    solutions.erase( std::remove_if(solutions.begin(),solutions.end(), t_filter(t_min,t_max) ), solutions.end() );\n    if (solutions.empty() && !silent ) \n        std::cout << "WARNING t_filter() results in empty solution set!!\\n";\n\n    if ( solutions.size() == 1) // if only one solution is found, return that.\n        return solutions[0];\n    \n    if (solutions.size()>1) {\n        std::vector<solvers::Solution> equidistant_solutions;\n        // If s3 is a linesite or arcsite, we look for a solution in both halfspaces delimited by s3\n        // Usually, the t_min / t_max should take care of filtering out the invalid solution, but in some\n        // cases, t remains nearly constant (e.g. if s1 and s2 are nearly parallel) and the out-of-region solution slips through. \n        // Therefore, we remove any solutions which deviate from the equidistance constraint by more than 1%.\n        for (std::size_t i = 0; i < solutions.size(); i++) {\n            const solvers::Solution& s = solutions[i];\n            double d1 = (s.p - s1->apex_point(s.p)).norm();\n            double d2 = (s.p - s2->apex_point(s.p)).norm();\n            double d3 = (s.p - s3->apex_point(s.p)).norm();\n            double err = std::max(std::abs(d1-d2), std::max(std::abs(d2-d3), std::abs(d3-d1)));\n            double mindist = std::min(d1, std::min(d2, d3));\n            if (err/mindist > 0.01) {\n                std::cout << "VertexPositioner::position() Warning:\\n";\n                std::cout << " Solution "<<i<<" violates equidistance constraint. Distances of solution were:\\n";\n                std::cout << "  p-s1: "<<sqrt(d1)<<"\\n";\n                std::cout << "  p-s2: "<<sqrt(d2)<<"\\n";\n                std::cout << "  p-s3: "<<sqrt(d3)<<"\\n";\n            }\n            else {\n                equidistant_solutions.push_back(s);\n            }\n        }\n        solutions = equidistant_solutions;\n    }\n    if ( solutions.size() == 1) // if only one solution is found, return that.\n        return solutions[0];\n\n    if (solutions.size()>1) {\n        // two or more points remain so we must further filter here!\n        // filter further using edge_error\n        double min_error=100;\n        solvers::Solution min_solution(Point(0,0),0,0);\n        //std::cout << " edge_error filter: \\n";\n        BOOST_FOREACH(solvers::Solution s, solutions) {\n            double err = edge_error(s); //g[edge].error(s);\n            //std::cout << s.p << " k3=" << s.k3 << " t=" <<  s.t << " err=" << err << "\\n";\n            if ( err < min_error) {\n                min_solution = s;\n                min_error = err;\n            }\n        }\n        if (min_error >= 1e-6) {\n            /*\n            std::cout << "WARNING: EDGE ERROR TOO LARGE\\n";\n            std::cout << " s1 = " << s1->str2() << " k1= " << k1 << "\\n";\n            std::cout << " s2 = " << s2->str2() << " k2= " << k2 << "\\n";\n            std::cout << " s3 = " << s3->str2() << "\\n";\n            std::cout << " sln=" << min_solution.p << " err=" << min_error << "\\n";\n            std::cout << " edge: " << g[ g.source(edge) ].position << " - " << g[ g.target(edge) ].position;\n            std::cout << " edge-point(t="<<min_solution.t << ")= " << g[edge].point(min_solution.t) << "\\n";\n            */\n            //assert(0);\n        }\n        //assert( min_error < 1e-6 );\n        return min_solution;\n    }\n    \n\n    // either 0, or >= 2 solutions found. This is an error.\n    // std::cout << " None, or too many solutions found! solutions.size()=" << solutions.size() << "\\n";\n     \n    if ( !silent) {\n        std::cout << " solution edge: " << g[ g.source(edge) ].position << "[" << g[ g.source(edge) ].type << "](t=" << g[ g.source(edge) ].dist() << ")";\n        std::cout << " - " << g[ g.target(edge) ].position << "[" << g[ g.target(edge) ].type << "](t=" << g[ g.target(edge) ].dist() << ") \\n";\n        std::cout << " solution edge: " << g[ g.source(edge) ].index << "[" << g[ g.source(edge) ].type<<"]{" << g[ g.source(edge) ].status<<"}";\n        std::cout << " -[" << g[edge].type << "]- ";\n        std::cout << g[ g.target(edge) ].index << "[" << g[ g.target(edge) ].type << "]{" << g[ g.target(edge) ].status<<"}\\n";\n        //std::cout << " t-vals t_min= " << t_min << " t_max= " << t_max << "\\n";\n        //std::cout << "  sites: " << s1->str() << "(k="<< k1<< ") " << s2->str() << "(k="<< k2 << ") new= " << s3->str() << "\\n";\n        std::cout << " s1= " << s1->str2() << "(k=" << k1<< ")\\n";\n        std::cout << " s2= " << s2->str2() << "(k=" << k2<< ")\\n";\n        std::cout << " s3= " << s3->str2() << "\\n";\n        \n        std::cout << "Running solvers again: \\n";\n    }\n    solver_debug(true);\n    // run the solver(s) one more time in order to print out un-filtered solution points for debugging\n    std::vector<solvers::Solution> solutions2;\n    solver_dispatch(s1,k1,s2,k2,s3,+1, solutions2);\n    if (!s3->isPoint()) // for points k3=+1 always\n        solver_dispatch(s1,k1,s2,k2,s3,-1, solutions2); // for lineSite or ArcSite we try k3=-1 also    \n    solver_debug(false);\n    \n    if ( !silent) { \n        if ( !solutions2.empty() ) {\n            std::cout << "The failing " << solutions2.size() << " solutions are: \\n";\n            BOOST_FOREACH(solvers::Solution s, solutions2 ) {\n                std::cout << s.p << " t=" << s.t << " k3=" << s.k3  << " e_err=" << edge_error(s) <<"\\n";\n                std::cout << " min<t<max=" << ((s.t>=t_min) && (s.t<=t_max));\n                std::cout << " s3.in_region=" << s3->in_region(s.p);\n                std::cout <<  " region-t=" << s3->in_region_t(s.p) << "\\n";\n                std::cout <<  " t - t_min= " << s.t - t_min << "\\n";\n                std::cout <<  " t_max - t= " << t_max - s.t << "\\n";\n                std::cout <<  " edge type : " << g[edge].type << "\\n"; //std::scientific;\n            }   \n        } else {\n            std::cout << "No solutions found by solvers!\\n";\n    lll_solver->set_debug(b);\n    qll_solver->set_debug(b);\n    sep_solver->set_debug(b);\n#ifdef ALT_SEP\n    alt_sep_solver->set_debug(b);\n#endif\n}\n\nint VertexPositioner::solver_dispatch(Site* s1, double k1, Site* s2, double k2, Site* s3, double k3, std::vector<Solution>& solns) {\n    VertexError s1_err_functor(g, edge, s1);\n    VertexError s2_err_functor(g, edge, s2);\n    VertexError s3_err_functor(g, edge, s3);\n    \n    if ( !silent) { \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,s2,s3, solns ); // all points, no need to specify k1,k2,k3, they are all +1\n#ifdef ALT_SEP\n    else if ( (s3->isLine() && s1->isPoint() ) || \n              (s1->isLine() && s3->isPoint() ) ||\n              (s3->isLine() && s2->isPoint() ) ||\n    //exit(-1);\n    return desp;\n}\n\n/// search numerically for a desperate solution along the solution-edge\nsolvers::Solution VertexPositioner::desperate_solution(Site* s3) {\n    VertexError err_functor(g, edge, s3);\n    //HEFace face = g[edge].face;     \n    //HEEdge twin = g[edge].twin;\n    //HEFace twin_face = g[twin].face;\n    //Site* s1 =  g[face].site;\n    //Site* s2 = g[twin_face].site;\n    HEVertex src = g.source(edge);\n    HEVertex trg = g.target(edge);\n    Point src_p = g[src].position;\n    Point trg_p = g[trg].position;\n            }\n        }\n    } \n#endif\n    \n    // if we didn\'t dispatch to a solver above, we try the general solver\n    return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver\n    \n    /*\n    if (s1->isLine() && s2->isLine() ) {\n        std::cout << s1->str2() << "\\n";\n        std::cout << s2->str2() << "\\n";\n        std::cout << s3->str2() << "\\n";\n    }\n    boost::array<double,8> x = g[edge].x;\n    boost::array<double,8> y = g[edge].y;\n    for (unsigned int n=0 ; n < 8 ; n++ ) {\n        std::cout << n << "  " << x[n] << "  " << y[n] << "\\n";\n    }\n    \n    for (int n=0 ; n < 20 ; n++ ) {\n        VertexError s1_err_functor(g, edge, s1);\n        VertexError s2_err_functor(g, edge, s2);\n        double ts = t_min + ((t_max-t_min)/(20-1))*n;\n        std::cout << n << " ts=" << ts << " s3_error= " << err_functor(ts) << " p="<< g[edge].point(ts) << "\\n";\n        std::cout << "     s1_err=" << s1_err_functor(ts) << " s2_err=" << s2_err_functor(ts) << "\\n";\n\n    }\n    */\n    \n    typedef std::pair<double, double> Result;\n    Result r = boost::math::tools::brent_find_minima( err_functor, t_min, t_max, 64);\n    double t_sln = r.first;\n    //Point p_sln = g[edge].point(t_sln);\n    Point p_sln = err_functor.edge_point(t_sln); //g[edge].point(t_sln);\n    double desp_k3(0);\n    if (s3->isPoint())\n        desp_k3 = 1;\n    else if ( s3->isLine() ) {\n        // find out on which side the desperate solution lies\n        Point src_se = s3->start();\n        Point trg_se = s3->end();\n        Point left = 0.5*(src_se+trg_se) + (trg_se-src_se).xy_perp(); \n        if (p_sln.is_right(src_se,trg_se)) {\n            desp_k3 = (s3->k()==1) ? -1 : 1;\n        } else {\n            desp_k3 = (s3->k()==1) ? 1 : -1;\n        }\n    }\n    solvers::Solution desp( p_sln, t_sln, desp_k3 ); \n    return desp;\n}\n\n/// set debug output true/false\nvoid VertexPositioner::solver_debug(bool b) {\n    ppp_solver->set_debug(b);\n    lll_solver->set_debug(b);\n    qll_solver->set_debug(b);\n    sep_solver->set_debug(b);\n    alt_sep_solver->set_debug(b);\n    lll_para_solver->set_debug(b);\n}\n\nvoid VertexPositioner::set_silent(bool b) {\n    silent=b;\n    ppp_solver->set_silent(b);\n    lll_solver->set_silent(b);\n    lll_para_solver->set_silent(b);\n    qll_solver->set_silent(b);\n    sep_solver->set_silent(b);\n    alt_sep_solver->set_silent(b);\n}\n    \n/// dispatch to the correct solver based on the sites\nint VertexPositioner::solver_dispatch(Site* s1, double k1, \n                                      Site* s2, double k2, \n                                      Site* s3, double k3, \n                    std::vector<solvers::Solution>& solns) {\n\n\n    if ( g[edge].type == SEPARATOR ) {\n        // this is a SEPARATOR edge with two LineSites adjacent.\n        // find the PointSite that defines the SEPARATOR, so that one LineSite and one PointSite\n        // can be submitted to the Solver.\n        if ( s1->isLine() && s2->isLine() ) {\n            // the parallel lineseg case      v0 --s1 --> pt -- s2 --> v1\n            // find t\n            if ( g[edge].has_null_face ) {\n                s2 = g[ g[edge].null_face ].site;\n                assert( s2->isPoint() ); // the sites of null-faces are allwais PointSite\n                k2 = +1;\n            } else if ( g[ g[edge].twin ].has_null_face ) {\n                s2 = g[ g[ g[edge].twin ].null_face ].site;\n                assert( s2->isPoint() );\n                k2 = +1;\n            }\n        } else if ( s1->isPoint() && s2->isLine() ) {\n            // a normal SEPARATOR edge, defined by a PointSite and a LineSite \n            // swap sites, so SEPSolver can assume s1=line s2=point\n            Site* tmp = s1;\n            double k_tmp = k1;\n            s1 = s2;\n            s2 = tmp;\n            k1 = k2;\n            k2 = k_tmp;\n            assert( s1->isLine() );\n            assert( s2->isPoint() );\n        }\n        assert( s1->isLine() && s2->isPoint() ); // we have previously set s1(line) s2(point)\n        return sep_solver->solve(s1,k1,s2,k2,s3,k3,solns); \n    } else if ( g[edge].type == PARA_LINELINE  && s3->isLine() ) { // an edge betwee parallel LineSites\n        //std::cout << " para lineline! \\n";\n        return lll_para_solver->solve( s1,k1,s2,k2,s3,k3, solns );\n    } else 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,1,s2,1,s3,1, solns ); // all points, no need to specify k1,k2,k3, they are all +1\n    else if ( (s3->isLine() && s1->isPoint() ) || \n              (s1->isLine() && s3->isPoint() ) ||\n              (s3->isLine() && s2->isPoint() ) ||\n              (s2->isLine() && s3->isPoint() ) // bad coverage for this line?\n            ) {\n        // if s1/s2 form a SEPARATOR-edge, this is dispatched automatically to sep-solver\n        // here we detect for a separator case between\n        // s1/s3\n        // s2/s3\n        if (s3->isLine() && s1->isPoint() ) {\n            if ( detect_sep_case(s3,s1) ) {\n                alt_sep_solver->set_type(0);\n                return alt_sep_solver->solve(s1, k1, s2, k2, s3, k3, solns );\n            }\n        }\n        if (s3->isLine() && s2->isPoint() ) {\n            if ( detect_sep_case(s3,s2) ) {\n                alt_sep_solver->set_type(1);\n                return alt_sep_solver->solve(s1, k1, s2, k2, s3, k3, solns );\n            }\n        }\n    } \n    \n    // if we didn\'t dispatch to a solver above, we try the general solver\n    return qll_solver->solve( s1,k1,s2,k2,s3,k3, solns ); // general case solver\n    \n}\n\n/// detect separator-case, so we can dispatch to the correct Solver\nbool VertexPositioner::detect_sep_case(Site* lsite, Site* psite) {\n    HEEdge le = lsite->edge();\n    HEVertex src = g.source(le);\n    HEVertex trg = g.target(le);\n    //std::cout << " detect_sep_case() Linesite from " << g[src].index << " to " << g[trg].index << "\\n";\n    // now from segment end-points get the null-vertex\n    HEEdge src_out;\n    BOOST_FOREACH(HEEdge e, g.out_edge_itr(src) ) {\n        if ( g[e].type == NULLEDGE )\n            src_out = e;\n    }\n    HEEdge trg_out;\n    BOOST_FOREACH(HEEdge e, g.out_edge_itr(trg) ) {\n        if ( g[e].type == NULLEDGE )\n            trg_out = e;\n    }\n    //std::cout << " detect_sep_case() src null-edge "; g.print_edge(src_out); // << g[src].index << " to " << g[trg].index << "\\n";\n    //std::cout << " detect_sep_case() trg null-edge "; g.print_edge(trg_out);\n    \n    HEFace src_null_face = g[src_out].face;\n    if (g[src_null_face].null == false ) {\n        // take twin face instead\n        HEEdge src_out_twin = g[src_out].twin;\n        src_null_face = g[src_out_twin].face;\n    }\n    \n    HEFace trg_null_face = g[trg_out].face;\n    if ( g[trg_null_face].null == false ) {\n        HEEdge trg_out_twin = g[trg_out].twin;\n        trg_null_face = g[trg_out_twin].face;\n    }\n    assert( g[src_null_face].null && g[trg_null_face].null );\n        \n    // do we want src_out face??\n    // OR src_out_twin face??\n    // we want the null-face !\n        \n    //std::cout << " detect_sep_case() src null-face " << src_null_face << "\\n";\n    //g.print_face(src_null_face);\n    //std::cout << " detect_sep_case() trg null-face " << trg_null_face << "\\n";\n    //g.print_face(trg_null_face);\n    \n    Site* src_site = g[src_null_face].site;\n    Site* trg_site = g[trg_null_face].site;\n    if (src_site == NULL || trg_site == NULL ) {\n        exit(-1);\n    }\n    if ( !src_site->isPoint() || !trg_site->isPoint() ) {\n        exit(-1);\n    }\n    //std::cout << " detect_sep_case() src PointSite is "  << src_site->str() << "\\n"; // << src_site->vertex();\n    //std::cout << " detect_sep_case() trg PointSite is "  << trg_site->str() << "\\n";\n    HEVertex src_vertex = src_site->vertex();\n    HEVertex trg_vertex = trg_site->vertex();\n    //std::cout << " detect_sep_case() 1st end-point vertex is " << g[src_vertex].index << "\\n";\n    //std::cout << " detect_sep_case() 2nd end-point vertex is " << g[trg_vertex].index << "\\n";\n    //std::cout << " detect_sep_case() psite is " << psite->str() << "\\n";\n    //std::cout << " detect_sep_case() psite is " << g[psite->vertex()].index << "\\n"; // g[ psite->vertex()].index << "\\n";\n    if ( src_vertex == psite->vertex() ) {\n        //std::cout << " detect_sep_case(): src separator case!\\n";\n        //std::cout << " detect_sep_case(): line is " << g[src].index << " - " << g[trg].index << " with psites " << g[src_vertex].index << " - " << g[trg_vertex].index << "\\n";\n        //std::cout << " detect_sep_case(): psite vertex is " << g[ psite->vertex() ].index << "\\n";\n        return true;\n    }\n    if ( trg_vertex == psite->vertex() ) {\n        //std::cout << " detect_sep_case(): trg separator case!\\n";\n        //std::cout << " detect_sep_case(): line is " << g[src].index << " - " << g[trg].index << " with psites " << g[src_vertex].index << " - " << g[trg_vertex].index << "\\n";\n        //std::cout << " detect_sep_case(): psite vertex is " << g[ psite->vertex() ].index << "\\n";\n\n        return true;\n    }\n    //std::cout << " detect_sep_case()   NOT a separator case.\\n";\n    return false;\n}\n\n/// error from solution to corresponding point on the edge\ndouble VertexPositioner::edge_error(solvers::Solution& sl) {\n    Point p;\n    if (g[edge].type==PARA_LINELINE) {\n        p = projection_point( sl );\n    } else {\n        p = g[edge].point( sl.t );\n    }\n    return (p-sl.p).norm();\n}\n\n/// when the edge is not parametrized by t-value as normal edges\n/// so we need a projection of sl onto the edge instead\nPoint VertexPositioner::projection_point(solvers::Solution& sl) {\n    assert( g[edge].type == PARA_LINELINE );\n    // edge given by\n    // p = p0 + t * (p1-p0)   with t in [0,1]\n    Point p0( g[ g.source(edge) ].position );\n    Point p1( g[ g.target(edge) ].position ); \n    //std::cout << " edge is  " << p0 << " - " << p1 << "\\n";\n    //std::cout << " edge direction: " << v << "\\n";\n    Point v = p1-p0;\n    \n    double t = (sl.p - p0).dot(v) / v.dot(v);\n    // clamp to [0,1]\n    if ( t>1)\n        t=1;\n    else if (t<0)\n        t=0;\n    //std::cout << " projection of solution " << sl.p << " is " << (p0+v*t) << "\\n";\n    return (p0+v*t);\n}\n\n/// check that the new solution lies on the edge\nbool VertexPositioner::solution_on_edge(solvers::Solution& s) {\n    double err = edge_error(s);\n    double limit = 9E-4;\n    if ( err>=limit ) {\n        std::cout << "solution_on_edge() ERROR err= " << err << "\\n";\n        std::cout << " solution edge: " << g[ g.source(edge) ].index << "[" << g[ g.source(edge) ].type<<"]{" << g[ g.source(edge) ].status<<"}";\n        std::cout << " -[" << g[edge].type << "]- ";\n        std::cout << g[ g.target(edge) ].index << "[" << g[ g.target(edge) ].type << "]{" << g[ g.target(edge) ].status<<"}\\n";\n\n\n        std::cout << " edge: " << g[ g.source(edge) ].index << "(t=" << g[ g.source(edge) ].dist() << ")"; \n        std::cout << " - " << g[ g.target(edge) ].index << "(t=" << g[ g.target(edge) ].dist() << ")\\n";\n        std::cout << " edge: " << g[ g.source(edge) ].position << " - " << g[ g.target(edge) ].position << "\\n";\n        std::cout << " solution: " << s.p << " t=" << s.t << "\\n";\n    }\n    return (err<limit);\n}\n\n// calculate the distance from the solution-point to the corresponding point on the edge.\n/*\ndouble VertexPositioner::edge_error(HEEdge e, Solution& s) {\n    Point ep = g[e].point( s.t, s );\n    return (ep-s.p).norm();\n}*/\n\n/// new vertices should lie within the far_radius\nbool VertexPositioner::check_far_circle(solvers::Solution& s) {\n    if (!(s.p.norm() < 18*1)) {\n        std::cout << "WARNING check_far_circle() new vertex outside far_radius! \\n";\n        std::cout << s.p << " norm=" << s.p.norm() << " far_radius=" << 1 << "\\n"; \n        return false;\n    }\n    return true;\n}\n\n/// distance sanity check\n// all vertices should be of degree three, i.e. three adjacent faces/sites\n// distance to the three adjacent sites should be equal\nbool VertexPositioner::check_dist(HEEdge e, const solvers::Solution& sl, Site* s3) {\n    HEFace face = g[e].face;     \n    HEEdge tw_edge = g[e].twin;\n    HEFace twin_face = g[tw_edge].face;      \n    \n    Site* s1 = g[face].site;\n    Site* s2 = g[twin_face].site;\n    \n    double d1 = (sl.p - s1->apex_point(sl.p) ).norm();\n    double d2 = (sl.p - s2->apex_point(sl.p) ).norm();  \n    double d3 = (sl.p - s3->apex_point(sl.p) ).norm(); \n    \n    double maxd = std::max( std::max( fabs(sl.t-d1),fabs(sl.t-d2)) , fabs(sl.t-d3));\n    errstat.push_back(maxd);\n        \n    if ( !equal(d1,d2) || !equal(d1,d3) || !equal(d2,d3) ||\n         !equal(sl.t,d1) || !equal(sl.t,d2) || !equal(sl.t,d3) ) {\n        std::cout << "WARNING check_dist() ! \\n";\n        std::cout << "  sl.t= " << sl.t << "\\n";\n        std::cout << "  d1= " << d1 << "\\n"; \n        std::cout << "  d2= " << d2 << "\\n";\n        std::cout << "  d3= " << d3 << "\\n";\n        std::cout << " solution edge: " << g[ g.source(edge) ].index << "[" << g[ g.source(edge) ].type<<"]{" << g[ g.source(edge) ].status<<"}";\n        std::cout << " -[" << g[edge].type << "]- ";\n        std::cout << g[ g.target(edge) ].index << "[" << g[ g.target(edge) ].type << "]{" << g[ g.target(edge) ].status<<"}\\n";\n    \n        return false;\n    }\n    return true;\n}\n\n/// distance-error\n// new vertices should be equidistant to the three adjacent sites that define the vertex\n// we here calculate the distances d1, d2, d3 from the Solution to the three sites s1, s2, s3\n// and return the max deviation from the solution t-value.\n// this works as a sanity check for the solver.\n// a high error value here is also an indication of numerical instability in the solver\ndouble VertexPositioner::dist_error(HEEdge e, const solvers::Solution& sl, Site* s3) {\n    HEFace face = g[e].face;     \n    HEEdge tw_edge = g[e].twin;\n    HEFace twin_face = g[tw_edge].face;      \n    \n    Site* s1 = g[face].site;\n    Site* s2 = g[twin_face].site;\n    \n    double d1 = (sl.p - s1->apex_point(sl.p) ).norm();\n    double d2 = (sl.p - s2->apex_point(sl.p) ).norm();  \n    double d3 = (sl.p - s3->apex_point(sl.p) ).norm(); \n    \n    return std::max( std::max( fabs(sl.t-d1),fabs(sl.t-d2)) , fabs(sl.t-d3));\n\n}\n\n/// are \\a d1 and \\a d2 roughly equal?\nbool VertexPositioner::equal(double d1, double d2) {\n    double tol = 1e-3;\n    if ( fabs(d1-d2) < 1e-15 )\n        return true;\n    if ( fabs(d1-d2) > tol*std::max(d1,d2) )\n        return false;\n    return true;\n}\n    \n    \n} // end namespace\n', 'message': 'have svg colors match VTK colors roughly\n', 'author_name': 'Anders Wallin', 'lang': 'cpp'}