segment_delaunay_graph_hierarchy_2_impl.h

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

  }

  // remove at level 0
  Vertex_handle u = v->up();
  bool success = hierarchy[0]->remove_base(v);
  if ( !success ) { return false; }

  // remove at higher levels
  unsigned int l = 1;
  Vertex_handle vv = u;
  while ( u != Vertex_handle() ) {
    if ( l >= sdg_hierarchy_2__maxlevel) { break; }
    vv = u;
    u = vv->up();
    success = hierarchy[l++]->remove_base(vv);
    CGAL_assertion( success );
  }

  // unregister the input site
  if ( is_point ) {
    this->unregister_input_site( h1 );
  } else {
    this->unregister_input_site( h1, h2 );
  }

  return true;
}

//===========================================================================
//===========================================================================

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//  nearest neighbor location
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
template<class Gt, class ST, class STag, class DS, class LTag>
typename
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::Vertex_handle 
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
nearest_neighbor(const Point_2& p, bool force_point) const
{
  Vertex_handle vnear[sdg_hierarchy_2__maxlevel];
  //  nearest_neighbor(Site_2(p), vnear, force_point);

  Site_2 t = Site_2::construct_site_2(p);

  nearest_neighbor(t, vnear, force_point);
  return vnear[0];
}

template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
nearest_neighbor(const Site_2& t,
		 Vertex_handle vnear[sdg_hierarchy_2__maxlevel],
		 bool /* force_point */) const
{
  CGAL_precondition( t.is_point() );

  Vertex_handle nearest;
  int level  = sdg_hierarchy_2__maxlevel;

  // find the highest level with enough vertices
  while ( hierarchy[--level]->number_of_vertices() 
	  < sdg_hierarchy_2__minsize ) {
    if ( !level ) break;  // do not go below 0
  }
  for (unsigned int i = level + 1; i < sdg_hierarchy_2__maxlevel; i++) {
    vnear[i] = Vertex_handle();
  }

  while ( level > 0 ) {
    vnear[level] = nearest =
      hierarchy[level]->nearest_neighbor(t, nearest);  

    CGAL_assertion( !hierarchy[level]->is_infinite(vnear[level]) );
    CGAL_assertion( vnear[level] != Vertex_handle() );
    // go at the same vertex on level below
    nearest = nearest->down();
    --level;
  }
  vnear[0] = hierarchy[0]->nearest_neighbor(t, nearest);
  // at level 0
}



//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//  miscellaneous methods
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::   
copy(const Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag> &sdg)
{
#ifndef CGAL_NO_ASSERTIONS
  for (unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i) {
    CGAL_assertion( hierarchy[i]->pc_.size() == 0 );
    CGAL_assertion( hierarchy[i]->isc_.size() == 0 );

    CGAL_assertion( sdg.hierarchy[i]->pc_.size() == 0 );
    CGAL_assertion( sdg.hierarchy[i]->isc_.size() == 0 );
  }
#endif

  // first copy the point container and input point container
  this->pc_ = sdg.pc_;

  // first create a map between the old point handles and the new ones
  Handle_map hm;

  Point_handle it_other = sdg.hierarchy[0]->pc_.begin();
  Point_handle it_this = hierarchy[0]->pc_.begin();
  for (; it_other != sdg.hierarchy[0]->pc_.end(); ++it_other, ++it_this) {
    hm.insert( Point_handle_pair(it_other, it_this) );
  }

  {
    for(unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
      hierarchy[i]->copy(*sdg.hierarchy[i], hm);
    }
  }

  //up and down have been copied in straightforward way
  // compute a map at lower level
  std::map< Vertex_handle, Vertex_handle > V;
  {
    for(Finite_vertices_iterator it = hierarchy[0]->finite_vertices_begin(); 
	it != hierarchy[0]->finite_vertices_end(); ++it) {
      if ( it->up() != Vertex_handle() ) {
	V[ it->up()->down() ] = it;
      }
    }
  }
  {
    for(unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i) {
      for(Finite_vertices_iterator it = hierarchy[i]->finite_vertices_begin(); 
	  it != hierarchy[i]->finite_vertices_end(); ++it) {
	// down pointer goes in original instead in copied triangulation
	it->set_down(V[it->down()]);
	// make reverse link
	it->down()->set_up( it );
	// make map for next level
	if ( it->up() != Vertex_handle() ) {
	  V[ it->up()->down() ] = it;
	}
      }
    }
  }

  // the point container and the input sites container are copied by
  // the operator= of the one-level classes
  //  hierarchy[0]->pc_ = sdg.hierarchy[0]->pc_;
  //  hierarchy[0]->isc_ = sdg.hierarchy[0]->isc_;
}

template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>:: 
clear()
{
  for(unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
    hierarchy[i]->clear();
  }
}

template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>:: 
swap(Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>& other)
{
  Base* temp;
  Base::swap(other);
  for(unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i) {
    temp = hierarchy[i];
    hierarchy[i] = other.hierarchy[i];
    other.hierarchy[i]= temp;
  }
}

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//  validity check
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
template<class Gt, class ST, class STag, class DS, class LTag>
bool
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>:: 
is_valid(bool verbose, int level) const
{
  bool result(true);

  //verify correctness of triangulation at all levels
  for(unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
    if ( verbose ) {
      std::cerr << "Level " << i << ": " << std::flush;
    }
    result = result && hierarchy[i]->is_valid(verbose, level);
    if ( verbose ) {
      std::cerr << std::endl;
    }
  }
  //verify that lower level has no down pointers
  for( Finite_vertices_iterator it = hierarchy[0]->finite_vertices_begin(); 
       it != hierarchy[0]->finite_vertices_end(); ++it) {
    result = result && ( it->down() == Vertex_handle() );
  }

  //verify that other levels has down pointer and reciprocal link is fine
  for(unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i) {
    for( Finite_vertices_iterator it = hierarchy[i]->finite_vertices_begin(); 
	 it != hierarchy[i]->finite_vertices_end(); ++it) {
      Vertex_handle vit(it);
      result = result && ( it->down()->up() == vit );
    }
  }
  return result;
}


