snc_external_structure.h

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

template <typename Items_, typename SNC_structure_>
class SNC_external_structure : public SNC_external_structure_base<Items_, SNC_structure_>
{ 
  typedef CGAL::SNC_decorator<SNC_structure_>                 SNC_decorator;
  typedef CGAL::SNC_point_locator<SNC_decorator>             SNC_point_locator;
public:

  SNC_external_structure( SNC_structure_& W, SNC_point_locator* spl = NULL) 
    : SNC_external_structure_base<Items_, SNC_structure_>(W, spl) 
  {}
};




template <typename SNC_structure_>
class SNC_external_structure<SNC_indexed_items, SNC_structure_> 
  : public SNC_external_structure_base<int, SNC_structure_> {
 
public:
  typedef SNC_structure_                                SNC_structure;
  typedef SNC_external_structure_base<int, SNC_structure>    Base;

  typedef CGAL::SNC_decorator<SNC_structure>                 SNC_decorator;
  typedef CGAL::SNC_point_locator<SNC_decorator>             SNC_point_locator;
  typedef CGAL::SNC_FM_decorator<SNC_structure>              FM_decorator;
  typedef typename SNC_structure::Sphere_map                 Sphere_map;
  typedef CGAL::SM_decorator<Sphere_map>                     SM_decorator;  
  typedef CGAL::SNC_simplify<SNC_indexed_items, SNC_structure> SNC_simplify;

  typedef typename SNC_structure::Halfedge_iterator Halfedge_iterator;
  typedef typename SNC_structure::SHalfedge_iterator SHalfedge_iterator;
  typedef typename SNC_structure::SHalfloop_iterator SHalfloop_iterator;

  typedef typename SNC_structure::Halfedge_handle Halfedge_handle;
  typedef typename SNC_structure::SHalfedge_handle SHalfedge_handle;

  typedef typename SNC_structure::Object_handle Object_handle;

  typedef typename SNC_structure::SHalfedge_around_facet_circulator 
    SHalfedge_around_facet_circulator;
  typedef typename SM_decorator::SHalfedge_around_svertex_circulator 
    SHalfedge_around_svertex_circulator;
  
  typedef typename SNC_structure::Plane_3 Plane_3;

  SNC_external_structure( SNC_structure& W, SNC_point_locator* spl = NULL) 
    : Base(W, spl) {}
  /*{\Mcreate makes |\Mvar| a decorator of |W|.}*/

 public:
  void pair_up_halfedges() const {
    typedef Halfedge_key_lt4<Halfedge_handle>  Halfedge_key_lt;
    typedef std::list<Halfedge_handle>  Halfedge_list;
    typedef std::map<int, Halfedge_list, int_lt> index_map;

    CGAL_NEF_TRACEN("pair up by indexes");

    index_map i2he;
    Halfedge_iterator ei;
    CGAL_forall_halfedges(ei, *this->sncp()) 
      i2he[ei->get_index()].push_back(ei);
    
    typename index_map::iterator it;
    CGAL_forall_iterators(it,i2he) {
      CGAL_NEF_TRACEN("pair up " << it->first);
      it->second.sort(Halfedge_key_lt());
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = *itl;
	CGAL_NEF_TRACEN(e1->source()->point() << ", " << e1->vector());
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = *itl;
	CGAL_NEF_TRACEN(" + " << e2->source()->point() << ", " << e2->vector());
	make_twins(e1,e2);
	//	SNC_io_parser<SNC_structure> O0(std::cerr,*this->sncp());
	//	O0.print();
	CGAL_assertion(e1->mark()==e2->mark());
      }
    }
  }

  void link_shalfedges_to_facet_cycles() const {
  /*{\Mop creates all non-trivial facet cycles from sedges. 
  \precond |pair_up_halfedges()| was called before.}*/
    
  //  CGAL_NEF_SETDTHREAD(43*31);
    CGAL_NEF_TRACEN(">>>>>link_shalfedges_to_facet_cycles");

    Halfedge_iterator e;
    CGAL_forall_edges(e,*this->sncp()) {
      //    progress++;
      CGAL_NEF_TRACEN("");
      CGAL_NEF_TRACEN(PH(e));
      Halfedge_iterator et = e->twin();
      SM_decorator D(&*e->source()), Dt(&*et->source());
      CGAL_NEF_TRACEN(e->source()->point());
      if ( D.is_isolated(e) ) continue;
      SHalfedge_around_svertex_circulator ce(D.first_out_edge(e)),cee(ce);
      SHalfedge_around_svertex_circulator cet(Dt.first_out_edge(et)),cete(cet);
      
      CGAL_For_all(cet,cete) {
	//	std::cerr << cet->get_index() << ", " << ce->twin()->get_index() << std::endl;
	if (cet->get_forward_index() == ce->twin()->get_backward_index())
	    //	    cet->source()->twin() == ce->source())
	  break;
      }

      CGAL_NEF_TRACEN("vertices " << e->source()->point() << 
      "    "      << et->source()->point());
      
      SHalfedge_around_svertex_circulator sc(D.first_out_edge(e));
      SHalfedge_around_svertex_circulator sct(Dt.first_out_edge(et));

      CGAL_NEF_TRACEN("");
      CGAL_For_all(sc,cee)
	CGAL_NEF_TRACEN("sseg@E addr="<<&*sc<<
			" src="<< sc->source()->point()<< 
			" tgt="<< sc->target()->point()<< std::endl << 
			" circle=" << sc->circle()<< std::endl <<
			" indexes=" << sc->get_forward_index() << 
			"," << sc->get_backward_index() << std::endl <<
			"         " << sc->twin()->get_forward_index() <<
			"," << sc->twin()->get_backward_index());
 
      CGAL_NEF_TRACEN("");

      CGAL_For_all(sct,cete)
      CGAL_NEF_TRACEN("sseg@ET addr="<<&*sct<<
		      " src="<< sct->source()->point()<<
		      " tgt="<<sct->target()->point() <<std::endl<<
		      " circle=" << sct->circle() << std::endl<<
		      " indexes=" << sct->get_forward_index() << 
		      "," << sct->get_backward_index() << std::endl <<
		      "         " << sct->twin()->get_forward_index() <<
	              "," << sct->twin()->get_backward_index());
      CGAL_NEF_TRACEN("");

      CGAL_assertion( cet->get_index() == ce->twin()->get_index());
      CGAL_assertion( cet->twin()->get_index() == ce->get_index());
      CGAL_assertion( normalized(cet->circle()) == normalized(ce->circle().opposite()) ); 
      CGAL_assertion( cet->source()->twin() == ce->source()); 
      CGAL_For_all(ce,cee) { 
	CGAL_NEF_TRACEN("circles " << cet->circle() << "   " << ce->circle() << 
			" sources " << cet->target()->point() << 
			"   " << ce->target()->point());
	CGAL_assertion( normalized(cet->circle()) == normalized(ce->circle().opposite())); 
	CGAL_assertion( cet->source()->twin() == ce->source()); 
	CGAL_assertion(ce->mark()==cet->mark());
	link_as_prev_next_pair(cet->twin(),ce);
	link_as_prev_next_pair(ce->twin(),cet);
	--cet; // ce moves ccw, cet moves cw
      }
    }
  }

  void categorize_facet_cycles_and_create_facets() const {
  /*{\Mop collects all facet cycles incident to a facet and creates
  the facets. \precond |link_shalfedges_to_facet_cycles()| was called
  before.}*/

    //    CGAL_NEF_SETDTHREAD(43*31);
    CGAL_NEF_TRACEN(">>>>>categorize_facet_cycles_and_create_facets");
    
    typedef std::list<Object_handle> Object_list;
    typedef std::map<int, Object_list> 
      Map_planes;
   
    Map_planes M;
    SHalfedge_iterator e;
    CGAL_forall_shalfedges(e,*this->sncp()) {
      if(e->get_index() > e->twin()->get_index())
	continue;
      M[e->get_index()].push_back(Object_handle(e));
    }
    SHalfloop_iterator l;
    CGAL_forall_shalfloops(l,*this->sncp()) {
      if(l->get_index() > l->twin()->get_index())
	continue;
      M[l->get_index()].push_back(Object_handle(l));
    }
    
#ifdef CGAL_NEF3_TIMER_PLANE_SWEEPS
  number_of_plane_sweeps=0;
  timer_plane_sweeps.reset();
#endif

    typename Map_planes::iterator it;
    CGAL_forall_iterators(it,M) { 
      CGAL_NEF_TRACEN("  plane "<< it->first);
      CGAL_NEF_TRACEN("  size "<< it->second.size());
      FM_decorator D(*this->sncp());
      Plane_3 h;
      Object_handle o(*it->second.begin());
      if(CGAL::assign(e, o))
	h = e->circle().opposite().plane_through(e->source()->source()->point());
      else if(CGAL::assign(l, o))
	h = l->circle().opposite().plane_through(l->incident_sface()->center_vertex()->point());
      else
	CGAL_assertion_msg(false, "wrong handle");

      D.create_facet_objects(h,it->second.begin(),it->second.end());
    }
    //       CGAL_NEF_SETDTHREAD(1);
  }

  void create_volumes() {
    Base::create_volumes();
  }
   
  void build_external_structure() {
//    CGAL_NEF_SETDTHREAD(503*509);

#ifdef CGAL_NEF3_TIMER_EXTERNAL_STRUCTURE
    CGAL::Timer timer_external_structure;
    timer_external_structure.start();
#endif

#ifdef CGAL_NEF3_TIMER_PLUECKER
    CGAL::Timer timer_pluecker;
    timer_pluecker.start();
#endif
    //    SNC_io_parser<SNC_structure> O0(std::cerr,*this->sncp());
    //    O0.print();
    pair_up_halfedges();
#ifdef CGAL_NEF3_TIMER_PLUECKER
    timer_pluecker.stop();
     if(cgal_nef3_timer_on)
      std::cout << "Runtime_pluecker: " 
		<< timer_pluecker.time() << std::endl;
#endif
     //     SNC_io_parser<SNC_structure> O0(std::cerr,*this->sncp());
     //     O0.print();
    link_shalfedges_to_facet_cycles();

    std::map<int, int> hash;
    CGAL::Unique_hash_map<SHalfedge_handle, bool> done(false);

    SHalfedge_iterator sei;
    CGAL_forall_shalfedges(sei, *this->sncp()) {
      hash[sei->get_index()] = sei->get_index();
    }
    
    CGAL_forall_shalfedges(sei, *this->sncp()) {
      if(done[sei])
	continue;
      SHalfedge_around_facet_circulator circ(sei), end(circ);
      int index = circ->get_index();
      ++circ;
      CGAL_For_all(circ, end)
	if(circ->get_index() < index)
	  index = circ->get_index();      
      index = hash[index];
      CGAL_For_all(circ, end) {
	hash[circ->get_index()] = index;
	circ->set_index(index);
	done[circ] = true;
      }
    }
    
    SHalfloop_iterator sli;
    CGAL_forall_shalfloops(sli, *this->sncp())
      sli->set_index(hash[sli->get_index()]);

    categorize_facet_cycles_and_create_facets();
    create_volumes();

#ifdef CGAL_NEF3_TIMER_EXTERNAL_STRUCTURE
    timer_external_structure.stop();
    if(cgal_nef3_timer_on)
      std::cout << "Runtime_external_structure: " 
		<< timer_external_structure.time() << std::endl;
#endif
  }

  void clear_external_structure() {
    Base::clear_external_structure();    
  }

  template<typename Association>
  void build_after_binary_operation(Association& A) {
    
    SHalfedge_iterator sei;
    CGAL_forall_shalfedges(sei, *this->sncp()) {
      CGAL_NEF_TRACEN("hash sedge " << sei->get_index() 
		      << "->" << A.get_hash(sei->get_index()));
      sei->set_index(A.get_hash(sei->get_index()));
    }

    SHalfloop_iterator sli;
    CGAL_forall_shalfloops(sli, *this->sncp()) {
      CGAL_NEF_TRACEN("hash sloop " << sli->get_index() 
		      << "->" << A.get_hash(sli->get_index()));
      sli->set_index(A.get_hash(sli->get_index()));
    }

    //    CGAL_NEF_SETDTHREAD(43);
    /*
    {    CGAL::SNC_io_parser<SNC_structure> O
      (std::cerr, *this->sncp(), false, true);
      O.print();}
    */
    pair_up_halfedges();
    /*
    {      CGAL::SNC_io_parser<SNC_structure> O
	(std::cerr, *this->sncp(), false, true);
      O.print();}
    */
    link_shalfedges_to_facet_cycles();

    SNC_simplify simp(*this->sncp());
    simp.vertex_simplificationI();

    //    std::map<int, int> hash;
    CGAL::Unique_hash_map<SHalfedge_handle, bool> 
      done(false);

    /*
    SHalfedge_iterator sei;
    CGAL_forall_shalfedges(sei, *this->sncp()) {
      hash[sei->get_forward_index()] = sei->get_forward_index();
      hash[sei->get_backward_index()] = sei->get_backward_index();
    }
    */

    categorize_facet_cycles_and_create_facets();
    create_volumes();
  }
}; 

CGAL_END_NAMESPACE
#endif //CGAL_SNC_EXTERNAL_STRUCTURE_H