snc_external_structure.h

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

	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<<-e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	make_twins(e1,e2);
	CGAL_assertion(e1->mark()==e2->mark());
	
	// discard temporary sphere_point ?
      }
    }

    CGAL_forall_iterators(it,M3) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = *itl;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = *itl;
	while(normalized(e1->vector()) != normalized(-e2->vector())) {
	  ++itl;
	  make_twins(e1,*itl);
	  e1 = e2;
	  ++itl;
	  e2 = *itl;
	}
	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<<-e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	make_twins(e1,e2);
	CGAL_assertion(e1->mark()==e2->mark());
	
	// discard temporary sphere_point ?
      }
    }    

    CGAL_forall_iterators(it,M2) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = *itl;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = *itl;
	while(normalized(e1->vector()) != normalized(-e2->vector())) {
	  ++itl;
	  make_twins(e1,*itl);
	  e1 = e2;
	  ++itl;
	  e2 = *itl;
	}
	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<<-e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	make_twins(e1,e2);
	CGAL_assertion(e1->mark()==e2->mark());
	
	// discard temporary sphere_point ?
      }
    }
    
    CGAL_forall_iterators(it,M) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = *itl;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = *itl;
	while(normalized(e1->vector()) != normalized(-e2->vector())) {
	  ++itl;
	  make_twins(e1,*itl);
	  e1 = e2;
	  ++itl;
	  e2 = *itl;
	}
	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<<-e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	make_twins(e1,e2);
	CGAL_assertion(e1->mark()==e2->mark());
	
	// discard temporary sphere_point ?
      }
    }

  }
#else
  void pair_up_halfedges() const {
  /*{\Mop pairs all halfedge stubs to create the edges in 3-space.}*/

//    CGAL_NEF_SETDTHREAD(43*61);
    CGAL_NEF_TRACEN(">>>>>pair_up_halfedges");
    typedef Halfedge_key< Point_3, Halfedge_handle>
      Halfedge_key;
    typedef Halfedge_key_lt< Point_3, Halfedge_handle, SNC_decorator> 
      Halfedge_key_lt;
    typedef std::list<Halfedge_key>  Halfedge_list;
    
    typedef typename Standard_kernel::Kernel_tag   Kernel_tag;
    typedef CGAL::Pluecker_line_3<Kernel_tag,Standard_kernel> Pluecker_line_3;
    typedef CGAL::Pluecker_line_lt        Pluecker_line_lt;
    typedef std::map< Pluecker_line_3, Halfedge_list, Pluecker_line_lt> 
      Pluecker_line_map;
    
    SNC_decorator D(*this);
    Pluecker_line_map M;
    Pluecker_line_map M2;
    Pluecker_line_map M3;
    Pluecker_line_map M4;
    
    NT eval(Infi_box::compute_evaluation_constant_for_halfedge_pairup(*this->sncp()));;
    
    Halfedge_iterator e;
    CGAL_forall_halfedges(e,*this->sncp()) {
      //    progress++;
      Point_3 p = e->source()->point();
      Point_3 q = p + e->vector();
      CGAL_NEF_TRACE(" segment("<<p<<", "<<q<<")"<<
	    " direction("<<e->vector()<<")");
      Standard_point_3 sp = Infi_box::standard_point(p,eval);
      Standard_point_3 sq = Infi_box::standard_point(q,eval);
      Pluecker_line_3  l( sp, sq);
      
      int inverted;
      l = categorize( l, inverted);
      
      if(Infi_box::is_edge_on_infibox(e))
	if(Infi_box::is_type4(e))
	  M4[l].push_back(Halfedge_key(p,inverted,e));
	else
	  if(Infi_box::is_type3(e))
	    M3[l].push_back(Halfedge_key(p,inverted,e));
	  else
	    M2[l].push_back(Halfedge_key(p,inverted,e));
      else
	M[l].push_back(Halfedge_key(p,inverted,e));
      
      // the following trace crashes when compiling with optimizations (-O{n})
      //CGAL_NEF_TRACEN(Infi_box::standard_point(point(vertex(e)))+
      
      CGAL_NEF_TRACEN(" line("<<l<<")"<<" inverted="<<inverted);
    }
    
    typename Pluecker_line_map::iterator it;
    
    CGAL_forall_iterators(it,M4) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = itl->e;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = itl->e;
	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<<-e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	make_twins(e1,e2);
	CGAL_assertion(e1->mark()==e2->mark());
	
	// discard temporary sphere_point ?
      }
    }
    
    CGAL_forall_iterators(it,M3) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = itl->e;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = itl->e;
	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<<-e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	make_twins(e1,e2);
	CGAL_assertion(e1->mark()==e2->mark());
	
	// discard temporary sphere_point ?
      }
    }
    
    CGAL_forall_iterators(it,M2) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = itl->e;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = itl->e;
	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<<-e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	make_twins(e1,e2);
	CGAL_assertion(e1->mark()==e2->mark());
	
	// discard temporary sphere_point ?
      }
    }
    
    CGAL_forall_iterators(it,M) {
      //    progress++;
      it->second.sort(Halfedge_key_lt());
      CGAL_NEF_TRACEN("search opposite  "<<it->first); 
      typename Halfedge_list::iterator itl;
      CGAL_forall_iterators(itl,it->second) {
	Halfedge_handle e1 = itl->e;
	++itl; 
	CGAL_assertion(itl != it->second.end());
	Halfedge_handle e2 = itl->e;
	CGAL_NEF_TRACEN("    " << e1->source()->point() 
			<< " -> " << e2->source()->point());
	CGAL_NEF_TRACEN(e1->vector()<<" -> "<< -e2->vector());
	//	CGAL_assertion(normalized(e1->vector())==normalized(-e2->vector()));
	CGAL_assertion(e1->source()->point() != e2->source()->point());
	CGAL_assertion(e1->mark()==e2->mark());
	make_twins(e1,e2);
	
	// discard temporary sphere_point ?
      }
    }
  }
#endif

  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");

#ifdef CGAL_NEF_EXPLOIT_REFERENCE_COUNTING
    Point_3 p1(1,2,7), p2(p1);     
    bool reference_counted = (&(p1.hx()) == &(p2.hx()));
#endif

    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);
      
#ifdef CGAL_NEF_EXPLOIT_REFERENCE_COUNTING
      if(reference_counted) {
	CGAL_For_all(cet,cete)
	  if ( &(cet->circle().a()) == &(ce->circle().opposite().a()) && 
	       cet->source()->twin() == ce->source() )
	    break;
      } else
#endif
        CGAL_For_all(cet,cete)
	  if ( cet->circle() == ce->circle().opposite() && 
	       cet->source()->twin() == ce->source() ) 
            break;

      // DEBUG     
      if( cet->circle() != ce->circle().opposite() )
	CGAL_NEF_TRACEN("assertion failed!");
      
      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());

      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());
      CGAL_NEF_TRACEN("");

      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;
#ifdef CGAL_NEF_EXPLOIT_REFERENCE_COUNTING
    typedef std::map<Plane_3, Object_list, Plane_RT_lt> 
      Map_planes;
#else
    typedef std::map<Plane_3, Object_list, Plane_lt> 
      Map_planes;
#endif 
   
    Map_planes M;