/Users/mourrain/Devel/mmx/shape/include/shape/topology2d.hpp

Go to the documentation of this file.

/*****************************************************************************
 * M a t h e m a g i x
 *****************************************************************************
 * TopologyCurve
 * 2008-05-16
 * Bernard Mourrain & Julien Wintz
 *****************************************************************************
 *               Copyright (C) 2008 INRIA Sophia-Antipolis
 *****************************************************************************
 * Comments :
 ****************************************************************************/
# ifndef shape_topology2d_hpp
# define shape_topology2d_hpp

# include <shape/vertex.hpp>
# include <shape/cell.hpp>
# include <shape/kdtree.hpp>
# include <shape/graph.hpp>
# include <shape/list.hpp>
# include <shape/curve.hpp>
# include <shape/algebraic_curve.hpp>
# include <shape/parametric_curve.hpp>
# include <shape/semialgebraic_curve.hpp>
# include <shape/cell2d_list.hpp>
# include <shape/cell2d_intersection.hpp>
# include <shape/cell2d_algebraic_curve.hpp>
# include <shape/cell2d_parametric_curve.hpp>
# include <shape/cell2d_semialgebraic_curve.hpp>
//# include <shape/cell2d_voronoi_site2d.hpp>
//# include <shape/cell2d_voronoi_diagram.hpp>
# include <shape/topology.hpp>

# include <stack>
# define  STACK std::stack<Cell2d*>


# define TMPL template<class C, class V>
# define TMPL1 template<class V>
# define REF REF_OF(V)

//# define Shape SHAPE_OF(V)
# define AlgebraicCurve algebraic_curve<C,V>
# define SemiAlgebraicCurve semialgebraic_curve<C,REF>
# define ParametricCurve parametric_curve<C,REF>
//# define VoronoiSite2d voronoi_site2d<C,REF>
# define Cell2dAlgebraicCurve cell2d_algebraic_curve<C,REF>
# define Cell2dParametricCurve cell2d_parametric_curve<C,REF>
# define Cell2dSemiAlgebraicCurve cell2d_semialgebraic_curve<C,REF>
//# define Cell2dVoronoiSite cell2d_voronoi_site2d<C,REF>
//# define Cell2dVoronoiDiagram cell2d_voronoi_diagram<C,REF>
# define Cell2dList cell2d_list<C,REF>
# define Cell2dInter cell2d_intersection<C,REF>
# define SELF   topology2d<C,V>
# define Viewer viewer<axel,V>
# undef Cell
//====================================================================
namespace mmx {
namespace shape {


// TMPL struct topology2d;

// TMPL struct with_topology2d { 
//   typedef topology2d<K> Topology2d; 
// };

// TMPL struct topology2d_def 
//   :public topology_def<K>
//   ,public with_cell2d<K>
//   ,public with_curve<K>
//   ,public with_topology2d<K>
// {};

TMPL1 class curve ;
TMPL class cell2d_parametric_curve ;
TMPL class cell2d_algebraic_curve;
TMPL class cell2d_list;

                //template <class Object, class CELL> class octree_node;
                //template <class Object, class CELL> class quadtree;
 
template<class C, class V=default_env>
class topology2d: public topology<C,V> {
public:
  typedef topology<C,V> Topology;
  typedef typename topology<C,V>::Point       Point;  
  typedef typename topology<C,V>::Edge        Edge;
  typedef typename topology<C,V>::Face        Face;
  typedef typename topology<C,V>::BoundingBox BoundingBox;
  typedef cell<C,V>         Cell;
  typedef cell2d<C,REF>     Cell2d;
  typedef curve<REF>       Curve;
  
  typedef node<Curve*, Cell*>               Node;
  typedef kdtree<Curve*, Cell*>             Kdtree;

  
public:
  topology2d(const BoundingBox& bx);
  topology2d(Curve * curve) ;
  ~topology2d(void) ;

  void run(void) ;
  
  virtual void insert(Point*);
  virtual void insert(Edge *);
  virtual void insert(Point * p1, Point * p2);

