snc_structure.h

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

  Vertex_handle new_vertex_only() { 
    vertices_.push_back(* get_vertex_node(Vertex()));
    CGAL_NEF_TRACEN("  new vertex only "<<&*(--vertices_end()));
    return --vertices_end(); 
  }
  Halfedge_handle new_halfedge_only(Halfedge_handle e)  { 
    Halfedge_handle ne = halfedges_.insert(e, * get_halfedge_node(Halfedge()));
    CGAL_NEF_TRACEN("  after "<<&*e<<" new halfedge only "<<&*ne);
    return ne;
  }
  Halfedge_handle new_halfedge_only()  { 
    CGAL_NEF_TRACEN("  new halfedge only "<<&*(--halfedges_end()));
    halfedges_.push_back( * get_halfedge_node(Halfedge()));
    return --halfedges_end();
  }
  Halffacet_handle new_halffacet_only()  { 
    halffacets_.push_back( * get_halffacet_node(Halffacet()));
    CGAL_NEF_TRACEN("  new halffacet only "<<&*(--halffacets_end()));
    return --halffacets_end(); 
  } 
  Volume_handle new_volume_only()  { 
    volumes_.push_back( * get_volume_node(Volume()));
    CGAL_NEF_TRACEN("  new volume only "<<&*(--volumes_end()));
    return --volumes_end(); 
  }
  SHalfedge_handle new_shalfedge_only()  {
    shalfedges_.push_back( * get_shalfedge_node(SHalfedge()));
    CGAL_NEF_TRACEN("  new shalfedge only "<<&*(--shalfedges_end()));
    return --shalfedges_end();
  }
  SHalfedge_handle new_shalfedge_only(SHalfedge_handle se) {
    SHalfedge_handle nse = shalfedges_.insert(se, * get_shalfedge_node(SHalfedge()));
    CGAL_NEF_TRACEN("  after " << &*se << " new shalfedge only " << &*nse);
    return nse;
  }
  SHalfloop_handle new_shalfloop_only()  {
    shalfloops_.push_back( * get_shalfloop_node(SHalfloop()));
    CGAL_NEF_TRACEN("  new shalfloop only "<<&*(--shalfloops_end()));
    return --shalfloops_end(); 
  }
  SFace_handle new_sface_only() {
    sfaces_.push_back( * get_sface_node(SFace()));
    CGAL_NEF_TRACEN("  new sface only "<<&*(--sfaces_end()));
    return --sfaces_end(); 
  }
  SFace_handle new_sface_only(SFace_handle sf) {
    SFace_handle nsf = sfaces_.insert(sf, * get_sface_node(SFace()));
    CGAL_NEF_TRACEN("  after " << &*sf << " new sface only " << &*nsf);
    return nsf;
  }

  void delete_vertex_only(Vertex_handle h) {
    CGAL_NEF_TRACEN("~ deleting vertex only "<<&*h<<" from "<<&*this);
    vertices_.erase(h);
    put_vertex_node(&*h);
  }
  void delete_halfedge_only(Halfedge_handle h) { 
    CGAL_NEF_TRACEN("~ deleting halfedge only "<<&*h<<" from "<<&*this);
    CGAL_assertion(!is_sm_boundary_object(h));
    halfedges_.erase(h);
    put_halfedge_node(&*h);
  }
  void delete_halffacet_only(Halffacet_handle h) { 
    CGAL_NEF_TRACEN("~ deleting halffacet only "<<&*h<<" from "<<&*this);
    halffacets_.erase(h);         
    put_halffacet_node(&*h);
  }
  void delete_volume_only(Volume_handle h) {
    CGAL_NEF_TRACEN("~ deleting volume only "<<&*h<<" from "<<&*this);
    volumes_.erase(h); 
    put_volume_node(&*h);
  }
  void delete_shalfedge_only(SHalfedge_handle h)  { 
    CGAL_NEF_TRACEN("~ deleting shalfedge only "<<&*h<<" from "<<&*this);
    CGAL_assertion(!is_sm_boundary_object(h));
    shalfedges_.erase(h);
    put_shalfedge_node(&*h);
  }
  void delete_shalfloop_only(SHalfloop_handle h)  { 
    CGAL_NEF_TRACEN("~ deleting shalfloop only "<<&*h<<" from "<<&*this);
    CGAL_assertion(!is_sm_boundary_object(h));
    shalfloops_.erase(h); 
    put_shalfloop_node(&*h);
  }
  void delete_sface_only(SFace_handle h)  { 
    CGAL_NEF_TRACEN("~ deleting sface only "<<&*h<<" from "<<&*this);
    CGAL_assertion(!is_boundary_object(h));
    sfaces_.erase(h);
    put_sface_node(&*h);
  }
  
    std::size_t bytes() {
      // bytes used for the SNC_structure

      std::size_t result = sizeof(Self);
      result += number_of_vertices()   * (sizeof(Vertex) 
					  - sizeof(Point_3));
      result += number_of_halfedges()  * (sizeof(Halfedge) 
					  - sizeof(Sphere_point));
      result += number_of_halffacets() * (sizeof(Halffacet)
					  - sizeof(Plane_3));
      result += number_of_volumes()    * sizeof(Volume);
      result += number_of_shalfedges() * (sizeof(SHalfedge)
					  - sizeof(Sphere_circle));
      result += number_of_shalfloops() * sizeof(SHalfloop);
      result += number_of_sfaces()     * sizeof(SFace);

      Halffacet_iterator hf;
      CGAL_forall_halffacets(hf, *this) {
	Halffacet_cycle_iterator fc;
	CGAL_forall_facet_cycles_of(fc, hf)
	  result += sizeof(*fc) + 2 * sizeof(void*);
      }

      Volume_iterator c;
      CGAL_forall_volumes(c, *this) {
	Shell_entry_iterator sei;
	CGAL_forall_shells_of(sei,c) 
	  result += sizeof(*sei) + 2 * sizeof(void*);
      }

      SFace_iterator sf;
      CGAL_forall_sfaces(sf, *this) {
	SFace_cycle_iterator sfc;
	CGAL_forall_sface_cycles_of(sfc,sf)
	  result += sizeof(*sfc) + 2 * sizeof(void*);
      }

      return result;
    }


    std::size_t bytes_reduced() {
      // bytes used for the SNC_structure

      std::size_t result = sizeof(Self);
      result += number_of_vertices()   * (sizeof(Vertex) 
					  - sizeof(Point_3)
					  - sizeof(SHalfloop_iterator)
					  - 2 * sizeof(Mark)
					  - sizeof(void*));
      result += number_of_halfedges()  * (sizeof(Halfedge) 
					  - sizeof(SHalfedge_handle)
					  - sizeof(SFace_handle)
					  - sizeof(void*)
					  - sizeof(Sphere_point));
      result += number_of_halffacets() * (sizeof(Halffacet)
					  - sizeof(Plane_3));
      result += number_of_volumes()    * sizeof(Volume);
      result += number_of_shalfedges() * (sizeof(SHalfedge)
					  - sizeof(SVertex_handle)
					  - 3 * sizeof(SHalfedge_handle)
					  - sizeof(SFace_handle)
					  - sizeof(void*)
					  - sizeof(Mark)
					  - sizeof(Sphere_circle));
      result += number_of_sfaces()     * (sizeof(SFace)
					  - sizeof(void*)
					  - sizeof(Mark)
					  - sizeof(Object_list));

      Halffacet_iterator hf;
      CGAL_forall_halffacets(hf, *this) {
	Halffacet_cycle_iterator fc;
	CGAL_forall_facet_cycles_of(fc, hf)
	  result += sizeof(*fc) + 2 * sizeof(void*);
      }

      Volume_iterator c;
      CGAL_forall_volumes(c, *this) {
	Shell_entry_iterator sei;
	CGAL_forall_shells_of(sei,c) 
	  result += sizeof(*sei) + 2 * sizeof(void*);
      }

      return result;
    }

    std::size_t bytes_reduced2() {
      // bytes used for the SNC_structure

      std::size_t result = sizeof(Self);
      result += number_of_vertices()   * (sizeof(Mark) 
					  + sizeof(SNC_structure*)
					  + sizeof(Object_list)
					  + 2 * sizeof(SFace_handle));
      result += number_of_halfedges()  * (sizeof(Vertex_handle)
					  + sizeof(SVertex_handle)
					  + sizeof(Mark)
					  + 2 * sizeof(Object_handle));
      result += number_of_halffacets() * (sizeof(Halffacet)
					  - sizeof(Plane_3));
      result += number_of_volumes()    * sizeof(Volume);
      result += number_of_shalfedges() * (2 * sizeof(SHalfedge_handle)
					  + sizeof(Halffacet_handle));
      result += number_of_shalfloops() * sizeof(SHalfloop);
      result += number_of_sfaces()     * (sizeof(Vertex_handle)
					  + sizeof(Volume_handle));

      Halffacet_iterator hf;
      CGAL_forall_halffacets(hf, *this) {
	Halffacet_cycle_iterator fc;
	CGAL_forall_facet_cycles_of(fc, hf)
	  result += sizeof(*fc) + 2 * sizeof(void*);
      }

      Volume_iterator c;
      CGAL_forall_volumes(c, *this) {
	Shell_entry_iterator sei;
	CGAL_forall_shells_of(sei,c) 
	  result += sizeof(*sei) + 2 * sizeof(void*);
      }

      return result;
    }

