snc_decorator.h

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

      //      Mark m1 = SD.mark_of_halfsphere(-1);  
      //      Mark m2 = SD.mark_of_halfsphere(+1);
      //      SM_point_locator PL(vi);
      //      PL.init_marks_of_halfspheres();
      //      valid = valid && (SD.mark_of_halfsphere(-1) == m1);
      //      valid = valid && (SD.mark_of_halfsphere(+1) == m2);
     
      //      CGAL_NEF_TRACEN(m1 << "," << m2 << " should have been " << 
      //	     SD.mark_of_halfsphere(-1) << "," << SD.mark_of_halfsphere(+1));

      valid = valid && (++count <= max);
    }

   verr << "CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;

    Points.sort(points_lt());
    typename std::list<Point_3>::const_iterator li1, li2;
    li2 = li1 = Points.begin();
    if(!Points.empty()) {
      li2++;
      while(valid && li2 != Points.end()) {
	valid = valid && (*li1++ != *li2++);
      }
    }

    verr << "CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;
    
    Halfedge_iterator he;
    CGAL_forall_halfedges(he,*this) {

      valid = valid && he->is_valid(verb, level);
      valid = valid && (he->twin()!=he);
      valid = valid && (he->twin()->twin()==he);

      if(he->is_twin()) {
	SM_decorator S1(&*he->source());
	SM_decorator S2(&*he->twin()->source());
	SHalfedge_handle se1(S1.first_out_edge(he));
	SHalfedge_handle se2(S2.first_out_edge(he->twin()));
	if(se1 != NULL && se2 != NULL) {
	  SHalfedge_handle start1(se1);
	  SHalfedge_handle start2(se2->twin()->snext());
	  while(se1->facet() != se2->twin()->facet() && se2 != start2)
	    se2 = se2->sprev()->twin();

	  start2 = se2;
	  do {
	    se1 = se1->twin()->snext();
	    se2 = se2->sprev()->twin();
	    valid = valid && (se1->facet() == se2->facet()->twin());
	  } while(se1 != start1);
	  valid = valid && (se2 == start2);
	}

	//	Line_3 supporting_line(he->source()->point(), he->point());
	//	valid = valid && supporting_line.has_on(he->twin()->source()->point());
      }
      valid = valid && (++count <= max);
    }

    verr << "CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;

    Unique_hash_map<SHalfedge_handle, bool> SEinUniqueFC(false);
    Halffacet_iterator hfi;
    CGAL_forall_halffacets(hfi,*this) {
      valid = valid && hfi->is_valid(verb, level);
      valid = valid && (hfi->twin()!=hfi);
      valid = valid && (hfi->twin()->twin()==hfi);
      valid = valid && (hfi->plane().opposite() == hfi->twin()->plane()); 
     
      Halffacet_cycle_iterator hfci;
      CGAL_forall_facet_cycles_of(hfci,hfi) { 
	if(hfci.is_shalfedge()) {
	  SHalfedge_handle sheh(hfci);
	  valid = valid && (sheh != SHalfedge_handle());
	  SHalfedge_around_facet_circulator shec1(sheh), shec2(shec1);
       	  CGAL_For_all(shec1, shec2) {
	    CGAL_assertion(!SEinUniqueFC[shec1]);
	    SEinUniqueFC[shec1] = true;
	    Plane_3 p_ref(shec1->source()->source()->point(),shec1->circle().opposite().orthogonal_vector());
	    valid = valid && Infi_box::check_point_on_plane(shec1->source()->source()->point(), hfi->plane());
	    valid = valid && (normalized(hfi->plane()) == normalized(p_ref));
	    valid = valid && (sheh->incident_sface()->volume() == 
			      hfi->twin()->incident_volume());
	  }
	}
	else if(hfci.is_shalfloop())
	  valid = valid && (SHalfloop_handle(hfci) != SHalfloop_handle()); 
	else
	  valid = false;
	valid = valid && (++count <= max);	
      }
      
      valid = valid && (++count <= max);
    }

    verr << "CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;

    Volume_iterator voli;
    CGAL_forall_volumes(voli,*this) {
      
      if(number_of_vertices() > 0)
	valid = valid && (voli->is_valid(verb, level));

      Shell_entry_iterator si;
      CGAL_forall_shells_of(si,voli) {
	//	valid = valid && (si != Shell_entry_iterator() &&
	valid = valid && (SFace_handle(si) != SFace_handle() && 
			  SFace_handle(si) != NULL);
	valid = valid && (++count <= max);
      }
      valid = valid && (++count <= max);
    }

   verr << "CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;

    SHalfedge_iterator she;
    CGAL_forall_shalfedges(she,*sncp()) {
      valid = valid && (she->next() != she);
      valid = valid && (she->prev() != she);
      valid = valid && (she->next()->prev() == she);
      valid = valid && (she->prev()->next() == she);
      valid = valid && (she->next()->twin()->next() == she->twin());
      valid = valid && (she->prev()->twin()->prev() == she->twin());
      valid = valid && (she->facet()->twin() == she->twin()->facet());
      valid = valid && (she->facet()->mark() == she->mark());
      valid = valid && (she->twin()->facet()->incident_volume() == 
			she->incident_sface()->volume());
      valid = valid && (++count <= max);
    }

   verr << "CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;

    SHalfloop_iterator shl;
    CGAL_forall_shalfloops(shl,*sncp()){
      SM_decorator SD;
      valid = valid && (shl->facet()->mark() == shl->mark());
      //      valid = valid && (sh1->twin()->facet()->plane() == sh1->circle()); 
      //      valid = valid && (sh1->twin()->facet()->volume() == sh1->sface()->volume());
    }

    verr << "CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;

    SFace_iterator sf;
    CGAL_forall_sfaces(sf,*sncp()) {
      SM_decorator SD;
      valid = valid && (sf->volume()->mark() == sf->mark());
      SFace_cycle_iterator sfc;
      for(sfc=sf->sface_cycles_begin();sfc!=sf->sface_cycles_end();++sfc)
	if(sfc.is_shalfedge())
	  valid = valid && (sf==SHalfedge_handle(sfc)->incident_sface());
    }

    verr << "end of CGAL::SNC_decorator<...>::is_valid(): structure is "
	 << ( valid ? "valid." : "NOT VALID.") << std::endl;

    return valid;
  }

  template <typename Visitor>
  void visit_shell_objects(SFace_handle f, Visitor& V) const;

  Vertex_iterator   vertices_begin()   { return sncp()->vertices_begin(); }
  Vertex_iterator   vertices_end()     { return sncp()->vertices_end(); }
  Halfedge_iterator halfedges_begin()  { return sncp()->halfedges_begin(); }
  Halfedge_iterator halfedges_end()    { return sncp()->halfedges_end(); }
  Halffacet_iterator halffacets_begin(){ return sncp()->halffacets_begin(); }
  Halffacet_iterator halffacets_end()  { return sncp()->halffacets_end(); }
  Volume_iterator   volumes_begin()    { return sncp()->volumes_begin(); }
  Volume_iterator   volumes_end()      { return sncp()->volumes_end(); }
  SVertex_iterator   svertices_begin() { return sncp()->svertices_begin(); }
  SVertex_iterator   svertices_end()   { return sncp()->svertices_end(); }
  SHalfedge_iterator shalfedges_begin(){ return sncp()->shalfedges_begin(); }
  SHalfedge_iterator shalfedges_end()  { return sncp()->shalfedges_end(); }
  SHalfloop_iterator shalfloops_begin(){ return sncp()->shalfloops_begin(); }
  SHalfloop_iterator shalfloops_end()  { return sncp()->shalfloops_end(); }
  SFace_iterator   sfaces_begin() { return sncp()->sfaces_begin(); }
  SFace_iterator   sfaces_end()   { return sncp()->sfaces_end(); }

  Shell_entry_iterator shells_begin(Volume_handle c) {
    return c->shells_begin();
  }
  Shell_entry_iterator shells_end(Volume_handle c) {
    return c->shells_end();
  }

  Size_type number_of_vertices() const  
  { return sncp()->number_of_vertices(); }
  Size_type number_of_halfedges() const 
  { return sncp()->number_of_halfedges(); }
  Size_type number_of_edges() const     
  { return sncp()->number_of_edges(); }
  Size_type number_of_halffacets() const    
  { return sncp()->number_of_halffacets();}
  Size_type number_of_facets() const    
  { return sncp()->number_of_facets();}
  Size_type number_of_volumes() const   
  { return sncp()->number_of_volumes();}

};

