apollonius_graph_hierarchy_2_impl.h

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

	Vertex_handle non_hidden;
	Finite_vertices_iterator vit = this->finite_vertices_begin();
	do {
	  non_hidden = Vertex_handle(vit);
	  ++vit;
	} while ( v_hidden.find(non_hidden) != v_hidden.end() );

	non_hidden->set_up( Vertex_handle() );
      }
    } else {
      typename Apollonius_graph_base::Vertex_map::iterator it;
      for (it = v_hidden.begin(); it != v_hidden.end(); it++) {
	Vertex_handle v = (*it).first;
	Vertex_handle u = v->up();
	if ( u != Vertex_handle() ) {
	  v = u;
	  u = v->up();
	  unsigned int l = 1;
	  while ( true ) {
	    hierarchy[l++]->remove(v);
	    if ( u == Vertex_handle() ) break; 
	    if(l >= ag_hierarchy_2__maxlevel) { break; }
	    v = u;
	    u = v->up();
	  }
	}
      }
    }
  }

  // now really insert at level 0
  vertex = retriangulate_conflict_region(p, l, fm, v_hidden);

  fm.clear();
  v_hidden.clear();
  // end of insertion at level 0

  // insert at other levels
  Vertex_handle previous = vertex;
  Vertex_handle first = vertex;

  if ( n_hidden != 0 ) {
    nearest_neighbor(p.point(), vnear);
  }
      
  int level = 1;
  while (level <= vertex_level ){
    vertex = hierarchy[level]->insert(p, vnear[level]);
    vertex->set_down(previous); // link with level above
    previous->set_up(vertex);
    previous = vertex;
    level++;
  }
  return first;
}

template<class Gt, class Agds, class LTag>
void 
Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::
remove(Vertex_handle v)
{
  CGAL_triangulation_precondition( v != Vertex_handle());
  CGAL_triangulation_precondition( !is_infinite(v));

  // get the hidden circles
  typename Apollonius_graph_base::Site_list wp_list;
  typename Apollonius_graph_base::Vertex::Hidden_sites_iterator wpit;

  for (wpit = v->hidden_sites_begin();
       wpit != v->hidden_sites_end(); ++wpit) {
    wp_list.push_back(*wpit);
  }
  v->clear_hidden_sites_container();

  // do the actual removal
  Vertex_handle u = v->up();
  unsigned int l = 0;
  while ( true ) {
    hierarchy[l++]->remove(v);
    if ( u == Vertex_handle() ) break; 
    if(l >= ag_hierarchy_2__maxlevel) break;
    v = u;
    u = v->up();
  }

  insert(wp_list.begin(), wp_list.end());
}


template<class Gt, class Agds, class LTag>
typename Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::Vertex_handle 
Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::
nearest_neighbor(const Point_2& p) const
{
  Vertex_handle vnear[ag_hierarchy_2__maxlevel];
  nearest_neighbor(p, vnear);
  return vnear[0];
}



template<class Gt, class Agds, class LTag>
void
Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::
swap(Apollonius_graph_hierarchy_2<Gt,Agds,LTag>& agh)
{
  Ag_base* temp;
  Ag_base::swap(agh);
  for(unsigned int i = 1; i < ag_hierarchy_2__maxlevel; ++i){
    temp = hierarchy[i];
    hierarchy[i] = agh.hierarchy[i];
    agh.hierarchy[i]= temp;
  }
}




template<class Gt, class Agds, class LTag>
void
Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::
nearest_neighbor(const Point_2& p,
		 Vertex_handle vnear[ag_hierarchy_2__maxlevel]) const
{
  Vertex_handle nearest = 0;
  unsigned int level  = ag_hierarchy_2__maxlevel;

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

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

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

template<class Gt, class Agds, class LTag>
int
Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::
random_level()
{
  unsigned int l = 0;
  while (1) {
    if ( random(ag_hierarchy_2__ratio) ) break;
    ++l;
  }
  if (l >= ag_hierarchy_2__maxlevel)
    l = ag_hierarchy_2__maxlevel -1;
  return l;
}

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::
file_input(std::istream& is)
{
  typedef std::vector<Vertex_handle>  Vertex_vector;

  // firstly, read the Apollonius graph at each level
  clear();
  for (unsigned int i = 0; i < ag_hierarchy_2__maxlevel; ++i) {
    hierarchy[i]->file_input(is);
  }

  Vertex_vector* V = new Vertex_vector[ag_hierarchy_2__maxlevel];

  // secondly, create the map of vertex indices
  for (unsigned int i = 0; i < ag_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 < ag_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;
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_hierarchy_2<Gt,Agds,LTag>::
file_output(std::ostream& os) const
{
  typedef std::map<Vertex_handle,int> Vertex_map;

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

  Vertex_map* V = new Vertex_map[ag_hierarchy_2__maxlevel];

  // create the map of vertex indices
  for (unsigned int i = 0; i < ag_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[ag_hierarchy_2__maxlevel];
  Vertex_map* V_down = new Vertex_map[ag_hierarchy_2__maxlevel];

  // create the map of up and down pointers
  for (unsigned int i = 0; i < ag_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 < ag_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;
}

CGAL_END_NAMESPACE


#endif // CGAL_APOLLONIUS_GRAPH_HIERARCHY_2_IMPL_H