sm_overlayer.h

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

    SVertex_const_iterator v;
    CGAL_forall_svertices(v,PI[i]) {
      CGAL_NEF_TRACEN(v->point() << " from " << i << " mark " << v->mark());
      if ( !PI[i].is_isolated(v) ) continue;
      L.push_back(trivial_segment(PI[i],v));
      From[--L.end()] = Seg_info(v,i);
    }
    SHalfedge_const_iterator e;
    CGAL_forall_sedges(e,PI[i]) {
      if ( e->source() == e->target() ) {
       if(with_trivial_segments) {
          v = e->source();
          L.push_back(trivial_segment(PI[i],v));
          From[--L.end()] = Seg_info(v,i);
        } else {
          Seg_pair p = two_segments(PI[i],e);
          L.push_back(p.first);
          L.push_back(p.second);
          From[--L.end()] = From[--(--L.end())] = Seg_info(e,i);
        }
      } else {
        L.push_back(segment(PI[i],e));
        From[--L.end()] = Seg_info(e,i);
      }
    }
    if ( PI[i].has_shalfloop() ) {
      SHalfloop_const_handle shl = PI[i].shalfloop();
      Seg_pair p = two_segments(PI[i],shl);
      L.push_back(p.first); 
      L.push_back(p.second.opposite());
      From[--L.end()] = From[--(--L.end())] = 
        Seg_info(shl,i);
    }
  }

  CGAL_assertion_code(typename Seg_list::iterator it);
  CGAL_assertion_code(CGAL_forall_iterators(it,L) CGAL_NEF_TRACEN("  "<<*it));
  bool compute_halfsphere[3][2];
#ifdef CGAL_NEF3_SPHERE_SWEEP_OPTIMIZATION_OFF
  int cs = -1;
  compute_halfsphere[2][0]=true;
  compute_halfsphere[2][1]=true;
#else
  int cs = check_sphere(L, compute_halfsphere);
#endif

  CGAL_NEF_TRACEN("compute_halfsphere\n  cs = " << cs);
  for(int i=0; i<6; ++i)
    CGAL_NEF_TRACEN("  " << i << " : " << compute_halfsphere[i/2][i%2]);
  Seg_list L_pos,L_neg;

  switch(cs) {
  case 1: 
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(1,0,0), Sphere_circle(0,0,-1),
			    compute_halfsphere[0][1]);
    break;
  case 0:
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(-1,0,0), Sphere_circle(0,0,-1),
			    compute_halfsphere[0][0]);
    break;
  case 3: 
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(0,1,0), Sphere_circle(1,0,0),
			    compute_halfsphere[1][1]);
    break;
  case 2:
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(0,-1,0), Sphere_circle(1,0,0), 
			    compute_halfsphere[1][0]);
    break;
  case 5: 
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(0,0,1), Sphere_circle(1,0,0),
			    compute_halfsphere[2][1]);
    break;
  case 4:
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(0,0,-1), Sphere_circle(1,0,0), 
			    compute_halfsphere[2][0]);
    break;
  case -1:
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);
    break;
  default: CGAL_assertion_msg(0, "wrong value");
  }

  cs = cs==-1 ? 2 : cs/2;

#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
  timer_sphere_sweeps.start();
#endif
  
  typedef SMO_from_sm<Self,Seg_iterator,Seg_info> SM_output;
  typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
  typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
  
  typedef CGAL::Segment_overlay_traits< 
    Seg_iterator, SM_output, PH_geometry>  PHS_traits;
  typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;
    
  typedef CGAL::Segment_overlay_traits< 
    Seg_iterator, SM_output, NH_geometry> NHS_traits;
  typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;

  typedef typename PHS_traits::INPUT Input_range;

  SVertex_handle v;
  SHalfedge_handle e;
  SM_output O(*this,PI,From); 

  if(compute_halfsphere[cs][0]) {
    PH_geometry phg(cs);
    Positive_halfsphere_sweep SP(
	Input_range(L_pos.begin(),L_pos.end()),O,phg);
    SP.sweep();
    v=--this->svertices_end(); e=--this->shalfedges_end();
#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
    number_of_sphere_sweeps++;
#endif
  }

  if(compute_halfsphere[cs][1]) {
    NH_geometry nhg(cs);
    Negative_halfsphere_sweep SM(
        Input_range(L_neg.begin(),L_neg.end()),O,
        nhg);
    SM.sweep();
#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
    number_of_sphere_sweeps++;
#endif
  }

#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
  timer_sphere_sweeps.stop();