/* visiting shell objects:

Objects are marked as done, when placed in the output list.  We have
to maintain a stack of sface candidates (the spherical rubber sectors
that provide connectivity at the local graphs of vertices) and facet
candiates (the plane pieces in three space also providing
connectivity). Note that we have to take care about the orientation of
sobjects and facets. We have to take care that (1) the search along
the shell extends along the whole shell structure (2) does not visit
any object twice, and (3) all 3-space objects have to be reported and
this also just once.

The facets and sfaces are marked |done| when they are put into their
corresponding queues thus each such object is visited exactly once
when taken out of the queue. 

When an sface |sf| is taken out of the queue |SFaceCandiates| its
boundary structure is examined and all 2-skeleton objects (vertices
and edges of 3-space) that are incident to the volume represented by
|sf| are reported. Facets are reported when they are taken out of
|FacetCandiates|.

*/

template <typename EW>
template <typename Visitor>
void SNC_decorator<EW>::
visit_shell_objects(SFace_handle f, Visitor& V) const
{ 
  typedef typename SM_decorator::SHalfedge_around_sface_circulator 
    SHalfedge_around_sface_circulator;
  std::list<SFace_handle> SFaceCandidates;
  std::list<Halffacet_handle> FacetCandidates;
  CGAL::Generic_handle_map<bool> Done(false);
  SFaceCandidates.push_back(f);  Done[f] = true;
  while ( true ) {
    if ( SFaceCandidates.empty() && FacetCandidates.empty() ) break;
    if ( !FacetCandidates.empty() ) {
      Halffacet_handle f = *FacetCandidates.begin();
      FacetCandidates.pop_front();
      V.visit(f); // report facet
      Halffacet_cycle_iterator fc;
      CGAL_forall_facet_cycles_of(fc,f) {
        if (fc.is_shalfedge() ) {
	  SHalfedge_handle e(fc);
          SHalfedge_around_facet_circulator ec(e),ee(e);
          CGAL_For_all(ec,ee) { e = ec->twin();
            if ( Done[e->incident_sface()] ) continue;
            SFaceCandidates.push_back(e->incident_sface());
            Done[e->incident_sface()] = true;
          }
        } else if (fc.is_shalfloop()) {
	  SHalfloop_handle l(fc);
	  l = l->twin();
          if ( Done[l->incident_sface()] ) continue;
          SFaceCandidates.push_back(l->incident_sface());
          Done[l->incident_sface()] = true;
        } else CGAL_assertion_msg(0,"Damn wrong handle.");
      }
    }
    if ( !SFaceCandidates.empty() ) {
      SFace_handle sf = *SFaceCandidates.begin();
      SFaceCandidates.pop_front();
      V.visit(sf); // report sface
      if ( !Done[sf->center_vertex()] )
        V.visit(sf->center_vertex()); // report vertex
      Done[sf->center_vertex()] = true;
      //      SVertex_handle sv;
      SM_decorator SD(&*sf->center_vertex());
      /*      
      CGAL_forall_svertices(sv,SD){
	if(SD.is_isolated(sv) && !Done[sv])
	  V.visit(sv);
      }
      */
      SFace_cycle_iterator fc;
      CGAL_forall_sface_cycles_of(fc,sf) {
        if ( fc.is_shalfedge() ) {
	  SHalfedge_handle e(fc);
	  SHalfedge_around_sface_circulator ec(e),ee(e);
          CGAL_For_all(ec,ee) {
	    V.visit(SHalfedge_handle(ec));
            SVertex_handle v = ec->twin()->source();
            if ( !SD.is_isolated(v) && !Done[v] ) {
              V.visit(v); // report edge
              Done[v] = Done[v->twin()] = true;
            }
            Halffacet_handle f = ec->twin()->facet();
            if ( Done[f] ) continue;
            FacetCandidates.push_back(f); Done[f] = true;
          }
        } else if ( fc.is_svertex() ) {
	  SVertex_handle v(fc);
          if ( Done[v] ) continue; 
          V.visit(v); // report edge
	  V.visit(v->twin());
          Done[v] = Done[v->twin()] = true;
	  CGAL_assertion(SD.is_isolated(v));
	  SFaceCandidates.push_back(v->twin()->incident_sface());
	  Done[v->twin()->incident_sface()]=true;
          // note that v is isolated, thus v->twin() is isolated too
	  //	  SM_decorator SD;
	  //	  SFace_handle fo;
	  //	  fo = v->twin()->incident_sface();
	  /*
	  if(SD.is_isolated(v)) 
	    fo = v->source()->sfaces_begin();
	  else
	    fo = v->twin()->incident_sface();
	  */
	  //	  if ( Done[fo] ) continue;
	  //	  SFaceCandidates.push_back(fo); Done[fo] = true;
        } else if (fc.is_shalfloop()) {
	  SHalfloop_handle l(fc);
	  V.visit(l);
          Halffacet_handle f = l->twin()->facet();
          if ( Done[f] ) continue;
          FacetCandidates.push_back(f);  Done[f] = true;
        } else CGAL_assertion_msg(0,"Damn wrong handle.");
      }
    }
  }
}



CGAL_END_NAMESPACE
#endif //CGAL_SNC_DECORATOR_H