snc_simplify.h

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

      while( f_next != D.halffacets_end() && f_next->is_twin());
      CGAL_assertion( f != f->twin());
      Volume_handle c1 = f->incident_volume(), c2 = f->twin()->incident_volume();
      CGAL_NEF_TRACEN(" mark(c1)="<<c1->mark()<<
           	      " mark(f)="<<f->mark() <<
		      " mark(c2)="<<c2->mark()<<
      	              " is_f->twin()="<<f->is_twin());
      if( c1->mark() == f->mark() && f->mark() == c2->mark()
	  && D.is_standard(f)) {
	merge_sets( c1, c2, hash_volume, uf_volume);
	remove_f_including_all_edge_uses_in_its_boundary_cycles
	  (f, hash_sface, uf_sface);
	update_sfaces = update_volumes = true;
	CGAL_NEF_TRACEN("UNION of c1 & c2");
      }
      f = f_next;
    }
    
    CGAL_forall_halffacets( f, *this->sncp()) {
      hash_facet[f] = uf_facet.make_set(f);
      this->sncp()->reset_object_list(f->boundary_entry_objects());
    }
    
    /* 
     * Edges simplification
     */

    Halfedge_iterator e(D.halfedges_begin());
    while( e != D.halfedges_end() && e->is_twin())
      e++;
    while( e != (*this->sncp()).halfedges_end()) {
      CGAL_assertion( !e->is_twin());
      Halfedge_iterator e_next(e);
      do 
	e_next++;
      while( e_next != D.halfedges_end() && e_next->is_twin());
      SM_decorator SD(&*e->source());
      if( SD.is_isolated(e)) {
	if(e->mark() == e->incident_sface()->volume()->mark()) {
	  CGAL_NEF_TRACEN("removing pair ");
	  this->sncp()->delete_halfedge_pair(e);
	  update_facets = true;
	}
      } 
      else { 
	if( D.has_outdeg_two(e)) {
	  SHalfedge_handle e1(SD.first_out_edge(e)); 
	  SHalfedge_handle e2(SD.cyclic_adj_succ(e1));
	  if( e1->circle()==e2->twin()->circle() &&
	      e1->mark()==e->mark() && e->mark()==e2->mark()) {
	    Halffacet_handle f1(e1->facet()); 
	    Halffacet_handle f2(e2->facet());
	    CGAL_NEF_TRACEN("UNION of f1 & f2->twin()");
	    merge_sets( f1, f2->twin(), hash_facet, uf_facet);
	    merge_sets( f1->twin(), f2, hash_facet, uf_facet);
	    CGAL_NEF_TRACEN("removing e");
	    remove_edge_and_merge_facet_cycles(e);
	    update_facets = true;
	  }
	}
      }
      e = e_next;
    }

    update_facets = vertex_simplification() || update_facets;
    purge_no_find_objects(hash_volume, hash_facet, hash_sface, uf_volume, 
			  uf_facet, uf_sface);
    create_boundary_links_forall_sfaces( hash_sface, uf_sface);
    create_boundary_links_forall_facets( hash_facet, uf_facet);
    create_boundary_links_forall_volumes( hash_volume, uf_volume);
    
    CGAL_NEF_TRACEN(">>> simplifying done ");

    return update_sfaces || update_facets || update_volumes;
  }
   
  void remove_edge_and_merge_facet_cycles( Halfedge_handle e) {
    CGAL_assertion_code(SNC_decorator D(*this->sncp()));
    CGAL_assertion( D.has_outdeg_two(e));
    Halfedge_handle et = e->twin();
    CGAL_assertion( D.has_outdeg_two(et));
    CGAL_NEF_TRACEN("source " << e->source()->point());
    CGAL_NEF_TRACEN("target " << et->source()->point());
    SHalfedge_handle e1 = e->out_sedge();
    SHalfedge_handle e2 = e1->prev()->snext();
    merge_sedges_at_target_and_remove_svertex( e1->twin(), e);
    merge_sedges_at_target_and_remove_svertex( e2->twin(), et);
  }

   void merge_sedges_at_target_and_remove_svertex( SHalfedge_handle s1,
						   SVertex_handle v) {
     SNC_decorator D(*this->sncp());
     SM_decorator SD(&*v->source());
     CGAL_assertion( s1->twin()->source() == v);
     SHalfedge_handle s2(s1->snext());
     CGAL_assertion( s2->source() == v);
     //     CGAL_NEF_TRACEN("s1 = " << IO->index(s1));
     //     CGAL_NEF_TRACEN("s2 = " << IO->index(s2));
     if( s1 == s2) {
       //       CGAL_NEF_TRACEN(IO->index(s1)<<'('<<IO->index(s2->twin())<<") to sloop");
       Halffacet_handle f = s1->facet();
       Halffacet_handle facet = s1->facet();
       SD.convert_edge_to_loop(s1);
       CGAL_assertion(SD.shalfloop() != SHalfloop_handle());
       D.add_sloop_to_facet( SD.shalfloop(), f);
       //       CGAL_NEF_TRACEN(IO->index(s2)<<" removed");
     }
     else {
       CGAL_assertion( D.has_outdeg_two(v));
       D.link_as_prev_next_pair( s1, s2->next());
       //       CGAL_NEF_TRACEN(IO->index(s1)<<" "<<IO->index(s2->next())<<" linked.");
       D.link_as_prev_next_pair(s2->next()->twin(), s1->twin());
       //       CGAL_NEF_TRACEN(IO->index(s2->next()->twin())<<" "<<
       //	      IO->index(s1->twin())<<" linked.");
       SD.merge_edge_pairs_at_target( s1); // s2 is removed
       //       CGAL_NEF_TRACEN(IO->index(s2)<<" removed");
     }
   }

   virtual void merge_halfedge_pairs( SVertex_handle p, SVertex_handle q) {
     SNC_decorator D(*this->sncp());
     CGAL_assertion( p->source() == q->source());
     Vertex_handle v(p->source()); 
     CGAL_assertion( is_part_of_edge(v));
     SM_decorator SD(&*v);
     SHalfedge_around_svertex_circulator s(SD.first_out_edge(p)), se(s);
     CGAL_For_all( s, se) {
       D.link_as_prev_next_pair( s->prev(), s->next());
       D.link_as_prev_next_pair( s->twin()->prev(), s->twin()->next());
     }
     D.make_twins( p->twin(), q->twin());
     SD.delete_vertex(p);
     SD.delete_vertex(q);
     this->sncp()->delete_vertex(v);
   }

   void purge_no_find_objects( 
      Unique_hash_map< Volume_handle, UFH_volume>& hash_volume,
      Unique_hash_map< Halffacet_handle, UFH_facet>& hash_facet,
      Unique_hash_map< SFace_handle, UFH_sface>& hash_sface,
      Union_find< Volume_handle>& uf_volume,
      Union_find< Halffacet_handle>& uf_facet,
      Union_find< SFace_handle>& uf_sface ) {
     SNC_decorator D(*this->sncp());
     SFace_iterator sf;
     std::list<SFace_handle> sflist;
     CGAL_forall_sfaces( sf, *this->sncp()) {
       if( uf_sface.find(hash_sface[sf]) != hash_sface[sf]) {
	 //	 CGAL_NEF_TRACEN("no find object "<<IO->index(sf));
	 sflist.push_back(sf);
       }
     }

     typename std::list<SFace_handle>::const_iterator sfli;
     for(sfli = sflist.begin(); sfli != sflist.end(); sfli++){     
       SM_decorator SD(&*(*sfli)->center_vertex());
       SD.delete_face_only(*sfli);
     }

     Halffacet_iterator f;
     std::list<Halffacet_handle> flist;
     CGAL_forall_facets( f, *this->sncp()) {
       //       CGAL_NEF_TRACEN("facet "<<IO->index(f));
       if( uf_facet.find(hash_facet[f]) != hash_facet[f]) {
	 //	 CGAL_NEF_TRACEN("no find object "<<IO->index(f));
	 flist.push_back(f);
       }
     }
     
     typename std::list<Halffacet_handle>::const_iterator fli;
     for(fli = flist.begin(); fli != flist.end(); fli++)
       this->sncp()->delete_halffacet_pair(*fli);

     Volume_iterator c;
     std::list<Volume_handle> clist;
     CGAL_forall_volumes( c, *this->sncp()) {
       if( uf_volume.find(hash_volume[c]) != hash_volume[c]) {
	 //	 CGAL_NEF_TRACEN("no find object "<<IO->index(c));
	 clist.push_back(c);
       }
     }

     typename std::list<Volume_handle>::const_iterator cli;
     for(cli = clist.begin(); cli != clist.end(); cli++){     
       this->sncp()->delete_volume(*cli);
     }
   }

  void create_boundary_links_forall_sfaces(
      Unique_hash_map< SFace_handle, UFH_sface>& hash,
      Union_find< SFace_handle>& uf ) {
    Unique_hash_map< SHalfedge_handle, bool> linked(false);
    SNC_decorator D(*this->sncp());
    SHalfedge_iterator e;
    CGAL_forall_shalfedges(e, *this->sncp()) {
      if( linked[e])
	continue;
      SM_decorator SD(&*e->source()->source());
      SFace_handle sf = *(uf.find(hash[e->incident_sface()]));
      CGAL_assertion( sf != SFace_handle());
      SHalfedge_around_sface_circulator c(e), cend(c);
      CGAL_For_all( c, cend) {
	SD.set_face(c, sf);
	linked[c] = true;
      }
      SD.store_sm_boundary_object( e, sf);
    }

    SVertex_handle sv;
    CGAL_forall_svertices(sv, *this->sncp()) {
      SM_decorator SD(&*sv->source());
      if( SD.is_isolated(sv)) {
	SFace_handle sf = *(uf.find(hash[sv->incident_sface()])); 
	CGAL_assertion( sf != SFace_handle());
	SD.set_face( sv, sf);
	SD.store_sm_boundary_object( sv, sf);
      }
    }

    SHalfloop_handle sl;
    CGAL_forall_shalfloops(sl, *this->sncp()) {
      SM_decorator SD(&*sl->incident_sface()->center_vertex());
      SD.store_sm_boundary_object( sl, sl->incident_sface());
    }
  }

  void create_boundary_links_forall_facets(
      Unique_hash_map< Halffacet_handle, UFH_facet>& hash,
      Union_find< Halffacet_handle>& uf) {
    Unique_hash_map< SHalfedge_handle, bool> linked(false);
    SNC_decorator D(*this->sncp());
    SHalfedge_iterator u;
    CGAL_forall_shalfedges(u, *this->sncp()) {
      if( linked[u])
	continue;
      /* set find(f) as incident facet of every edge use on the cycle of u */
      SHalfedge_handle u_min = u;
      Halffacet_handle f = *(uf.find(hash[u->facet()]));
      SHalfedge_around_facet_circulator c(u), cend(c);
      CGAL_For_all( c, cend) {
	D.set_facet( c, f);
	if( lexicographically_xyz_smaller(c->source()->source()->point(), 
					  u_min->source()->source()->point()))
	  u_min = c;
	linked[c] = true;
      }
      /* store the edge use at the lexicographicaly minimum facet vertex, as
	 a cycle entry of f.  The outermost cycle is stored at first
	 on the facet's cycles list. */
      if( is_empty_range( f->boundary_entry_objects().begin(),
			  f->boundary_entry_objects().end())) {
	D.store_boundary_object( u_min, f);
	CGAL_NEF_TRACEN("new outer cycle min. vertex: "<< u_min->source()->source()->point());
      }
      else {
	SHalfedge_handle f_sedge;
	CGAL_assertion( CGAL::assign( f_sedge, 
				     f->boundary_entry_objects().front()));
	CGAL::assign( f_sedge, f->boundary_entry_objects().front());
	if( lexicographically_xyz_smaller(u_min->source()->source()->point(), 
					  f_sedge->source()->source()->point()))
	  D.store_as_first_boundary_object( u_min, f);
	else
	  D.store_boundary_object( u_min, f);
      }
    }
    SHalfloop_iterator l;
    CGAL_forall_shalfloops( l, *this->sncp()) {
      Halffacet_handle f = *(uf.find(hash[l->facet()]));
      D.set_facet( l, f);
      D.store_boundary_object( l, f);
    }
  }

  void create_boundary_links_forall_volumes( 
      Unique_hash_map< Volume_handle, UFH_volume>& hash,
      Union_find< Volume_handle>& uf) {
    typedef typename SNC_decorator::template Shell_volume_setter<SNC_decorator> Volume_setter;
    //   typedef Unique_hash_map< SFace_handle, bool> SFace_map;
    //  SFace_map linked(false);

    SNC_decorator D(*this->sncp());
    Volume_setter setter(D);

    SFace_iterator sf;
    Volume_handle c;
    CGAL_forall_sfaces(sf, *this->sncp()) {
      //      CGAL_NEF_TRACEN("SFace " << IO->index(sf));
      if( setter.is_linked(sf)) continue;
      c = *(uf.find(hash[sf->volume()]));
      //      CGAL_NEF_TRACEN("Volume " << IO->index(c));
      setter.set_volume(c);
      D.visit_shell_objects( sf, setter );      
      D.store_boundary_object( sf, c);
    }
  }
};