#endif

  if(compute_halfsphere[cs][0]) {
    ++v; 
    ++e;
  }
  else {
    v = this->svertices_begin(); 
    e = this->shalfedges_begin();
  }

  if(compute_halfsphere[cs][0])
    create_face_objects(this->shalfedges_begin(), e, this->svertices_begin(), v, O,
                        PH_geometry(cs));
  if(compute_halfsphere[cs][1])
    create_face_objects(e, this->shalfedges_end(), v, this->svertices_end(), O,
			NH_geometry(cs));

  CGAL_forall_sedges(e,*this) {
    e->circle() = Sphere_circle(e->source()->point(), e->twin()->source()->point()); 
    e->twin()->circle() = e->circle().opposite();
    CGAL_NEF_TRACEN(PH(e) << " with circle " << e->circle());
  }

  std::vector<Mark> mohs(4);
  SM_point_locator L0(M0);
  SM_point_locator L1(M1);
  
  L0.marks_of_halfspheres(mohs, 0, cs);
  L1.marks_of_halfspheres(mohs, 2, cs);

  CGAL_NEF_TRACEN("mohs[0]=" << mohs[0]);
  CGAL_NEF_TRACEN("mohs[1]=" << mohs[1]);
  CGAL_NEF_TRACEN("mohs[2]=" << mohs[2]);
  CGAL_NEF_TRACEN("mohs[3]=" << mohs[3]);

  CGAL_NEF_TRACEN("compute_halfsphrere\n  cs = " << cs << 
	 "\n  [cs][0] = " << compute_halfsphere[cs][0] <<
	 "\n  [cs][1] = " << compute_halfsphere[cs][1]);
  /*
  SVertex_iterator svii;
  CGAL_forall_svertices(svii, *this) {
    SVertex_const_handle vs;
    SHalfedge_const_handle es;
    if(CGAL::assign(vs, supp_object(svii,0)))
      std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
    else if(CGAL::assign(es, supp_object(svii,0)))
      std::cerr << svii->point() << " supported by sedge" << std::endl;
    else
      std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
    if(CGAL::assign(vs, supp_object(svii,1)))
      std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
    else if(CGAL::assign(es, supp_object(svii,1)))
      std::cerr << svii->point() << " supported by sedge" << std::endl;
    else
      std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
  }
  */
  if(compute_halfsphere[cs][0])
    complete_face_support(this->svertices_begin(), v, O, mohs, 0, 
			  compute_halfsphere[cs][1]);
  if(compute_halfsphere[cs][1])
    complete_face_support(v, this->svertices_end(), O, mohs, 1,
			  compute_halfsphere[cs][0]);

  complete_sface_marks();

  // DEBUG CODE: to do: have all svertices a halfedge below associated?
  CGAL_NEF_TRACEN("Vertex info after swep");
  CGAL_assertion_code(SVertex_iterator svi);
  CGAL_assertion_code(
    for(svi=this->svertices_begin(); svi!=this->svertices_end(); svi++) {
      CGAL_NEF_TRACEN("vertex "<<svi->point()<<" info "<<info(svi)<<
	     " marks "<<mark(svi,0)<<" "<<mark(svi,1));
    }
  )

  if(compute_halfsphere[cs][0] && compute_halfsphere[cs][1])
    merge_halfsphere_maps(this->svertices_begin(),v,O);
  else
    set_outer_face_mark(compute_halfsphere[cs][1], mohs);
  
  CGAL_assertion_code(this->check_integrity_and_topological_planarity());
  
  CGAL_NEF_TRACEN("subdivided");
  CGAL_assertion_code(CGAL_forall_svertices(v,*this) CGAL_NEF_TRACEN(PH(v)));
}

