apollonius_graph_2_impl.h

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

  bool result;

  if ( !is_inf_v1 && !is_inf_v2 && !is_inf_v3 && !is_inf_v4 ) {
    result = finite_edge_interior(v1, v2, v3, v4, v, b);
  } else if ( is_inf_v3 || is_inf_v4 ) {
    result = finite_edge_interior_degenerated(v1, v2, v3, v4, v, b);
  } else {
    result = infinite_edge_interior(v1, v2, v3, v4, v, b);
  }

  return result;
}


template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
edge_interior(const Face_handle& f, int i,
	      const Site_2& p, bool b) const
{
  Face_handle g = f->neighbor(i);

  bool is_inf_f = is_infinite(f);
  bool is_inf_g = is_infinite(g);

  bool result;

  if ( !is_inf_f && !is_inf_g ) {
    result = finite_edge_interior(f, i, p, b);
  } else if ( !is_inf_f || !is_inf_g ) {
    result = finite_edge_interior_degenerated(f, i, p, b);
  } else {
    //    Edge e(f, i);
    if ( !is_infinite(f, i) ) {
      result = finite_edge_interior_degenerated(f, i, p, b);
    } else {
      result = infinite_edge_interior(f, i, p, b);
    }
  }

  return result;
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Conflict_type
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_conflict_type_degenerated(const Site_2& p1,
				      const Site_2& p2,
				      const Site_2& q) const
{
  Sign i1 = incircle(p1, p2, q);
  Sign i2 = incircle(p2, p1, q);

  if ( i1 == NEGATIVE && i2 == POSITIVE ) {
    return LEFT_VERTEX;
  } else if ( i1 == POSITIVE && i2 == NEGATIVE ) {
    return RIGHT_VERTEX;
  } else if ( i1 == POSITIVE && i2 == POSITIVE ) {
    bool b = finite_edge_interior_degenerated(p1, p2, q, false);
    return (b ? INTERIOR : NO_CONFLICT);
  } else if ( i1 == NEGATIVE && i2 == NEGATIVE ) {
    bool b = finite_edge_interior_degenerated(p1, p2, q, true);
    return (b ? ENTIRE_EDGE : BOTH_VERTICES);
  } else {
    // this should never be reached; the degenerated incircle never
    // returns ZERO
    CGAL_assertion( false );
  }

  // to satisfy compiler
  return NO_CONFLICT;
}


//----------------------------------------------------------------------
// methods for disk removal
//----------------------------------------------------------------------


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_first(Vertex_handle v)
{
  Delaunay_graph::remove_first(v);
}

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_second(Vertex_handle v)
{
  Delaunay_graph::remove_second(v);
}

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_third(Vertex_handle v)
{
  if ( is_degree_2(v) ) {
    Face_handle fh( incident_faces(v) );
    int i = fh->index(v);
    flip(fh, i);
  } else if ( degree(v) == 4 ) {
    Edge_circulator ec = incident_edges(v);
    for (int i = 0; i < 4; i++) {
      Edge e = *ec;
      Edge sym = sym_edge(e);
      if ( e.first->vertex(e.second) !=	sym.first->vertex(sym.second) ) {
	flip(e);
	break;
      }
      ++ec;
    }
  }

  this->_tds.remove_dim_down( v );
}


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

  // find a neighbor of v to use for point location of hidden sites to
  // be re-inserted
  Vertex_handle vnear;
  if ( /*StoreHidden*/ true ) {
    if ( number_of_vertices() > 10 ) {
      Vertex_circulator vc_start = incident_vertices(v);
      Vertex_circulator vc = vc_start;
      do {
	if ( !is_infinite(vc) ) {
	  vnear = Vertex_handle(vc);
	  break;
	}
	++vc;
      } while ( vc != vc_start );
    }
  }

  Site_list wp_list;
  typename Vertex::Hidden_sites_iterator wpit;
  for (wpit = v->hidden_sites_begin();
       wpit != v->hidden_sites_end(); ++wpit) {
    wp_list.push_back(*wpit);
  }

  int n = number_of_vertices();
  if ( n == 1 ) {
    remove_first(v);
  } else if ( n == 2 ) {
    remove_second(v);
  } else if ( n == 3 ) {
    remove_third(v);
  } else {
    int deg = degree(v);
    if ( deg == 2 ) {
      remove_degree_2(v);
    } else if ( deg == 3 ) {
      remove_degree_3(v);
    } else {
      remove_degree_d_vertex(v);
    }
  }

  Site_less_than_comparator less_than(geom_traits());
  std::sort(wp_list.begin(), wp_list.end(), less_than);
  for (unsigned int i = 0; i < wp_list.size(); i++) {
    vnear = insert(wp_list[i], vnear);
  }
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_degree_d_vertex(Vertex_handle v)
{
  minimize_degree(v);
  int deg = degree(v);
  if ( deg == 3 ) {
    remove_degree_3(v);
    return;
  }
  if ( deg == 2 ) {
    remove_degree_2(v);
    return;
  }
  
  Apollonius_graph_2<Gt,Agds,LTag> ag_small;

  std::map<Vertex_handle,Vertex_handle> vmap;

  Vertex_circulator vc_start = incident_vertices(v);
  Vertex_circulator vc = incident_vertices(v);
  Vertex_handle vh_large, vh_small;
  do {
    vh_large = Vertex_handle(vc);
    if ( is_infinite(vh_large) ) {
      vh_small = ag_small.infinite_vertex();
      vmap[vh_small] = vh_large;
    } else { 
      vh_small = ag_small.insert(vc->site());
      if ( vh_small != Vertex_handle() ) {
	vmap[vh_small] = vh_large;
      }
    }
    ++vc;
  } while ( vc != vc_start );

  if ( ag_small.number_of_vertices() == 2 ) {
    CGAL_assertion( deg == 4 );
    Edge_circulator ec = incident_edges(v);
    for (int i = 0; i < 4; i++) {
      Edge e = *ec;
      Edge sym = sym_edge(e);
      if ( e.first->vertex(e.second) !=	sym.first->vertex(sym.second) ) {
	flip(e);
	break;
      }
      ++ec;
    }
    remove_degree_3(v);
    return;
  }


  Vertex_handle vn = ag_small.nearest_neighbor(v->site().point());

  CGAL_assertion( vn != Vertex_handle() );

  List l;
  Face_map fm;
  Vertex_map vm;
  std::vector<Vh_triple*> flipped_edges;  

  ag_small.find_conflict_region_remove(v, vn, l, fm, vm,
				       &flipped_edges);

  l.clear();
  fm.clear();
  vm.clear();

  Edge_circulator ec;

  unsigned int num_fe = flipped_edges.size();
  for (unsigned int i = 0; i < num_fe; i++) {
    Vh_triple *vhq = flipped_edges[num_fe - i - 1];

    bool found(false);
    ec = incident_edges(v);
    Edge_circulator ec_start = ec;
    do {
      Edge e = *ec;
      if ( (e.first->vertex(  cw(e.second) ) == vmap[(*vhq)[1]] &&
	    e.first->vertex(     e.second  ) == vmap[(*vhq)[2]]) ||
	   (e.first->vertex( ccw(e.second) ) == vmap[(*vhq)[1]] &&
	    tds().mirror_vertex(e.first,e.second) == vmap[(*vhq)[2]]) ) {
	flip(e);
	found = true;
	break;
      }
      ++ec;
    } while ( ec != ec_start );

    CGAL_assertion( found );
  }
  CGAL_triangulation_precondition( degree(v) == 3 );

#ifdef CGAL_T2_USE_ITERATOR_AS_HANDLE
  this->_tds.remove_degree_3( v, Face_handle() );
#else
  this->_tds.remove_degree_3( v, NULL );
#endif

  for (unsigned int i = 0; i < num_fe; i++) {
    delete flipped_edges[i];
  }
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
minimize_degree(Vertex_handle v)
{
  CGAL_precondition ( degree(v) > 3 );

  Face_circulator fc_start = incident_faces(v);
  Face_circulator fc = incident_faces(v);
  bool found(false);
  do {
    Face_handle f = Face_handle(fc);
    int i = ccw( f->index(v) );

    CGAL_assertion( f->vertex( cw(i) ) == v );

    Vertex_handle v0 = f->vertex( i );
    Vertex_handle v1 = tds().mirror_vertex( f, i );

    bool is_admissible = (v0 != v1) &&
      !is_infinite(f) && !is_infinite( f->neighbor(i) );

    if ( is_admissible && is_degenerate_edge(f, i) ) {
      Edge e = flip(f, i);
      f = e.first;

      if ( !f->has_vertex(v) ) {
	f = e.first->neighbor(e.second);
	CGAL_assertion( f->has_vertex(v) );
      }

      fc = --( incident_faces(v,f) );
      fc_start = fc;
      found = true;
    } else {
      ++fc;
      found = false;
    }
  } while ( found || fc != fc_start );
}


//----------------------------------------------------------------------
// methods for I/O
//----------------------------------------------------------------------

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::file_output(std::ostream& os) const
{
  // ouput to a file
  size_type n = this->_tds.number_of_vertices();
  size_type m = this->_tds.number_of_full_dim_faces();

  CGAL_assertion( n >= 1 );

  if( is_ascii(os) ) {
    os << n << ' ' << m << ' ' << dimension() << std::endl;
  } else {
    os << n << m << dimension();
  }

  std::map<Vertex_handle,int> V;
  std::map<Face_handle,int> F;

  // first vertex (infinite vertex) 
  int inum = 0;
  V[infinite_vertex()] = inum++;
  
  // finite vertices
  if (is_ascii(os)) os << std::endl;
  for (Finite_vertices_iterator vit = finite_vertices_begin();
       vit != finite_vertices_end(); ++vit) {
    V[vit] = inum++;
    os << vit->site();
    if ( is_ascii(os) ) { os << ' '; }
    os << vit->number_of_hidden_sites();
    typename Vertex::Hidden_sites_iterator hit;
    for (hit = vit->hidden_sites_begin(); hit != vit->hidden_sites_end();
	 ++hit) {
      if ( is_ascii(os) ) { os << ' '; }
      os << *hit;
    }
    // write non-combinatorial info of the vertex
    //    os << *vit ;
    if ( is_ascii(os) ) { os << std::endl; }
  }
  if ( is_ascii(os) ) { os << std::endl; }

  // vertices of the faces
  inum = 0;
  int dim = (dimension() == -1 ? 1 :  dimension() + 1);
  for(All_faces_iterator fit = all_faces_begin();
      fit != all_faces_end(); ++fit) {
    F[fit] = inum++;
    for(int j = 0; j < dim ; ++j) {
      os << V[ fit->vertex(j) ];
      if( is_ascii(os) ) { os << ' '; }
    }
    // write non-combinatorial info of the face
    //    os << *fit ;
    if( is_ascii(os) ) { os << std::endl; }
  }
  if( is_ascii(os) ) { os << std::endl; }
    
  // neighbor pointers of the  faces
  for( All_faces_iterator it = all_faces_begin();
       it != all_faces_end(); ++it) {
    for(int j = 0; j < dimension()+1; ++j){
      os << F[ it->neighbor(j) ];
      if( is_ascii(os) ) { os << ' '; }
    }
    if( is_ascii(os) ) { os << std::endl; }
  }

  if ( is_ascii(os) ) { os << std::endl; }
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::file_input(std::istream& is)
{
  //input from file
  size_type n, m;
  int d;
  is >> n >> m >> d;

  CGAL_assertion( n >= 1 );

  if ( n == 1 ) {
    CGAL_assertion( d == -1 );
    if ( number_of_vertices() > 0 ) { clear(); }
    return;
  }
  if ( n == 2 ) {
    CGAL_assertion( d == 0 );
    if ( number_of_vertices() > 0 ) { clear(); }
    Site_2 s;
    is >> s;
    Vertex_handle v = insert(s);
    unsigned int n_hidden;
    is >> n_hidden;
    for (unsigned int i = 0; i < n_hidden; i++) {
      is >> s;
      v->add_hidden_site(s);
    }
    return;
  }
  if ( n == 3 ) {
    CGAL_assertion( d == 1 );
    if ( number_of_vertices() > 0 ) { clear(); }
    for (int j = 0; j < 2; j++) {
      Site_2 s;
      is >> s;
      Vertex_handle v = insert(s);
      unsigned int n_hidden;
      is >> n_hidden;
      for (unsigned int i = 0; i < n_hidden; i++) {
	is >> s;
	v->add_hidden_site(s);
      }
    }
    return;
  }

  if (this->_tds.number_of_vertices() != 0) { this->_tds.clear(); }

  this->_tds.set_dimension(d);

  std::vector<Vertex_handle> V(n);
  std::vector<Face_handle> F(m);

  size_type i = 0;

  // first vertex (infinite vertex)
  V[0] = create_vertex();
  this->set_infinite_vertex(V[0]);
  i++;


  // read vertices
  for (; i < n; ++i) {
    V[i] = create_vertex();
    Site_2 s;
    is >> s;
    V[i]->set_site(s);
    unsigned int n_hidden;
    is >> n_hidden;
    for (unsigned int j = 0; j < n_hidden; j++) {
      is >> s;
      V[i]->add_hidden_site(s);
    }
    // read non-combinatorial info of the vertex
    //    is >> *(V[i]);
  }
  
  // Creation of the faces
  int index;
  int dim = (dimension() == -1 ? 1 : dimension() + 1);

  for (i = 0; i < m; ++i) {
    F[i] = this->_tds.create_face();
    for (int j = 0; j < dim ; ++j){
      is >> index;
      F[i]->set_vertex(j, V[index]);
      // The face pointer of vertices is set too often,
      // but otherwise we had to use a further map
      V[index]->set_face(F[i]);
    }
    // read in non-combinatorial info of the face
    //      is >> *(F[i]) ;
  }

  // Setting the neighbor pointers 
  for (i = 0; i < m; ++i) {
    for (int j = 0; j < dimension()+1; ++j){
      is >> index;
      F[i]->set_neighbor(j, F[index]);
    }
  }
}


CGAL_END_NAMESPACE


#endif // CGAL_APOLLONIUS_GRAPH_2_IMPL_H