pm_const_decorator.h

很多二维 三维几何计算算法 C++ 类库

   A |Hole_iterator| can be assigned to a 
   |Halfedge_around_face_const_circulator|.}*/
{ return f->fc_begin(); }

Hole_const_iterator  holes_end(Face_const_handle f) const
/*{\Mop returns the past-the-end iterator of |f|.}*/
{ return f->fc_end(); }

Isolated_vertex_const_iterator 
  isolated_vertices_begin(Face_const_handle f) const
/*{\Mop returns an iterator for all isolated vertices in the interior 
   of |f|.}*/
{ return f->iv_begin(); }

Isolated_vertex_const_iterator 
  isolated_vertices_end(Face_const_handle f) const
/*{\Mop returns the past the end iterator of |f|.}*/
{ return f->iv_end(); }


/*{\Mtext \headerline{Associated Information}\setopdims{2.5cm}{4cm}
The type |Mark| is the general attribute of an object. The type
|GenPtr| is equal to type |void*|.}*/

const Point& point(Vertex_const_handle v) const
/*{\Mop returns the embedding of |v|.}*/
{ return v->point(); }

const Mark& mark(Vertex_const_handle v) const  
/*{\Mop returns the mark of |v|.}*/
{ return v->mark(); }

const Mark& mark(Halfedge_const_handle e) const 
/*{\Mop returns the mark of |e|.}*/
{ if (&*e < &*(e->opposite())) return e->mark();
  else return e->opposite()->mark();
} // we store the mark in the container with smaller memory address !

const Mark& mark(Face_const_handle f) const
/*{\Mop returns the mark of |f|.}*/
{ return f->mark(); }

const GenPtr& info(Vertex_const_handle v) const
/*{\Mop returns a generic information slot.}*/
{ return v->info(); }

const GenPtr& info(Halfedge_const_handle e) const
/*{\Mop returns a generic information slot.}*/
{ return e->info(); }

const GenPtr& info(Face_const_handle f) const
/*{\Mop returns a generic information slot.}*/
{ return f->info(); }


/*{\Mtext \headerline{Statistics and Integrity}}*/

Size_type number_of_vertices() const 
/*{\Mop returns the number of vertices.}*/
{ return phds->size_of_vertices(); }

Size_type number_of_halfedges() const 
/*{\Mop returns the number of halfedges.}*/
{ return phds->size_of_halfedges(); }

Size_type number_of_edges() const    
/*{\Mop returns the number of halfedge pairs.}*/
{ return phds->size_of_halfedges()/2; }

Size_type number_of_faces() const    
/*{\Mop returns the number of faces.}*/
{ return phds->size_of_faces(); }

Size_type number_of_face_cycles() const;
/*{\Mop returns the number of face cycles.}*/

Size_type number_of_connected_components() const;
/*{\Mop calculates the number of connected components of |P|.}*/

void print_statistics(std::ostream& os = std::cout) const
/*{\Mop print the statistics of |P|: the number of vertices, edges, and 
   faces.}*/
{
  os << "Plane Map - Statistics\n";
  os << "|V| = " << number_of_vertices() << std::endl;
  os << "|E| = " << number_of_edges() 
  << " (" << 2*number_of_edges() << ")" << std::endl;
  os << "|F| = " << number_of_faces() << std::endl;
  os << "|Fcs| = " << number_of_face_cycles() << std::endl << std::endl;
}
 
void check_integrity_and_topological_planarity(bool faces=true) const;
/*{\Mop checks the link structure and the genus of |P|.}*/

}; // PM_const_decorator

template <class VH>
std::string PV(VH v)
{ std::ostringstream os; CGAL::set_pretty_mode(os);
  if (v != VH()) os << v->point();
  else           os << "nil";
  return os.str();
}

template <class HH>
std::string PE(HH e)
{ std::ostringstream os;
  if (e==HH()) return "nil";
  os << "[" << PV(e->opposite()->vertex()) << ","
            << PV(e->vertex()) << " " << e->info() << "]";
  return os.str();
}