  //    virtual void insert(BoundingBox*, bool);
  virtual void insert_singular(Point*);

protected:
  bool is_regular (Cell * cell) ;
  bool insert_regular(Cell * cell) ;
  bool singularity(Cell * cell) ;
  bool   subdivide(Cell * cell, Node * node) ;
  
  std::list<Node *> m_nodes ;

private:
  Kdtree         *  m_tree ;
  
  static bool active_cell(gNode<Cell2d*>* v)
  {
    return (v->get_aux()>0 );
  }

  static void ccw_walk(gNode<Cell2d*>* v)
  {
    //
  }

public:

  Seq<Point*>         m_vertices;
  Seq<Edge *>         m_edges;
  Seq<Face *>         m_faces;
  
  Graph<Point*>       m_graph;  // topological graph
  
  Graph<Cell2d*>      m_leaves; // active leaves graph
  Graph<Cell2d*>      b_leaves; // border leaves CCW loop
  
  int nbv() const { return m_vertices.size();}
  int nbe() const { return m_edges.size();}
  
  Point*  vertices(int i) const { return m_vertices[i] ; }
  Seq<Edge*> edges(void)  const { return m_edges ; }
  Edge*      edges(int i) const { return m_edges[i] ; }
  
  Seq<Point*>         m_specials;
};

//--------------------------------------------------------------------
// TMPL struct cell2d_factory ;
// TMPL struct cell2d_factory_def
//   :public with_algebraic_curve<K>
//   ,public with_cell2d_algebraic_curve<K>
//   ,public with_cell2d_semialgebraic_curve<K>
// //  ,public with_cell2d_voronoi_site2d<K>
//   ,public with_parametric_curve<K>
//   ,public with_cell2d_parametric_curve<K>
// {};

# define Cell2dFactory cell2d_factory<C,V>
TMPL 
struct cell2d_factory {
public:
  typedef typename SHAPE_OF(V)     Shape;  
  typedef bounding_box<C,REF>      BoundingBox;
  typedef cell<C,REF>                    Cell ;

  static Cell2dFactory * instance(void) {

        if(!m_instance)
            m_instance = new Cell2dFactory ;

        return m_instance ;
    }

  Cell * create(Shape * curve, const BoundingBox& bx) {
    // std::cout<<"create"<<std::endl;
        
    Cell* cell = NULL ;
    if(SemiAlgebraicCurve * isemialg = dynamic_cast<SemiAlgebraicCurve *>(curve))
      {
        cell = new Cell2dSemiAlgebraicCurve(isemialg,bx);
        //std::cout<<"semialg"<<std::endl;
      }
    //else if(VoronoiSite2d * vcurve = dynamic_cast<VoronoiSite2d *>(curve))
    //  {
    //  cell = new Cell2dVoronoiSite(vcurve,bx);
    //  //std::cout<<"voronoi site"<<std::endl;
    //}
    else if(AlgebraicCurve * icurve = dynamic_cast<AlgebraicCurve *>(curve))
      {
        cell = new Cell2dAlgebraicCurve(icurve,bx);
        //std::cout<<"algcurve"<<std::endl;
      }
    else if(ParametricCurve * pcurve = dynamic_cast<ParametricCurve *>(curve))
      {
        cell = new Cell2dParametricCurve(pcurve,bx);
        //std::cout<<"parametric curve"<<std::endl;
      }

    if(cell==NULL) std::cout<<"no dynamic cast cell2d_factory"<<std::endl;
    return cell ;

  }

