/Users/mourrain/Devel/mmx/shape/src/ssi_dsearch_build.cpp

Go to the documentation of this file.

#include <shape/ssi_dsearch.hpp>

namespace mmx {
namespace  shape_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;
};

std::list<dcurve*> * dsearch::reduce( std::vector< dcurve * > * conflicts )
{
  unsigned i;
  if ( conflicts->size() == 0 ) return 0;
  
  unsigned   endsize  = 2*conflicts->size();
  sdpoint_t * ends = new sdpoint_t[endsize];
  
  for ( i = 0; i < endsize; i+= 2 )
    extremums( ends + i, (*conflicts)[i/2] );
      
  sheap_t h;
  build_sheap(h,ends, ends + endsize, 0.04 );
  solve_sheap(h);
  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