template <typename HDS>
void PM_const_decorator<HDS>::
check_integrity_and_topological_planarity(bool faces) const
{
  CGAL_NEF_TRACEN("check_integrity_and_topological_planarity:");
  using CGAL::Object_index;
  Object_index<Vertex_const_iterator>   
    VI(vertices_begin(),vertices_end(),'v');
  Object_index<Halfedge_const_iterator> 
    EI(halfedges_begin(),halfedges_end(),'e');
  Object_index<Face_const_iterator> 
    FI(faces_begin(),faces_end(),'f');
  typedef Halfedge_around_vertex_const_circulator hvc_circulator;
  typedef Halfedge_around_face_const_circulator   hfc_circulator;
  Vertex_const_handle vit, vend = phds->vertices_end();
  int iso_vert_num=0;
  /* check the source links of out edges and count isolated vertices */
  for (vit = vertices_begin() ; vit != vend; ++vit) {
    if ( is_isolated(vit) ) {
      if ( faces )
        CGAL_assertion_msg( vit->face() != Face_const_handle(),
                            VI(vit).c_str());
      ++iso_vert_num;
    } else {
      CGAL_assertion_msg( vit->halfedge() != Halfedge_const_handle(),
      VI(vit).c_str());
      CGAL_assertion_msg( vit->halfedge()->vertex() == vit ,VI(vit).c_str());
    }
  }

  /* check the bidirected links and the face pointer init */
  Halfedge_const_iterator eit, eend = phds->halfedges_end();
  for (eit = phds->halfedges_begin() ; eit != eend; ++eit) {
    CGAL_assertion( twin(twin(eit)) == eit );
    CGAL_assertion( eit->vertex() != Vertex_const_handle() );
    CGAL_assertion( next(eit) != Halfedge_const_handle() );
    CGAL_assertion( previous(next(eit)) == eit );
    CGAL_assertion( target(eit) == source(next(eit)) );
    CGAL_assertion( previous(eit) != Halfedge_const_handle() );
    CGAL_assertion( next(previous(eit)) == eit );
    CGAL_assertion( target(previous(eit)) == source(eit) );
    if ( !faces ) continue;
    CGAL_assertion( face(eit) != Face_const_handle() );
    CGAL_assertion( face(next(eit)) == face(eit) );
    CGAL_assertion( face(previous(eit)) == face(eit) );
  }

  bool first=true;
  int fc_num(0),iv_num(0);
  Face_const_iterator fit;
  for (fit = faces_begin(); fit != faces_end(); ++fit) {
    if (!first) {
      CGAL_assertion( face(halfedge(fit))==fit ); ++fc_num;
    }
    Hole_const_iterator fcit;
    for( fcit = holes_begin(fit); fcit != holes_end(fit); ++fcit) {
      CGAL_assertion( face(fcit)==fit ); ++fc_num;
    }
    Isolated_vertex_const_iterator ivit;
    for(ivit = isolated_vertices_begin(fit); 
        ivit != isolated_vertices_end(fit); ++ivit) {
      CGAL_assertion( face(ivit)==fit ); ++iv_num;
    }
    first=false;
  }

  int v_num = number_of_vertices() - iso_vert_num;
  int e_num = number_of_edges();
  int c_num = number_of_connected_components() - iso_vert_num;
  int f_num = number_of_face_cycles() - c_num + 1;
  CGAL_NEF_TRACEV(fc_num);CGAL_NEF_TRACEV(iv_num);CGAL_NEF_TRACEV(iso_vert_num);
  CGAL_NEF_TRACEV(v_num);CGAL_NEF_TRACEV(e_num);CGAL_NEF_TRACEV(c_num);CGAL_NEF_TRACEV(f_num);
  // CGAL_assertion(fc_num == f_num && iv_num == iso_vert_num);
  /* this means all face cycles and all isolated vertices are 
     indeed referenced from a face */
  /* every isolated vertex increases the component count
       one face cycle per component is redundent except one
       finally check the Euler formula: */
  CGAL_assertion( v_num - e_num + f_num == 1 + c_num );
}