  Cell * create(const Seq<Shape*>& s, const BoundingBox& bx) {
    Cell * cell = NULL ;
  
    if (s.size()==0) return NULL;
    if (s.size()==1)  return create(s[0],bx);

    if( dynamic_cast<SemiAlgebraicCurve *>(s[0]) )
    {
      Cell2dInter* l= new Cell2dInter(bx);
      //std::cout<<"semialg intersection"<<std::endl;
      foreach(Shape* o, s) l->push_back(create(o,bx)) ;
      cell = l;
    } 
    //else if ( dynamic_cast<VoronoiSite2d *>(s[0]) ) {
    //  Cell2dVoronoiDiagram* l = new Cell2dVoronoiDiagram(bx);
    //  //std::cout<<"voronoi diagram"<<std::endl;
    // foreach(Shape* o, s) l->push_back(create(o,bx)) ;
    //  cell = l;
    //}
    else {
      Cell2dList* l= new Cell2dList(bx);
      // std::cout<<"cell-list"<<std::endl;
      foreach(Shape* o, s) l->push_back(create(o,bx)) ;
      cell = l;
    }
    
    return cell;
  }
  
private:
    cell2d_factory(void) {} ;

private:
    static Cell2dFactory * m_instance;
} ;

TMPL Cell2dFactory*  Cell2dFactory::m_instance = NULL;

//--------------------------------------------------------------------

TMPL 
SELF::topology2d(const BoundingBox& bx) : Topology(bx) {
  m_tree = new Kdtree ;
}

TMPL
SELF::topology2d(Curve * object) : Topology(object->boundingBox()) {
  this->m_objects.push_back(object);
  m_tree = new Kdtree ;
}

TMPL
SELF::~topology2d(void) {
  delete m_tree ;
}

TMPL void 
SELF::run() {
  
  Node* root = m_tree->root() ;

  std::cout<<"Running, objs="<<this->m_objects.size() << std::endl;

  Cell* cl = Cell2dFactory::instance()->create(this->m_objects,this->m_bbx);

  root->set_cell( (Cell*)cl ) ;
  this->m_nodes.push_back(root) ;

  //std::cout<<"RUNing "<< cl <<std::endl;

  // double maxsz = this->m_maxprec*m_tree->root()->get_cell()->size();
  // double minsz = this->m_minprec*m_tree->root()->get_cell()->size();
  double maxsz = this->m_maxprec;
  double minsz = this->m_minprec;

  while(!m_nodes.empty()  ) {   //      
    Node * node = m_nodes.front() ;
    Cell   * cl = node->get_cell() ;
    Cell2d * cl2= dynamic_cast<Cell2d*>(cl);

    //std::cout<<"node "<<cl <<std::endl;

    if(cl->is_active()) {

      //std::cout<<"active.. "<<std::endl;

      if(cl->size() > maxsz) 
        { 
          this->subdivide(cl, node) ;
        }
      else if(this->is_regular(cl) )// && cl->is_intersected())
      { 
        //std::cout<<"ins regular "<<std::endl;
        this->insert_regular(cl) ;
        //std::cout<<"ok "<<std::endl;
        cl2->m_gnode= 
          this->m_leaves.push_vertex(cl2);
        if (  cl2->is_border() )
          this->b_leaves.push_vertex(cl2);       
      }
      else if(cl->size() > minsz)
      { 
        //std::cout<<"subdivide "<<std::endl;
        this->subdivide(cl, node) ;
      }
      else
      { 
        //std::cout<<"singularity "<<std::endl;
        this->singularity(cl) ;
        cl2->m_gnode= 
          this->m_leaves.push_vertex(cl2);
        if (  cl2->is_border() )
          this->b_leaves.push_vertex(cl2);       
      }
    } 
    else    //inactive leaf -- end if
    {
      // cl2->m_gnode= 
      // this->m_leaves.push_vertex(cl2);
        if (  cl2->is_border() )
            this->b_leaves.push_vertex(cl2);       
    }
    this->m_nodes.pop_front() ;
  }

  /* add edges */
  Seq<Cell2d*> nlist;

  std::cout<<"border " << std::endl;
  // Border graph
  this->b_leaves.dfs(nlist);
  foreach(Cell2d* cl2, nlist)
  {
    if (cl2->s_neighbors.size()==0)
      foreach(Cell2d* nb, cl2->e_neighbors )
        if (nlist.member(nb) && nb->s_neighbors.size()==0)
          this->b_leaves.push_edge( cl2,nb ) ;
    if (cl2->e_neighbors.size()==0)
      foreach(Cell2d* nb, cl2->n_neighbors )
        if (nlist.member(nb) && nb->e_neighbors.size()==0)
          this->b_leaves.push_edge( cl2,nb ) ;
    if (cl2->n_neighbors.size()==0)
      foreach(Cell2d* nb, cl2->w_neighbors )
        if (nlist.member(nb)&& nb->n_neighbors.size()==0)
          this->b_leaves.push_edge( cl2,nb ) ;
    if (cl2->w_neighbors.size()==0)
             foreach(Cell2d* nb, cl2->s_neighbors )
               if (nlist.member(nb)&& nb->w_neighbors.size()==0)
                 this->b_leaves.push_edge( cl2,nb ) ;
  }
  nlist.clear();
}


TMPL bool 
SELF::is_regular(Cell * cl) {
  return cl->is_regular();
}

TMPL bool 
SELF::insert_regular(Cell * cl) {
  return cl->insert_regular(this);
}

TMPL bool 
SELF::singularity(Cell * cl) {
  return cl->insert_singular(this) ;
}

TMPL void 
SELF::insert_singular(Point * p) {
  m_specials<<p;
}

TMPL bool 
SELF::subdivide(Cell * cl, Node * node) {
  int v=0;
  
  Cell* left, * right;
  v = cl->subdivide(left, right) ;
  
  node->m_left  = new Node(node, left,  Node::LEFT,  v); 
  m_nodes << node->m_left ;
  node->m_right = new Node(node, right, Node::RIGHT, v); 
  m_nodes << node->m_right;

  return true ;
}