protected:
  void pointer_update(const Self& D);
  
  typedef boost::optional<Object_iterator> Optional_object_iterator ;
  
  Generic_handle_map<Optional_object_iterator> boundary_item_;
  Generic_handle_map<Optional_object_iterator> sm_boundary_item_;

  Vertex_list    vertices_;
  Halfedge_list  halfedges_;
  Halffacet_list halffacets_;
  Volume_list    volumes_;
  SHalfedge_list shalfedges_;
  SHalfloop_list shalfloops_;
  SFace_list     sfaces_;

}; // SNC_structure


template <typename Kernel, typename Items, typename Mark>
void SNC_structure<Kernel,Items,Mark>::
pointer_update(const SNC_structure<Kernel,Items,Mark>& D)
{
  CGAL::Unique_hash_map<Vertex_const_handle,Vertex_handle>       VM;
  CGAL::Unique_hash_map<Halfedge_const_handle,Halfedge_handle>   EM;
  CGAL::Unique_hash_map<Halffacet_const_handle,Halffacet_handle> FM;
  CGAL::Unique_hash_map<Volume_const_handle,Volume_handle>       CM;
  CGAL::Unique_hash_map<SHalfedge_const_handle,SHalfedge_handle> SEM;
  CGAL::Unique_hash_map<SHalfloop_const_handle,SHalfloop_handle> SLM;
  CGAL::Unique_hash_map<SFace_const_handle,SFace_handle>         SFM;
  Vertex_const_iterator vc = D.vertices_begin();
  Vertex_iterator v = vertices_begin();
  for ( ; vc != D.vertices_end(); ++vc,++v) VM[vc] = v;
  VM[D.vertices_end()] = vertices_end();
  Halfedge_const_iterator ec = D.halfedges_begin();
  Halfedge_iterator e = halfedges_begin();
  for ( ; ec != D.halfedges_end(); ++ec,++e) EM[ec] = e;
  EM[D.halfedges_end()] = halfedges_end();
  Halffacet_const_iterator fc = D.halffacets_begin();
  Halffacet_iterator f = halffacets_begin();
  for ( ; fc != D.halffacets_end(); ++fc,++f) FM[fc] = f;
  FM[D.halffacets_end()] = halffacets_end();
  Volume_const_iterator cc = D.volumes_begin();
  Volume_iterator c = volumes_begin();
  for ( ; cc != D.volumes_end(); ++cc,++c) CM[cc] = c;
  CM[D.volumes_end()] = volumes_end();
  SHalfedge_const_iterator sec = D.shalfedges_begin();
  SHalfedge_iterator se = shalfedges_begin();
  for ( ; sec != D.shalfedges_end(); ++sec,++se) SEM[sec] = se;
  SEM[D.shalfedges_end()] = shalfedges_end();
  SHalfloop_const_iterator slc = D.shalfloops_begin();
  SHalfloop_iterator sl = shalfloops_begin();
  for ( ; slc != D.shalfloops_end(); ++slc,++sl) SLM[slc] = sl;
  SLM[D.shalfloops_end()] = shalfloops_end();
  SFace_const_iterator sfc = D.sfaces_begin();
  SFace_iterator sf = sfaces_begin();
  for ( ; sfc != D.sfaces_end(); ++sfc,++sf) SFM[sfc] = sf;
  SFM[D.sfaces_end()] = sfaces_end();

  CGAL_forall_vertices(v,*this) {
    // Local Graph update: (SVertices are postponed/updated as Edges)
    v->sncp() = this;
    v->svertices_begin() = EM[v->svertices_begin()];
    v->svertices_last() = EM[v->svertices_last()];
    v->shalfedges_begin() = SEM[v->shalfedges_begin()];
    v->shalfedges_last() = SEM[v->shalfedges_last()];
    v->sfaces_begin() = SFM[v->sfaces_begin()];
    v->sfaces_last() = SFM[v->sfaces_last()];
    v->shalfloop() = SLM[v->shalfloop()];
  }
  // Halfedge update:
  CGAL_forall_halfedges(e,*this) {
    e->center_vertex() = VM[e->center_vertex()];
    e->twin() = EM[e->twin()];
    e->out_sedge() = SEM[e->out_sedge()];
    e->incident_sface() = SFM[e->incident_sface()];
  }
  // Halffacet update
  CGAL_forall_halffacets(f,*this) {
    f->twin() = FM[f->twin()];
    f->incident_volume() = CM[f->incident_volume()];
    Halffacet_cycle_iterator ftc;
    for(ftc = f->facet_cycles_begin(); ftc !=  f->facet_cycles_end(); ++ftc) {
      if (ftc.is_shalfedge() ) {
	se = SHalfedge_handle(ftc);
	*ftc = Object_handle(SEM[se]); 
	store_boundary_item(se,ftc); 
      } else if (ftc.is_shalfloop() ) {
	sl = SHalfloop_handle(ftc);
	*ftc = Object_handle(SLM[sl]); 
	store_boundary_item(sl,ftc); 
      } else CGAL_assertion_msg(0,"damn wrong boundary item in facet.");
    }
  }

  // Volume update
  CGAL_forall_volumes(c,*this) {
    Shell_entry_iterator sei;
    CGAL_forall_shells_of(sei,c) {
      sf = sei; // conversion from generic iterator to sface const handle
      *sei = Object_handle(SFM[sf]); 
      store_boundary_item(sf,sei); 
    }
  }

  CGAL_forall_shalfedges(se,*this) {
    se->source() = EM[se->source()];
    se->sprev() = SEM[se->sprev()]; se->snext() = SEM[se->snext()];
    se->incident_sface() = SFM[se->incident_sface()];
    se->twin() = SEM[se->twin()];
    se->prev() = SEM[se->prev()]; se->next() = SEM[se->next()];
    se->facet() = FM[se->facet()];
  }

  CGAL_forall_shalfloops(sl,*this) {
    sl->twin() = SLM[sl->twin()];
    sl->incident_sface() = SFM[sl->incident_sface()];
    sl->facet() = FM[sl->facet()];
  }
  for ( slc = D.shalfloops_begin(), sl = shalfloops_begin();
	slc != D.shalfloops_end(); ++slc, ++sl) {
    /* It is possible that the is_twin() property differs for equivalent 
       sloops on both SNC structures.  So, we need to store the correct
       selection mark in the correct (non-twin) facet of a shalfloop pair. */
    CGAL_assertion_code( if( slc->is_twin() == sl->is_twin())
			 CGAL_assertion( slc->mark() == sl->mark()));
    if( !sl->is_twin() && slc->is_twin()) sl->mark() = sl->twin()->mark();
  }

  CGAL_forall_sfaces(sf,*this) {
    sf->center_vertex() = VM[sf->center_vertex()];
    sf->volume() = CM[sf->volume()];
    SFace_cycle_iterator sfc;
    for(sfc = sf->sface_cycles_begin(); 
        sfc != sf->sface_cycles_end(); ++sfc) {
      if (sfc.is_svertex()) { 
	SVertex_handle sv(sfc);
	*sfc = Object_handle(EM[sv]);
	store_sm_boundary_item(sv,sfc);
      } else if (sfc.is_shalfedge()) { 
	se = SHalfedge_handle(sfc);
	*sfc = Object_handle(SEM[se]);
	store_sm_boundary_item(se,sfc);
      } else if (sfc.is_shalfloop()) { 
	sl = SHalfloop_handle(sfc);
	*sfc = Object_handle(SLM[sl]);
	store_sm_boundary_item(sl,sfc);
      } else CGAL_assertion_msg(0,"damn wrong boundary item in sface.");
    }
  }
}

CGAL_END_NAMESPACE
#endif // CGAL_SNC_STRUCTURE_H