template <typename HDS>
typename PM_const_decorator<HDS>::Size_type 
PM_const_decorator<HDS>::
number_of_face_cycles() const
{
  unsigned int fc_num=0;
  CGAL::Unique_hash_map<Halfedge_const_handle,bool> visited; 
    // init with bool() == false
  Halfedge_const_iterator eit =  phds->halfedges_begin();
  Halfedge_const_iterator eend = phds->halfedges_end();
  for ( ; eit != eend; ++eit) {
    if (visited[eit]) continue;
    Halfedge_around_face_const_circulator hfc(eit), hend(hfc);
    CGAL_For_all(hfc,hend) visited[hfc]=true;
    ++fc_num;
  }
  return fc_num;
}

template <typename HDS>
size_t PM_const_decorator<HDS>::
number_of_connected_components() const
{
  typedef Vertex_const_iterator vc_handle;
  typedef Halfedge_around_vertex_const_circulator hvc_circulator;
  int comp_num=0;
  CGAL::Unique_hash_map< vc_handle, bool> handled(false); 
  vc_handle vit = vertices_begin(), vend = vertices_end();
  for ( ; vit != vend; ++vit) {
    if (handled[vit]) continue;
    std::list<vc_handle> L;
    L.push_back(vit); handled[vit]=true; 
    /* we keep the invariant that all nodes which have been stacked
       are marked handled */
    while (!L.empty()) {
      vc_handle v=L.front(); L.pop_front();
      if ( is_isolated(v) ) continue;
      hvc_circulator havc(first_out_edge(v)), hend(havc);
      CGAL_For_all(havc,hend) {
        if (!handled[target(havc)]) {
          L.push_back(target(havc)); handled[target(havc)]=true; 
        }
      }
    }
    ++comp_num;
  }
  return comp_num;   
}

struct KERNELPNT {
  template <typename PNT>
  std::string operator() (const PNT& p) const
  { std::ostringstream os;
    os << "(" << CGAL::to_double(p.x()) << ","
              << CGAL::to_double(p.y()) << ")";
    return os.str();
  }
};

template <typename PMCDEC, typename POINTDA>
void print_as_leda_graph(std::ostream& os, const PMCDEC& D, 
  const POINTDA& P)
{
  typedef typename PMCDEC::Vertex_const_iterator   
  Vertex_const_iterator;
  typedef typename PMCDEC::Halfedge_const_iterator 
  Halfedge_const_iterator;
  int vn(1), en(1);  
  CGAL::Unique_hash_map<Vertex_const_iterator,int>   v_num;
  CGAL::Unique_hash_map<Halfedge_const_iterator,int> e_num;
  os << "LEDA.GRAPH\n" << "point\n" << "int\n";
  os << D.number_of_vertices() << std::endl;
  Vertex_const_iterator vit;
  for (vit = D.vertices_begin(); vit != D.vertices_end(); ++vit) {
    v_num[vit] = vn++;
    os << "|{(" << P(D.point(vit)) << ")}|\n";
     typename PMCDEC::Halfedge_around_vertex_const_circulator
       ecirc(D.first_out_edge(vit)),ecend(ecirc);
    int l=0;
    CGAL_For_all(ecirc,ecend) e_num[ecirc]=l++;
  }
  os << 2* D.number_of_edges() << std::endl;
  Halfedge_const_iterator eit;
  for (eit = D.halfedges_begin(); eit != D.halfedges_end(); ++eit) {
    e_num[eit] = en++;
  }
  for (eit = D.halfedges_begin(); eit != D.halfedges_end(); ++eit) {
    os << v_num[D.source(eit)] << " "
       << v_num[D.target(eit)] << " "
       << e_num[D.twin(eit)]   << " ";
    os << "|{" << e_num[eit] << "}|\n";
  }
  os << std::flush;
}



CGAL_END_NAMESPACE
#endif // CGAL_PM_CONST_DECORATOR_H