  TMPL void SELF::insert(Point * p) { 
    if(p->index()<0) {
      p->set_index(this->m_vertices.size());
      this->m_vertices << p; 
      this->m_graph.push_vertex(p);
    }
  }

TMPL void SELF::insert(Edge  * e) { 
  this->m_edges    << e;
  this->m_graph.push_uedge(e->source(), e->destination() ); 
}

TMPL void SELF::insert(Point * p1,Point * p2){ 
  this->m_edges << new Edge(p1,p2); 
  this->m_graph.push_uedge(p1,p2); 
}

//--------------------------------------------------------------------
TMPL struct viewer; struct axel;
TMPL Viewer&
operator<<(Viewer& out, const SELF& tp) {
  typedef SELF                        Topology2d;
  typedef typename Topology2d::Point  Point;
  typedef typename Topology2d::Edge   Edge; 
  //shape::edge<K>     Edge;
  //
  
  foreach(Point* p, tp.m_specials) out<<(*p)<<"\n";
  
  out<<" <curve type=\"mesh\">\n<vect>\nVECT\n";
  out<<tp.nbe()<<" "
     <<2*tp.nbe()<<" "
     <<tp.nbe()<<"\n";
  
  for(int i=0; i<tp.nbe();i++) out<<"2 ";
  out<<"\n";
  for(int i=0; i<tp.nbe();i++) out<<"1 ";
  out<<"\n";
  foreach(Edge* e, tp.edges()) {
    out <<e->source()->x()<<" "<<e->source()->y()<<" 0 "
        <<e->destination()->x()<<" "<<e->destination()->y()<<" 0 "
        <<"\n";
  }
  for(int i=0; i<tp.nbe();i++) 
    out<< "0.314 0.979 1 1\n";
  
  out<<" </vect>\n </curve>\n";
  
  return out;
}
//====================================================================
} // namespace shape
} // namespace mmx
//====================================================================
# undef TMPL
# undef AlgebraicCurve
# undef SemiAlgebraicCurve
# undef Cell
# undef Cell2dAlgebraicCurve
# undef Cell2dParametricCurve
# undef Cell2dSemiAlgebraicCurve
# undef Cell2dList
# undef Cell2dInter
# undef Cell2dFactory
# undef Curve
# undef SELF 
# undef Shape
# undef STACK
# undef Viewer
//# undef VoronoiSite2d
# undef ParametricCurve
//# undef Cell2dVoronoiDiagram
# undef Cell2dAlgebraicCurve
#endif