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

Go to the documentation of this file.

#include <shape/ssi_dsearch.hpp>

namespace mmx {
namespace  shape_ssi {

// search specialisation s is known to be a leaf
void dsearch::search_f(  qtree f, qtree const s )
{

  if (intersectp(f->box,s->box))
    {
      f->split(this);
      if ( leaf(f) ){ push_f(f,s); return; };
      search_f(f->l,s);
      search_f(f->r,s);
    };
};

// same thing here f is a leaf
void dsearch::search_s(   qtree const f, qtree s )
{

  if ( intersectp( f->box, s->box ) )
    {
      s->split(this);
      if ( leaf(s) ) { push_s(f,s); return; };
      search_s(f,s->l);
      search_s(f,s->r);
    };
};

// search generic case: both f and s are root node
void dsearch::search(  qtree f, qtree s )
{


  // if there bounding boxes intersect
  if ( intersectp(f->box,s->box) )
    {
      // compute if needed the next level in the hierarchy
      f->split(this);
      s->split(this);
      // if f and s are root node
      if ( !(f->leaf()) && !(s->leaf()) )
        {
          // check all the possible intersection between  sons
          search(f->l,s->l), search(f->l,s->r);
          search(f->r,s->l), search(f->r,s->r);
          return;
        };
      
      // s is leaf (not f) switch to specialized case
      if ( !leaf(f) ) 
          {
            search_f(f->l,s);
            search_f(f->r,s);
            return;
          };
        // same thing with f
      if ( !leaf(s) ) 
        {
          search_s(f,s->l);
          search_s(f,s->r);
          return;
        };
        // two unit quad had been reached push the conflict
      // the function push( qtree, qtree ) compute the intersection on the fly if any
      push(f,s);
    };
  };

// launch the search for region i vs region j
void dsearch::search( rid_t i, rid_t j )
{
  curr_config = new std::vector< dcurve* >();
  search( this->trees[i], this->trees[j] ); 
};

}

} //namespace mmx