template<typename Items, typename SNC_structure>
class SNC_simplify : public SNC_simplify_base<SNC_structure> {
public:
  SNC_simplify(SNC_structure& sncs)
    : SNC_simplify_base<SNC_structure>(sncs)
  {}
};


template<typename SNC_structure>
class SNC_simplify<SNC_indexed_items, SNC_structure> 
 : public SNC_simplify_base<SNC_structure> {

  typedef SNC_simplify_base<SNC_structure>              Base;
  typedef CGAL::SNC_decorator<SNC_structure>            SNC_decorator;
  typedef typename SNC_structure::Sphere_map            Sphere_map;
  typedef CGAL::SM_decorator<Sphere_map>                SM_decorator;
  
  typedef typename SNC_structure::Vertex_handle Vertex_handle;
  typedef typename SNC_structure::SVertex_handle SVertex_handle;
  typedef typename SNC_structure::SHalfedge_handle SHalfedge_handle;
  typedef typename SNC_structure::SHalfloop_handle SHalfloop_handle;
  typedef typename SNC_structure::Halffacet_iterator Halffacet_iterator; 
  typedef typename SNC_structure::Halffacet_cycle_iterator 
                                  Halffacet_cycle_iterator;
  typedef typename SNC_structure::SHalfedge_around_svertex_circulator 
                                  SHalfedge_around_svertex_circulator;
  typedef typename SNC_structure::SHalfedge_around_facet_circulator 
                                  SHalfedge_around_facet_circulator;

 public:
  SNC_simplify(SNC_structure& sncs) : Base(sncs) {}

  bool simplify() {

    bool result = Base::simplify();

    Halffacet_iterator fit;
    CGAL_forall_halffacets(fit, *this) {
      Halffacet_cycle_iterator fci = fit->facet_cycles_begin();
      SHalfedge_handle se_first = fci;
      int index = se_first->get_index();
      for(; fci!=fit->facet_cycles_end(); ++fci) {
	if(fci.is_shalfedge()) {
	  SHalfedge_around_facet_circulator sc1(fci), sc2(sc1);
	  CGAL_For_all(sc1,sc2)
	    sc1->set_index(index);
	} else if(fci.is_shalfloop()) {
	  SHalfloop_handle sl(fci);
	  sl->set_index(index);
	} else
	  CGAL_assertion_msg(false, "wrong handle");
      }
    }
    
    return result;
  }

  void merge_halfedge_pairs( SVertex_handle p, SVertex_handle q) {
    SNC_decorator D(*this->sncp());
    CGAL_assertion( p->source() == q->source());
    Vertex_handle v(p->source()); 
    CGAL_assertion( is_part_of_edge(v));
    SM_decorator SD(&*v);
    SHalfedge_around_svertex_circulator s(SD.first_out_edge(p)), se(s);
    CGAL_For_all( s, se) {
      D.link_as_prev_next_pair( s->prev(), s->next());
      D.link_as_prev_next_pair( s->twin()->prev(), s->twin()->next());
    }
    D.make_twins( p->twin(), q->twin());
    if(q->get_index() < p->get_index())
      p->twin()->set_index(q->twin()->get_index());
    else
      q->twin()->set_index(p->twin()->get_index());
    SD.delete_vertex(p);
    SD.delete_vertex(q);
    this->sncp()->delete_vertex(v);
  }
};

CGAL_END_NAMESPACE
#endif // CGAL_SNC_STRUCTURE_H