sm_overlayer.h

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

template <typename Map>
template <typename Forward_iterator>
void SM_overlayer<Map>::
create_from_circles(Forward_iterator start, Forward_iterator end)
{
  CGAL_NEF_TRACEN("creating from circle iterator range");
  Seg_list L;
  Unique_hash_map<Seg_iterator,bool> From_input(false);
  for ( ; start != end; ++start ) {
    std::pair<Sphere_segment,Sphere_segment> spair =
      start->split_at_xy_plane();
    L.push_back(spair.first); L.push_back(spair.second);
  }
  Seg_iterator it;
  CGAL_forall_iterators(it,L) From_input[it]=true;
  Seg_list L_pos,L_neg;
  partition_to_halfsphere(L.begin(), L.end(), L_pos, From_input,
			  Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
  partition_to_halfsphere(L.begin(), L.end(), L_neg, From_input,
			  Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);

  typedef SMO_from_segs<Self,Seg_iterator> SM_output;
  typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
  typedef CGAL::Segment_overlay_traits< 
            Seg_iterator, SM_output, PH_geometry>  PHS_traits;
  typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;

  typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
  typedef CGAL::Segment_overlay_traits< 
            Seg_iterator, SM_output, NH_geometry> NHS_traits;
  typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;

  SVertex_iterator v;
  SHalfedge_iterator e;
  SM_output O(*this,From_input); 

  typedef typename PHS_traits::INPUT Input_range;
  Positive_halfsphere_sweep SP(
    Input_range(L_pos.begin(),L_pos.end()),O,
    PH_geometry());
  SP.sweep();
  //CGAL_NEF_TRACEN("POS SWEEP\n"<<(dump(std::cerr),""));
  v=--this->svertices_end(); e=--this->shalfedges_end();

  Negative_halfsphere_sweep SM(
    Input_range(L_neg.begin(),L_neg.end()), O,
    NH_geometry());
  SM.sweep();
  //CGAL_NEF_TRACEN("NEG SWEEP\n"<<(dump(std::cerr),""));
  ++v; ++e;
  // now two CCs of sphere graph are calculated
  // v = first vertex of CC in negative x-sphere
  // e = first edge of CC in negative x-sphere

  create_face_objects(this->shalfedges_begin(), e, this->svertices_begin(), v, O,
                      PH_geometry());
  create_face_objects(e, this->shalfedges_end(), v, this->svertices_end(), O,
                      NH_geometry());

  SHalfedge_iterator u;
  CGAL_forall_sedges(u,*this) {
    Sphere_segment s(u->source()->point(),u->target()->point());
    u->circle() = s.sphere_circle();
    u->twin()->circle() = s.sphere_circle().opposite();
  }

  merge_halfsphere_maps(this->svertices_begin(),v,O);
  this->check_integrity_and_topological_planarity();

  O.clear_temporary_vertex_info();
}

#ifdef CGAL_NEF_NEW_CHECK_SPHERE
template <typename Map>
int SM_overlayer<Map>::
check_sphere(const Seg_list& L, bool compute_halfsphere[3][2]) const {

  int chsp = 0;
  CGAL_NEF_TRACEN("chsp " << chsp);
  
  typename Seg_list::const_iterator it;
  CGAL_forall_iterators(it,L) {
    CGAL_NEF_TRACEN("source " << it->source());
    CGAL_NEF_TRACEN("target " << it->target());

    if((chsp&1)!=1)
      if(it->source().hx()>0 || it->target().hx()>0)
        chsp|=1;
    if((chsp&2)!=2)
      if(it->source().hx()<0 || it->target().hx()<0)
        chsp|=2;
    if((chsp&4)!=4)
      if(it->source().hy()>0 || it->target().hy()>0)
        chsp|=4;
    if((chsp&8)!=8)
      if(it->source().hy()<0 || it->target().hy()<0)
        chsp|=8;
    if((chsp&16)!=16)
      if(it->source().hz()>0 || it->target().hz()>0)
        chsp|=16;
    if((chsp&32)!=32)
      if(it->source().hz()<0 || it->target().hz()<0)
        chsp|=32;
    CGAL_NEF_TRACEN("chsp " << chsp);
    if(chsp == 63)
      break;
  }

  CGAL_forall_iterators(it,L) {
    CGAL_NEF_TRACEN("chsp " << chsp);
    if(chsp == 63)
      break;

//    int l = it->compare_length_to_halfcircle();
    CGAL_NEF_TRACEN("source " << it->source());
    CGAL_NEF_TRACEN("target " << it->target());
    CGAL_NEF_TRACEN("cicle  " << it->sphere_circle());
    CGAL_NEF_TRACEN("is long " << it->is_long());

    if(it->is_short()) continue;

    CGAL_NEF_TRACEN("not short");
    CGAL_NEF_TRACEN("circle " << it->sphere_circle());
    if(it->is_long()) {
      if((chsp&60)!=60 && 
         it->sphere_circle().orthogonal_vector().x()!=0) chsp|=60;
      if((chsp&51)!=51 && 
         it->sphere_circle().orthogonal_vector().y()!=0) chsp|=51;
      if((chsp&15)!=15 && 
         it->sphere_circle().orthogonal_vector().z()!=0) chsp|=15;
    } else {

      int n = 0;
      if(it->source().hx()==0) ++n;
      if(it->source().hy()==0) ++n;
      if(it->source().hz()==0) ++n;
      CGAL_assertion(n<3);
      
      CGAL_NEF_TRACEN("n " << n);
      CGAL_NEF_TRACEN("number of coordinats =0:" << n);
      if(n==0) {
        if((chsp&60)!=60 && 
           it->sphere_circle().orthogonal_vector().x()!=0) chsp|=60;
        if((chsp&51)!=51 && 
           it->sphere_circle().orthogonal_vector().y()!=0) chsp|=51;
        if((chsp&15)!=15 && 
           it->sphere_circle().orthogonal_vector().z()!=0) chsp|=15;
      } else if(n==1) {
        if((chsp&48)!=48 && it->source().z()==0) {
          Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(1,0,0));
          CGAL_NEF_TRACEN("intersection " << i);
          if(!it->has_on_after_intersection(i)) i=i.antipode();
          if(i.z() > 0) chsp|=16;
          else if(i.z() < 0) chsp|=32;
        } else if((chsp&3)!=3 && it->source().x()==0) {
          Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(0,1,0));
          CGAL_NEF_TRACEN("intersection " << i);
          if(!it->has_on_after_intersection(i)) i=i.antipode();
          if(i.x() > 0) chsp|=1;
          else if(i.x() < 0) chsp|=2;
        } else if((chsp&12)!=12) {
          Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(1,0,0));
          CGAL_NEF_TRACEN("intersection " << i);
          if(!it->has_on_after_intersection(i)) i=i.antipode();
          if(i.y() > 0) chsp|=4;
          else if(i.y() < 0) chsp|=8;
        }
      } else { // n==2
        if((chsp&60)!=60 && it->source().x()!=0) {
          Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(1,0,0));
          CGAL_NEF_TRACEN("intersection " << i);
          if(!it->has_on_after_intersection(i)) i=i.antipode();
          if((chsp&12)!=12)
            if(i.y() > 0) chsp|=4;
            else if(i.y() < 0) chsp|=8;
          if((chsp&48)!=48)
            if(i.z() > 0) chsp|=16;
            else if(i.z() < 0) chsp|=32;
	} else if((chsp&51)!=51 && it->source().y()!=0) {
          Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(0,1,0));
          CGAL_NEF_TRACEN("intersection " << i);
          if(!it->has_on_after_intersection(i)) i=i.antipode();
          if((chsp&3)!=3)
            if(i.x() > 0) chsp|=1;
            else if(i.x() < 0) chsp|=2;
	  if((chsp&48)!=48)
	    if(i.z() > 0) chsp|=16;
            else if(i.z() < 0) chsp|=32;
        } else if((chsp&15)!=15 && it->source().z()!=0) {
          Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(0,0,1));
          CGAL_NEF_TRACEN("intersection " << i);
          if(!it->has_on_after_intersection(i)) i=i.antipode();
          if((chsp&3)!=3)
            if(i.x() > 0) chsp|=1;
            else if(i.x() < 0) chsp|=2;
	  if((chsp&12)!=12)
            if(i.y() > 0) chsp|=4;
            else if(i.y() < 0) chsp|=8;
        }          
      }
    }
  }

  CGAL_NEF_TRACEN("chsp " << chsp);

  compute_halfsphere[0][0] = (chsp&1)==1;
  compute_halfsphere[0][1] = (chsp&2)==2;
  compute_halfsphere[1][0] = (chsp&4)==4;
  compute_halfsphere[1][1] = (chsp&8)==8;
  compute_halfsphere[2][0] = (chsp&16)==16;
  compute_halfsphere[2][1] = (chsp&32)==32;

  if((chsp&1)==0) { 
      compute_halfsphere[0][1]=true;
      return 0;
  }
  if((chsp&2)==0) {
      compute_halfsphere[0][0]=true;
      return 1;
  }
  if((chsp&4)==0) { 
      compute_halfsphere[1][1]=true;
      return 2;
  }
  if((chsp&8)==0) {
      compute_halfsphere[1][0]=true;
      return 3;
  }
  if((chsp&16)==0) { 
      compute_halfsphere[2][1]=true; 
      return 4;
  }
  if((chsp&32)==0) { 
      compute_halfsphere[2][0]=true;
      return 5;
  }

  return -1;
}
#else
template <typename Map>
int SM_overlayer<Map>::
check_sphere(const Seg_list& L, bool compute_halfsphere[3][2]) const {

  for(int i=0; i<6; i++)
    compute_halfsphere[i/2][i%2] = false;  

  CGAL_NEF_TRACEN("compute_halfsphere (at begin)");
  for(int i=0; i<6; ++i)
    CGAL_NEF_TRACEN("  " << i << " : " << compute_halfsphere[i/2][i%2]);

  typename Seg_list::const_iterator it;
  CGAL_forall_iterators(it,L) {
    if(!compute_halfsphere[0][0])
      if(it->source().hx()>0 || it->target().hx()>0)
	compute_halfsphere[0][0] = true;
    if(!compute_halfsphere[0][1])
      if(it->source().hx()<0 || it->target().hx()<0)
	compute_halfsphere[0][1] = true;    
    if(!compute_halfsphere[1][0])
      if(it->source().hy()>0 || it->target().hy()>0)
	compute_halfsphere[1][0] = true;
    if(!compute_halfsphere[1][1])
      if(it->source().hy()<0 || it->target().hy()<0)
	compute_halfsphere[1][1] = true;    
    if(!compute_halfsphere[2][0])
      if(it->source().hz()>0 || it->target().hz()>0)
	compute_halfsphere[2][0] = true;
    if(!compute_halfsphere[2][1])
      if(it->source().hz()<0 || it->target().hz()<0)
	compute_halfsphere[2][1] = true;    
  }

  CGAL_NEF_TRACEN("compute_halfsphere (after vertices)");
  for(int i=0; i<6; ++i)
    CGAL_NEF_TRACEN("  " << i << " : " << compute_halfsphere[i/2][i%2]);


  if(!compute_halfsphere[2][0]) {
    CGAL_forall_iterators(it,L) {
      if((it->source().hz()==0 && it->target().hz()==0) 
         || it->is_long()) { 
	compute_halfsphere[2][0] = true;
	break;
      }
    }
  }
  
  if(!compute_halfsphere[2][0]) {
    compute_halfsphere[2][1] = true;
    return 4;
  }
  
  if(!compute_halfsphere[2][1]) {
    CGAL_forall_iterators(it,L) {
      if(it->is_long() || (it->source().hz()==0 && it->target().hz()==0)) { 
	compute_halfsphere[2][1] = true;
	break;
      }
    }
  }

  if(!compute_halfsphere[2][1])
    return 5;

  if(!compute_halfsphere[0][0]) {
    CGAL_forall_iterators(it,L) {
      if((it->source().hx()==0 && it->target().hx()==0) || it->is_long()) { 
	compute_halfsphere[0][0] = true;
	break;
      }
    }
  }

  if(!compute_halfsphere[0][0]) {
    compute_halfsphere[0][1] = true;
    return 0;
  }
  
  if(!compute_halfsphere[0][1]) {
    CGAL_forall_iterators(it,L) {
      if((it->source().hx()==0 && it->target().hx()==0) || it->is_long()) { 
	compute_halfsphere[0][1] = true;
	break;
      }
    }
  }

  if(!compute_halfsphere[0][1])
    return 1;
  

  if(!compute_halfsphere[1][0]) {
    CGAL_forall_iterators(it,L) {
      if((it->source().hy()==0 && it->target().hy()==0) || it->is_long()) { 
	compute_halfsphere[1][0] = true;
	break;
      }
    }
  }
  
  if(!compute_halfsphere[1][0]) {
    compute_halfsphere[1][1] = true;
    return 2;
  }
  
  if(!compute_halfsphere[1][1]) {
    CGAL_forall_iterators(it,L) {
      if((it->source().hy()==0 && it->target().hy()==0) || it->is_long()) { 
	compute_halfsphere[1][1] = true;
	break;
      }
    }
  }

  if(!compute_halfsphere[1][1])
    return 3;
  return -1;
}
#endif

template <typename Map>
void SM_overlayer<Map>::
create(const Sphere_circle& c)
{ SHalfloop_handle l1 = this->new_shalfloop_pair();
  SHalfloop_handle l2 = l1->twin();
  l1->circle() = c; l2->circle() = c.opposite();
  SFace_handle f1 = this->new_sface();
  SFace_handle f2 = this->new_sface();
  link_as_loop(l1,f1);
  link_as_loop(l2,f2);
}

template <typename Map>
void SM_overlayer<Map>::
subdivide(const Map* M0, const Map* M1, 
	  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) {