template <typename Map>
template <typename Association>
void SM_overlayer<Map>::
subdivide(const Map* M0, const Map* M1, 
	  Association& A, 
	  bool with_trivial_segments)
{
  PI[0] = SM_const_decorator(M0); 
  PI[1] = SM_const_decorator(M1);
  Seg_list L;
  Seg_map  From;
  for (int i=0; i<2; ++i) {
    SVertex_const_iterator v;
    CGAL_forall_svertices(v,PI[i]) {
      CGAL_NEF_TRACEN(v->point() << " from " << i << " mark " << v->mark());
      if ( !PI[i].is_isolated(v) ) continue;
      L.push_back(trivial_segment(PI[i],v));
      From[--L.end()] = Seg_info(v,i);
    }
    SHalfedge_const_iterator e;
    CGAL_forall_sedges(e,PI[i]) {
      if ( e->source() == e->target() ) {
       if(with_trivial_segments) {
          v = e->source();
          L.push_back(trivial_segment(PI[i],v));
          From[--L.end()] = Seg_info(v,i);
        } else {
          Seg_pair p = two_segments(PI[i],e);
          L.push_back(p.first);
          L.push_back(p.second);
          From[--L.end()] = From[--(--L.end())] = Seg_info(e,i);
        }
      } else {
        L.push_back(segment(PI[i],e));
        From[--L.end()] = Seg_info(e,i);
      }
    }
    if ( PI[i].has_shalfloop() ) {
      SHalfloop_const_handle shl = PI[i].shalfloop();
      Seg_pair p = two_segments(PI[i],shl);
      L.push_back(p.first); 
      L.push_back(p.second.opposite());
      From[--L.end()] = From[--(--L.end())] = 
        Seg_info(shl,i);
    }
  }

  CGAL_assertion_code(typename Seg_list::iterator it);
  CGAL_assertion_code(CGAL_forall_iterators(it,L) CGAL_NEF_TRACEN("  "<<*it));

  bool compute_halfsphere[3][2];
#ifdef CGAL_NEF3_SPHERE_SWEEP_OPTIMIZATION_OFF
  int cs = -1;
  compute_halfsphere[2][0]=true;
  compute_halfsphere[2][1]=true;
#else
  int cs = check_sphere(L, compute_halfsphere);
#endif

  CGAL_NEF_TRACEN("compute_halfsphere\n  cs = " << cs);
  for(int i=0; i<6; ++i)
    CGAL_NEF_TRACEN("  " << i << " : " << compute_halfsphere[i/2][i%2]);
  Seg_list L_pos,L_neg;

  switch(cs) {
  case 1: 
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(1,0,0), Sphere_circle(0,0,-1),
			    compute_halfsphere[0][1]);
    break;
  case 0:
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(-1,0,0), Sphere_circle(0,0,-1),
			    compute_halfsphere[0][0]);
    break;
  case 3: 
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(0,1,0), Sphere_circle(1,0,0),
			    compute_halfsphere[1][1]);
    break;
  case 2:
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(0,-1,0), Sphere_circle(1,0,0), 
			    compute_halfsphere[1][0]);
    break;
  case 5: 
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(0,0,1), Sphere_circle(1,0,0),
			    compute_halfsphere[2][1]);
    break;
  case 4:
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(0,0,-1), Sphere_circle(1,0,0), 
			    compute_halfsphere[2][0]);
    break;
  case -1:
    partition_to_halfsphere(L.begin(), L.end(), L_pos, From, 
			    Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
    partition_to_halfsphere(L.begin(), L.end(), L_neg, From, 
			    Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);
    break;
  default: CGAL_assertion_msg(0, "wrong value");
  }

  cs = cs==-1 ? 2 : cs/2;

#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
  timer_sphere_sweeps.start();
#endif
  
  typedef SMO_from_sm<Self,Seg_iterator,Seg_info> SM_output;
  typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
  typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
  
  typedef CGAL::Segment_overlay_traits< 
    Seg_iterator, SM_output, PH_geometry>  PHS_traits;
  typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;
    
  typedef CGAL::Segment_overlay_traits< 
    Seg_iterator, SM_output, NH_geometry> NHS_traits;
  typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;

  typedef typename PHS_traits::INPUT Input_range;

  SVertex_handle v;
  SHalfedge_handle e;
  SM_output O(*this,PI,From); 

  if(compute_halfsphere[cs][0]) {
    PH_geometry phg(cs);

    /*   
    // the following is only needed for indexed items
    SHalfedge_const_handle se;
    SHalfloop_const_handle sl;
    for(Seg_iterator it=L_pos.begin(); it!=L_pos.end();++it) {
      CGAL_NEF_TRACEN("pos " << *it);
      if(phg.compare_xy(it->target(),it->source())<0) {
	Object_handle o = From[it]._o;
	if(CGAL::assign(se, o)) {
	  if(it->sphere_circle() == se->circle())
	    From[it] = Seg_info(se->twin(), From[it]._from);
	} else if(CGAL::assign(sl, o)) {
	  if(it->sphere_circle() == sl->circle())
	    From[it] = Seg_info(sl->twin(), From[it]._from);
	}
      }
    }
 */

    Positive_halfsphere_sweep SP(
	Input_range(L_pos.begin(),L_pos.end()),O,phg);
    SP.sweep();
    v=--this->svertices_end(); e=--this->shalfedges_end();
#ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS