snc_structure.h

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

    { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*()); return e; }
    operator SHalfloop_handle() const 
    { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*()); return l; }

    operator Object_handle() const { return Ibase::operator*(); }
    Object_handle& operator*() const { return Ibase::operator*(); }
    Object_handle  operator->() const 
    { this->CGAL_nef_assertion_msg(0,"not impl."); return Object_handle(); }
  };

  class SFace_cycle_const_iterator : public Object_const_iterator 
  /*{\Mtypemember a generic iterator to an object in the boundary
  of a facet. Convertible to |Object_handle|.}*/
  { typedef Object_const_iterator Ibase;
  public:
    SFace_cycle_const_iterator() : Ibase() {}
    SFace_cycle_const_iterator(const Ibase& b) : Ibase(b) {}
    SFace_cycle_const_iterator(const SFace_cycle_const_iterator& i) 
      : Ibase(i) {}  
    bool is_svertex() const 
    { SVertex_handle v; return CGAL::assign(v,Ibase::operator*()); }
    bool is_shalfedge() const
    { SHalfedge_handle e; return CGAL::assign(e,Ibase::operator*()); }
    bool is_shalfloop() const
    { SHalfloop_handle l; return CGAL::assign(l,Ibase::operator*()); }
    operator SVertex_const_handle() const 
    { SVertex_handle v; CGAL::assign(v,Ibase::operator*()); 
      return SVertex_const_handle(v); }
    operator SHalfedge_const_handle() const 
    { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*()); 
      return SHalfedge_const_handle(e); }
    operator SHalfloop_const_handle() const 
    { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*()); 
      return SHalfloop_const_handle(l); }

    operator Object_handle() const { return Ibase::operator*(); }
    const Object_handle& operator*() const { return Ibase::operator*(); }
    Object_handle  operator->() const 
    { this->CGAL_nef_assertion_msg(0,"not impl."); return Object_handle(); }
  };


  class Shell_entry_iterator : public Object_iterator 
  /*{\Mtypemember a generic iterator to an object in the boundary
  of a shell. Convertible to |SFace_handle|.}*/
  { typedef Object_iterator Ibase; 
  public:
    Shell_entry_iterator() : Ibase() {}
    Shell_entry_iterator(const Ibase& b) : Ibase(b) {}
    Shell_entry_iterator(const Shell_entry_iterator& i) : Ibase(i) {}  

    operator SFace_handle() const 
    { SFace_handle f; 
      CGAL_assertion( CGAL::assign(f,Ibase::operator*()) );
      CGAL::assign(f,Ibase::operator*()); return f; }

    operator Object_handle() const { return Ibase::operator*(); }
    Object_handle& operator*() const { return Ibase::operator*(); }
    Object_handle  operator->() const 
    { this->CGAL_nef_assertion_msg(0,"not impl."); return Object_handle(); }
  };

  class Shell_entry_const_iterator : public Object_const_iterator 
  { typedef Object_const_iterator Ibase; 
  public:
    Shell_entry_const_iterator() : Ibase() {}
    Shell_entry_const_iterator(const Ibase& b) : Ibase(b) {}
    Shell_entry_const_iterator(const Shell_entry_const_iterator& i) :
      Ibase(i) {}  

    operator SFace_const_handle() const 
    { SFace_handle f; 
      CGAL_assertion( CGAL::assign(f,Ibase::operator*()) );
      CGAL::assign(f,Ibase::operator*()); 
      return SFace_const_handle(f); }

    operator Object_handle() const { return Ibase::operator*(); }
    Object_handle& operator*() const { return Ibase::operator*(); }
    Object_handle  operator->() const 
    { this->CGAL_nef_assertion_msg(0,"not impl."); return Object_handle(); }
  };

  typedef CircFromIt<SHalfedge_const_iterator, 
          move_shalfedge_around_facet<SHalfedge_const_iterator> > 
          SHalfedge_around_facet_const_circulator;

  // Mutable Circulators: 

  typedef CircFromIt<SHalfedge_iterator, 
          move_shalfedge_around_facet<SHalfedge_iterator> > 
          SHalfedge_around_facet_circulator;

