src/ssi_dsearch_build.cpp

Go to the documentation of this file.

#include <shape/ssi/ssi_dsearch.hpp>


namespace mmx {
namespace ssi {

template<class Container>
void search( Container& c, sdpoint_t * first, sdpoint_t * last, double epsilonn ) 
{
    sdknode* root;
    root = make(first,last,dim_cmp<sdpoint_t>());
    for ( sdpoint_t * p = first; p < last; p++ )
        search(c,root,p,0,epsilonn);
    delete root;
};


template<class Container>
void search( Container& c, pdpoint_t * first, pdpoint_t * last, double epsilonn )
{
    pdknode* root;
    pdpoint_t ** tmp = new pdpoint_t*[last-first];
    int i;
    for ( i = 0; i < last-first; i++ )
        tmp[i] = first + i;
    root = make(tmp,tmp + (last-first),dim_cmp<pdpoint_t>());
    delete[] tmp;
    for ( pdpoint_t * p = first; p < last; p++ )
        search(c,root,p,0,epsilonn);
    delete root;
};

template<class Container>
void search( Container& c, sdknode * curr, sdpoint_t * const  query, unsigned dim, double eps  ) 
{
    if (! curr ) return;

    bool left  = (*query)[dim]-eps<(*(curr->data))[dim];
    bool right = (*query)[dim]+eps>(*(curr->data))[dim];

    if ( (left && right) && (query<curr->data) && (curve(query) != curve(curr->data)) )
    {
        double d = distance(curr->data,query);
        if ( (d<eps) )
            container_add(c,assoc_t<sdpoint_t>(query,curr->data,d));
    };
    if ( left  ){  search( c, curr->l, query, (dim+1)%4, eps ); };
    if ( right ){  search( c, curr->r, query, (dim+1)%4, eps ); };
};

template<class Container>
void search( Container& c, pdknode * curr, pdpoint_t * const  query, unsigned dim, double eps  )
{
    if (! curr ) return;

    bool left  = (*query)[dim]-eps<(*(curr->data))[dim];
    bool right = (*query)[dim]+eps>(*(curr->data))[dim];
    if ( (left && right) && (query<curr->data) && (curve(query) != curve(curr->data)) )
    {
        double d = distance(curr->data,query);
        if ( (d<eps) )
            container_add(c,assoc_t<pdpoint_t>(query,curr->data,d));
    };
    if ( left  ){  search( c, curr->l, query, (dim+1)%4, eps ); };
    if ( right ){  search( c, curr->r, query, (dim+1)%4, eps ); };
};


void build_pheap( pheap_t& h, pdpoint_t * first, pdpoint_t * last, double prec )
{
    search(h,first,last,prec);
};

void build_pset( pset_t& s, pdpoint_t * first, pdpoint_t * last, double prec )
{
    search(s,first,last,prec);
};

void build_sheap( sheap_t& h, sdpoint_t * first, sdpoint_t * last, double prec )
{
    search(h,first,last,prec);
};


void solve_pheap( pheap_t& h )
{

    while( !h.empty() )
    {
        pdassc_t a = h.top();

        if (( isextrem(a.pp.first) && isextrem(a.pp.second) ) &&
                ( curve(a.pp.first) != curve(a.pp.second) ))
        {
            link(a.pp.first,a.pp.second);
        };
        h.pop();
    };
};

void solve_sheap( sheap_t& h )
{
    // dcurve * dummy_curve = new dcurve( point2(), point2(), point2(), point2(),
    //                           point3(), point3() );
    while( !h.empty() )
    {
        sdassc_t a = h.top();
        //        cout << a.d << endl;
        if (( isextrem(a.pp.first) && isextrem(a.pp.second) ) &&
                ( curve(a.pp.first) != curve(a.pp.second) ))
            link(a.pp.first,a.pp.second);
        h.pop();
    };
};

sdknode * make( sdpoint_t * first, sdpoint_t * last, const dim_cmp<sdpoint_t>& f ) 
{     
    if ( last-first >= 1 ) {
        if ( last-first > 1 ) {
            unsigned m = (last-first)>>1;
            std::nth_element(first, first+m,last,f);
            return new sdknode( first+m,
                                make( first, first + m, f.next()),
                                make( first+m+1, last,  f.next()) ); }
        else { return new sdknode(first,0,0); };};
    return 0;
};

pdknode * make( pdpoint_t ** first, pdpoint_t ** last, const dim_cmp<pdpoint_t>& f ) 
{     
    if ( last-first >= 1 ) {
        if ( last-first > 1 ) {
            unsigned m = (last-first)>>1;
            std::nth_element(first, first+m,last,f);
            return new pdknode( *(first+m),
                                make( first, first + m, f.next()),
                                make( first+m+1, last,  f.next()) ); }
        else { return new pdknode(*first,0,0); };};
    return 0;
};


void solve_pset( curves_links_t& links, pset_t& s )
{
    while ( !s.empty() )
    {
        pdassc_t ass(sibbles(*(s.begin())));
        pset_iterator it;
        it = s.find( ass  );
        if( it  != s.end() )
        {
            s.erase(s.find(ass));
            cpair_t tmp (curves(*(s.begin())));
            ppair_t p = (s.begin())->pp;
            if ( curve(p.first) != tmp.first )
            {
                links[tmp.second].push_front(p);
                std::swap(p.first,p.second);
                links[tmp.first].push_front(p);
            }
            else
            {
                links[tmp.first].push_front(p);
                std::swap(p.first,p.second);
                links[tmp.second].push_front(p);
            };
        };
        s.erase(s.begin());
    };
};

std::list<dcurve*> * reduce2( std::vector< dcurve * > * conflicts )
{
    if ( conflicts->size() == 0 ) return 0;
    unsigned   i;
    unsigned   endsize  = 4*conflicts->size();
    pdpoint_t * ends = new pdpoint_t[endsize];
    unsigned c = 0;
    for ( i = 0; i < conflicts->size(); i++ )
    {
        extremums( ends + c, (*conflicts)[i] );
        c+= 4;
    };

    pset_t s;
    build_pset(s,ends, ends + endsize, 0.01 );

    curves_links_t links;
    solve_pset(links,s);


    for (  curves_links_t::iterator it = links.begin();
           it != links.end(); it++ )
        satisfy_links( it );

    delete[] ends;

    std::list< dcurve* > * result = new std::list< dcurve * >();

    for ( i = 0; i < conflicts->size() ; i++ )
    {
        if ( empty((*conflicts)[i]) ) delete (*conflicts)[i];
        else result->push_front( (*conflicts)[i] );
    };

    return result;
};

}
} //namespace mmx    

---