//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//  local helper methods
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
print_error_message() const
{
  std::cerr << std::endl;
  std::cerr << "WARNING:" << std::endl;
  std::cerr << "A segment-segment intersection was found."
	    << std::endl;
  std::cerr << "The Segment_Delaunay_graph_hierarchy_2 class is not"
	    << " configured to handle this situation." << std::endl;
  std::cerr << "Please look at the documentation on how to handle"
	    << " this behavior." << std::endl;
  std::cerr << std::endl;
}

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//  file I/O
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
file_output(std::ostream& os) const
{
  typedef std::map<Vertex_handle,int>        Vertex_map;
  typedef typename Base::const_Point_handle  const_Point_handle;

  // compute the point handle mapper
  typename Base::Point_handle_mapper P;
  size_type inum = 0;
  for (const_Point_handle ph = this->pc_.begin(); ph != this->pc_.end(); ++ph) {
    P[ph] = inum++;
  }

  // write each level of the hierarchy
  hierarchy[0]->file_output(os, P, true);
  if ( is_ascii(os) ) { os << std::endl << std::endl; }
  for (unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i) {
    hierarchy[i]->file_output(os, P, false);
    if ( is_ascii(os) ) { os << std::endl << std::endl; }
  }

  Vertex_map* V = new Vertex_map[sdg_hierarchy_2__maxlevel];

  // create the map of vertex indices
  for (unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
    int inum = 0;
    for (Finite_vertices_iterator vit = hierarchy[i]->finite_vertices_begin();
	 vit != hierarchy[i]->finite_vertices_end(); ++vit) {
      V[i][vit] = inum++;
    }
  }

  Vertex_map* V_up   = new Vertex_map[sdg_hierarchy_2__maxlevel];
  Vertex_map* V_down = new Vertex_map[sdg_hierarchy_2__maxlevel];

  // create the map of up and down pointers
  for (unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
    for (Finite_vertices_iterator vit = hierarchy[i]->finite_vertices_begin();
	 vit != hierarchy[i]->finite_vertices_end(); ++vit) {
      if ( vit->up() != Vertex_handle() ) {
	V_up[i][vit] = V[i+1][vit->up()];
      } else {
	V_up[i][vit] = -1;
      }

      if ( vit->down() != Vertex_handle() ) {
	V_down[i][vit] = V[i-1][vit->down()];
      } else {
	V_down[i][vit] = -1;
      }
    }
  }

  // write up and down pointer info
  if ( is_ascii(os) ) { os << std::endl << std::endl; }
  for (unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
    os << i;
    if ( is_ascii(os) ) { os << " "; }
    os << hierarchy[i]->number_of_vertices();
    if ( is_ascii(os) ) { os << std::endl; }
    for (Finite_vertices_iterator vit = hierarchy[i]->finite_vertices_begin();
	 vit != hierarchy[i]->finite_vertices_end(); ++vit) {
      os << V[i][vit];
      if ( is_ascii(os) ) { os << " "; }
      os << V_down[i][vit];
      if ( is_ascii(os) ) { os << " "; }
      os << V_up[i][vit];
      if ( is_ascii(os) ) { os << std::endl; }
    }
    if ( is_ascii(os) ) { os << std::endl << std::endl; }
  }

  delete[] V;
  delete[] V_up;
  delete[] V_down;
}

template<class Gt, class ST, class STag, class DS, class LTag>
void
Segment_Delaunay_graph_hierarchy_2<Gt,ST,STag,DS,LTag>::
file_input(std::istream& is)
{
  typedef std::vector<Vertex_handle>  Vertex_vector;

  // firstly, read the segment Delaunay graph at each level
  clear();
  typename Base::Point_handle_vector P;
  hierarchy[0]->file_input(is, true, P);
  for (unsigned int i = 1; i < sdg_hierarchy_2__maxlevel; ++i) {
    hierarchy[i]->file_input(is, false, P);
  }

  Vertex_vector* V = new Vertex_vector[sdg_hierarchy_2__maxlevel];

  // secondly, create the map of vertex indices
  for (unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
    V[i].resize(hierarchy[i]->number_of_vertices());
    int j = 0;
    for (Finite_vertices_iterator vit = hierarchy[i]->finite_vertices_begin();
	 vit != hierarchy[i]->finite_vertices_end(); ++vit, ++j) {
      V[i][j] = vit;
    }
  }

  // read the correspondences between up and down pointers and set
  // them appropriately
  for (unsigned int i = 0; i < sdg_hierarchy_2__maxlevel; ++i) {
    unsigned int level;
    int vnum;
    is >> level >> vnum;
    for (int k = 0; k < vnum; k++) {
      int ithis, iup, idown;
      is >> ithis >> idown >> iup;
      if ( idown != -1 ) { V[i][ithis]->set_down(V[i-1][idown]); }
      if ( iup != -1 )   { V[i][ithis]->set_up(V[i+1][iup]); }
    }
  }

  delete[] V;
}


//--------------------------------------------------------------------


CGAL_END_NAMESPACE


// EOF