#ifdef CGAL_NEF3_FACET_WITH_BOX
  typedef std::pair<SHalfedge_around_facet_circulator,
                    SHalfedge_around_facet_circulator> Outer_cycle;
  typedef std::pair<SHalfedge_around_facet_circulator,
                    SHalfedge_around_facet_circulator> Inner_cycle;
  
  class Partial_facet {
  public:
    Halffacet_handle f;

    std::list<Outer_cycle> outer_cycles;
    std::list<Inner_cycle> inner_cycles;
    std::list<Point_3>     isolated_vertices;

    typedef typename std::list<Outer_cycle>::iterator Outer_cycle_iterator;
    typedef typename std::list<Inner_cycle>::iterator Inner_cycle_iterator;
    typedef typename std::list<Point_3>::iterator Isolated_vertex_iterator;

    Partial_facet() {}

    Partial_facet(const Partial_facet& pf) {
      f = pf.f;
      outer_cycles = pf.outer_cycles;
      inner_cycles = pf.inner_cycles;
      isolated_vertices = pf.isolated_vertices;
    }

    Partial_facet& operator=(const Partial_facet& pf) {
      f = pf.f;
      outer_cycles = pf.outer_cycles;
      inner_cycles = pf.inner_cycles;
      isolated_vertices = pf.isolated_vertices;
      return *this;
    }

    explicit Partial_facet(Halffacet_handle fin) : f(fin) {
      Halffacet_cycle_iterator fc = f->facet_cycles_begin();
      for(;fc != f->facet_cycles_end();++fc) {
	if(fc.is_shalfedge()) {
	  SHalfedge_around_facet_circulator se(fc), se_next(se);
	  ++se_next;
	  if(fc == f->facet_cycles_begin()) {
	    outer_cycles.push_back(Outer_cycle(se, se));
	    //	    outer_cycles.push_back(Outer_cycle(se_next, se));
	  } else {
	    inner_cycles.push_back(Inner_cycle(se, se));
	    //	    inner_cycles.push_back(Inner_cycle(se_next, se));
	  }
	} else if(fc.is_shalfloop()) {
	  SHalfloop_handle l(fc);
	  isolated_vertices.push_back(l->incident_sface()->center_vertex()->point());
	} else
	  CGAL_assertion_msg(false, "wrong value");
      }
    }

    Outer_cycle_iterator outer_cycles_begin() { return outer_cycles.begin(); }
    Inner_cycle_iterator inner_cycles_begin() { return inner_cycles.begin(); }
    Isolated_vertex_iterator isolated_vertices_begin() { return isolated_vertices.begin(); }

    Outer_cycle_iterator outer_cycles_end() { return outer_cycles.end(); }
    Inner_cycle_iterator inner_cycles_end() { return inner_cycles.end(); }
    Isolated_vertex_iterator isolated_vertices_end() { return isolated_vertices.end(); }

    bool divide(const Plane_3& p, Partial_facet& pf1, Partial_facet& pf2) {
      //      std::cerr << "divide " << std::endl;
      //      debug();
      pf1.f = pf2.f = f;
      Outer_cycle_iterator oc = outer_cycles.begin();
      for(;oc != outer_cycles.end(); ++oc) {
	bool next = false;
	//	CGAL_assertion(oc->first != oc->second);
	SHalfedge_around_facet_circulator se = oc->first, se_begin(se), se_new(se), se_end;
	Oriented_side ref = p.oriented_side(se->source()->source()->point()), cur;
	//	std::cerr << "start " << se->source()->source()->point() << ":" << ref << std::endl;
	++se;
	while(ref == ON_ORIENTED_BOUNDARY && se != oc->second) {
	  ref = p.oriented_side(se->source()->source()->point());
	  ++se;
	}
	if(se == oc->second) 
	  return false;

	for(;se != oc->second;++se) {
	  cur = p.oriented_side(se->source()->source()->point());
	  //	  std::cerr << "current " << se->source()->source()->point() << ":" << cur  << std::endl;
	  if(cur != ref) {
	    CGAL_assertion(ref != ON_ORIENTED_BOUNDARY);
	    if(cur == ON_ORIENTED_BOUNDARY) {
	      next = true;
	      continue;
	    }
	    se_end = se;
	    if(next)
	      --se_end;
	    if(cur == ON_NEGATIVE_SIDE) {
	      pf2.outer_cycles.push_back(Outer_cycle(se_begin, se_end));
	    } else if(cur == ON_POSITIVE_SIDE) {
	      pf1.outer_cycles.push_back(Outer_cycle(se_begin, se_end));
	    }
	    se_begin = se_new;
	    if(next)
	      ++se_begin;
	    ref = cur;
	  } else
	      se_new = se;
	  next = false;
	}
	//	std::cerr << "end of cycle " << ref << std::endl;
	if(next) {
	  if(ref == ON_POSITIVE_SIDE) {
	    pf1.outer_cycles.push_back(Outer_cycle(se_new, se));
	    pf2.outer_cycles.push_back(Outer_cycle(se_begin, --se));
	  } else {
	    pf2.outer_cycles.push_back(Outer_cycle(se_new, se));	 
	    pf1.outer_cycles.push_back(Outer_cycle(se_begin, --se));	 
	  }
	} else {
	  if(ref == ON_POSITIVE_SIDE)
	    pf2.outer_cycles.push_back(Outer_cycle(se_begin, se));
	  else if(ref == ON_NEGATIVE_SIDE)
	    pf1.outer_cycles.push_back(Outer_cycle(se_begin, se));
	}
      }

      Inner_cycle_iterator ic = inner_cycles.begin();
      for(;ic != inner_cycles.end(); ++ic) {
	bool next = false;
	SHalfedge_around_facet_circulator se = ic->first, se_begin(se), se_new(se), se_end;
	Oriented_side ref = p.oriented_side(se->source()->source()->point()), cur;
	++se;
	while(ref == ON_ORIENTED_BOUNDARY && se != ic->second) {
	  ref = p.oriented_side(se->source()->source()->point());
	  ++se;
	}
	if(se == ic->second) 
	  return false;

	for(;se != ic->second; ++se) {
	  cur = p.oriented_side(se->source()->source()->point());
	  if(cur != ref) {
	    CGAL_assertion(ref != ON_ORIENTED_BOUNDARY);
	    if(cur == ON_ORIENTED_BOUNDARY) {
	      next = true;
	      continue;
	    }
	    se_end = se;
	    if(next)
	      --se_end;
	    if(cur == ON_NEGATIVE_SIDE) {
	      pf2.inner_cycles.push_back(Inner_cycle(se_begin, se_end));
	    } else if(cur == ON_POSITIVE_SIDE) {
	      pf1.inner_cycles.push_back(Inner_cycle(se_begin, se_end));
	    }
	    se_begin = se_new;
	    if(next)
	      ++se_begin;
	    ref = cur;
	  } else
	      se_new = se;
	  next = false;
	}
	if(next) {
	  if(ref == ON_POSITIVE_SIDE) {
	    pf1.inner_cycles.push_back(Inner_cycle(se_new, se));
	    pf2.inner_cycles.push_back(Inner_cycle(se_begin, --se));
	  } else {
	    pf2.inner_cycles.push_back(Inner_cycle(se_new, se));	 
	    pf1.inner_cycles.push_back(Inner_cycle(se_begin, --se));	 
	  }
	} else {
	  if(ref == ON_POSITIVE_SIDE)
	    pf2.inner_cycles.push_back(Inner_cycle(se_begin, se));
	  else if(ref == ON_NEGATIVE_SIDE)
	    pf1.inner_cycles.push_back(Inner_cycle(se_begin, se));
	}
      }

      Isolated_vertex_iterator iv = isolated_vertices.begin();
      for(;iv != isolated_vertices.end();++iv) {
	Oriented_side side = p.oriented_side(*iv);
	if( side == ON_NEGATIVE_SIDE || side == ON_ORIENTED_BOUNDARY)
	  pf1.isolated_vertices.push_back(*iv);
	if( side == ON_POSITIVE_SIDE || side == ON_ORIENTED_BOUNDARY)
	  pf1.isolated_vertices.push_back(*iv);
      }
      //      std::cerr << "into " << std::endl;
      //      pf1.debug();      
      //      pf2.debug();
      return true;
    }

    void debug() {
      std::cerr << "Partial_facet " << std::endl;
      std::cerr << "Box " << std::endl;
      std::cerr << " " << f->b.min_coord(0) << std::endl;
      std::cerr << " " << f->b.min_coord(1) << std::endl;
      std::cerr << " " << f->b.min_coord(2) << std::endl;
      std::cerr << " " << f->b.max_coord(0) << std::endl;
      std::cerr << " " << f->b.max_coord(1) << std::endl;
      std::cerr << " " << f->b.max_coord(2) << std::endl;

      Outer_cycle_iterator oc = outer_cycles_begin();
      for(; oc != outer_cycles_end(); ++oc) {
	std::cerr << "Outer cycle " << std::endl;
	SHalfedge_around_facet_circulator sb(oc->first), se(oc->second);
	CGAL_For_all(sb,se) {
	  std::cerr << "  " << sb->source()->source()->point() << std::endl;
	}
      }

      Inner_cycle_iterator ic = inner_cycles_begin();
      for(; ic != inner_cycles_end(); ++ic) {
	std::cerr << "Inner cycle " << std::endl;
	SHalfedge_around_facet_circulator sb(ic->first), se(ic->second);
	CGAL_For_all(sb,se) {
	  std::cerr << "  " << sb->source()->source()->point() << std::endl;
	}
      }
    }  
  };

#endif

  /*{\Mcreation 3}*/
  /*{\Mtext |\Mname| is default and copy constructible. Note that copy
  construction means cloning an isomorphic structure and is thus an
  expensive operation.}*/

  SNC_structure() : 
    boundary_item_(boost::none), sm_boundary_item_(boost::none),
    vertices_(), halfedges_(), halffacets_(), volumes_(),
    shalfedges_(), shalfloops_(), sfaces_() {}
  ~SNC_structure() { CGAL_NEF_TRACEN("~SNC_structure: clearing "<<this); clear(); }

  SNC_structure(const Self& D) : 
    boundary_item_(boost::none), sm_boundary_item_(boost::none),
    vertices_(D.vertices_), halfedges_(D.halfedges_), 
    halffacets_(D.halffacets_), volumes_(D.volumes_),
    shalfedges_(D.shalfedges_), shalfloops_(D.shalfloops_), 
    sfaces_(D.sfaces_)
  { pointer_update(D); }

  Self& operator=(const Self& D) { 
    if ( this == &D ) 
      return *this;
    clear();
    boundary_item_.clear(boost::none);
    sm_boundary_item_.clear(boost::none);
    vertices_ = D.vertices_;
    halfedges_ = D.halfedges_;
    halffacets_ = D.halffacets_;
    volumes_ = D.volumes_;
    shalfedges_ = D.shalfedges_;
    shalfloops_ = D.shalfloops_;
    sfaces_ = D.sfaces_;
    pointer_update(D);
    return *this;
  }

  void clear_boundary() {
    boundary_item_.clear(boost::none);
    sm_boundary_item_.clear(boost::none);
  }

  void clear_snc_boundary() {
    boundary_item_.clear(boost::none);
  }

  void clear() { 
    boundary_item_.clear(boost::none);
    sm_boundary_item_.clear(boost::none);
    vertices_.destroy();
    halfedges_.destroy();
    halffacets_.destroy();
    volumes_.destroy();
    shalfedges_.destroy();
    shalfloops_.destroy();
    sfaces_.destroy();
  }

  template <typename H>