apollonius_graph_2_impl.h

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

    Site_list wp_list;
    typename Vertex_map::iterator vmit;
    for (vmit = vm.begin(); vmit != vm.end(); ++vmit) {
      Vertex_handle vhidden = (*vmit).first;

      wp_list.push_back(vhidden->site());
      typename Vertex::Hidden_sites_iterator it;
      for (it = vhidden->hidden_sites_begin();
	   it != vhidden->hidden_sites_end(); ++it) {
	wp_list.push_back(*it);
      }	
      vhidden->clear_hidden_sites_container();
    }

    // 2. find which vertex remains non-hidden and copy its hidden
    // sites to a local container
    Vertex_handle non_hidden;
    Finite_vertices_iterator vit = finite_vertices_begin();
    do {
      non_hidden = Vertex_handle(vit);
      ++vit;
    } while ( vm.find(non_hidden) != vm.end() );

    Site_2 p1 = non_hidden->site();
    Site_list wp_list1;
    typename Vertex::Hidden_sites_iterator it;
    for (it = non_hidden->hidden_sites_begin();
	 it != non_hidden->hidden_sites_end(); ++it) {
      wp_list1.push_back(*it);
    }	
    non_hidden->clear_hidden_sites_container();

    // 3. clear the current Apollonius graph
    clear();

    // 4. insert the two non-hidden sites and copy the corresponding
    // hidden sites
    Vertex_handle v1 = insert_first(p1);
    for (Site_list_iterator it = wp_list1.begin();
	 it != wp_list1.end(); ++it) {
      v1->add_hidden_site(*it);
    }

    Vertex_handle v = insert_second(p);
    for (Site_list_iterator it = wp_list.begin();
	 it != wp_list.end(); ++it) {
      v->add_hidden_site(*it);
    }

    return v;
  }

  Vertex_handle v = this->_tds.create_vertex();
  v->set_site(p);

  // 1. move all the hidden sites to the new one
  typename Vertex_map::iterator vmit;
  for (vmit = vm.begin(); vmit != vm.end(); ++vmit) {
    Vertex_handle vhidden = (*vmit).first;
    move_hidden_sites(vhidden, v);
    v->add_hidden_site(vhidden->site());
  }

  CGAL_precondition( number_of_vertices() - vm.size() >= 2 );

  // 2. add the bogus vetrices
  Vertex_list dummy_vertices = add_bogus_vertices(l);

  // 3. repair the face pointers...
  Edge e_start = l.front();
  Edge eit = e_start;
  do {
    Edge esym = sym_edge(eit);
    Face_handle f = eit.first;
    int k = eit.second;
    CGAL_assertion( !l.is_in_list(esym) );
    CGAL_assertion( fm.find(f) == fm.end() );
    f->vertex(ccw(k))->set_face(f);
    f->vertex( cw(k))->set_face(f);
    eit = l.next(eit);
  } while ( eit != e_start );

  //  std::vector<Face*> vf = get_faces_for_recycling(fm, l.size());
  std::list<Face*> vf;

  // 4. copy the edge list to a vector of edges and clear the in place 
  //    list
  typedef typename Agds::Edge Agds_edge;
  std::vector<Agds_edge> ve;

  Edge efront = l.front();
  Edge e = efront;
  do {
    ve.push_back(Agds_edge(e.first, e.second));
    e = l.next(e);
  } while ( e != efront );

  l.clear();

  // 5. remove the hidden vertices
  remove_hidden_vertices(vm);

  // 6. retriangulate the hole
  //  _tds.star_hole( v, ve.begin(), ve.end(), vf.begin(), vf.end());
  this->_tds.star_hole(v, ve.begin(), ve.end());

  // 7. remove the bogus vertices
  remove_bogus_vertices(dummy_vertices);

  // 8. remove the unused faces
  typename Face_map::iterator it;
  for (it = fm.begin(); it != fm.end(); ++it) {
    Face_handle fh = (*it).first;
    this->_tds.delete_face( fh );
  }

  CGAL_assertion( number_of_vertices() + vmsize == num_vert + 1 );

  // 9. DONE!!!!
  return v;
}



//--------------------------------------------------------------------
// point location
//--------------------------------------------------------------------
template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
nearest_neighbor(const Point_2& p) const
{
  return nearest_neighbor(p, Vertex_handle());
}


template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
nearest_neighbor(const Point_2& p,
		 Vertex_handle start_vertex) const
{
  if ( number_of_vertices() == 0 ) {
    return Vertex_handle();
  }

  if ( start_vertex == Vertex_handle() ) {
    start_vertex = finite_vertex();
  }

  //  if ( start_vertex == Vertex_handle() ) { return start_vertex; }

  Vertex_handle vclosest;
  Vertex_handle v = start_vertex;

  if ( number_of_vertices() < 3 ) {
    vclosest = v;
    Finite_vertices_iterator vit = finite_vertices_begin();
    for (; vit != finite_vertices_end(); ++vit) {
      Vertex_handle v1(vit);
      if ( v1 != vclosest /*&& !is_infinite(v1)*/ ) {
	Site_2 p1 = vclosest->site();
	Site_2 p2 = v1->site();
	if ( side_of_bisector(p1, p2, p) == ON_NEGATIVE_SIDE ) {
	  vclosest = v1;
	}
      }
    }
    return vclosest;
  }

  do {
    vclosest = v;
    Site_2 p1 = v->site();
    Vertex_circulator vc_start = incident_vertices(v);
    Vertex_circulator vc = vc_start;
    do {
      if ( !is_infinite(vc) ) {
	Vertex_handle v1(vc);
	Site_2 p2 = v1->site();
	if ( side_of_bisector(p1, p2, p) == ON_NEGATIVE_SIDE ) {
	  v = v1;
	  break;
	}
      }
      ++vc;
    } while ( vc != vc_start );
  } while ( vclosest != v );

  return vclosest;
}


//----------------------------------------------------------------------
// methods for the predicates
//----------------------------------------------------------------------

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
is_hidden(const Site_2 &p, const Site_2 &q) const
{
  return geom_traits().is_hidden_2_object()(p, q);
}

template<class Gt, class Agds, class LTag>
Oriented_side
Apollonius_graph_2<Gt,Agds,LTag>::
side_of_bisector(const Site_2 &p1,
		 const Site_2 &p2,
		 const Point_2 &p) const
{
  return geom_traits().oriented_side_of_bisector_2_object()(p1, p2, p);
}


template<class Gt, class Agds, class LTag>
Sign
Apollonius_graph_2<Gt,Agds,LTag>::
incircle(const Site_2 &p1, const Site_2 &p2,
	 const Site_2 &p3, const Site_2 &q) const
{
  return geom_traits().vertex_conflict_2_object()(p1, p2, p3, q);
}

template<class Gt, class Agds, class LTag>
Sign
Apollonius_graph_2<Gt,Agds,LTag>::
incircle(const Site_2 &p1, const Site_2 &p2,
	 const Site_2 &q) const
{
  return
    geom_traits().vertex_conflict_2_object()(p1, p2, q);
}


template<class Gt, class Agds, class LTag>
Sign
Apollonius_graph_2<Gt,Agds,LTag>::
incircle(const Face_handle& f, const Site_2& q) const
{
  if ( !is_infinite(f) ) {
    return incircle(f->vertex(0)->site(),
		    f->vertex(1)->site(),
		    f->vertex(2)->site(), q);
  }

  int inf_i(-1); // to avoid compiler warning
  for (int i = 0; i < 3; i++) {
    if ( is_infinite(f->vertex(i)) ) {
      inf_i = i;
      break;
    }
  }
  return incircle( f->vertex( ccw(inf_i) )->site(),
		   f->vertex(  cw(inf_i) )->site(), q );
}


template<class Gt, class Agds, class LTag>
Sign
Apollonius_graph_2<Gt,Agds,LTag>::
incircle(const Vertex_handle& v0, const Vertex_handle& v1,
	 const Vertex_handle& v) const
{
  CGAL_precondition( !is_infinite(v0) && !is_infinite(v1)
		     && !is_infinite(v) );

  return incircle( v0->site(), v1->site(), v->site());
}

template<class Gt, class Agds, class LTag>
Sign
Apollonius_graph_2<Gt,Agds,LTag>::
incircle(const Vertex_handle& v0, const Vertex_handle& v1,
	 const Vertex_handle& v2, const Vertex_handle& v) const
{
  CGAL_precondition( !is_infinite(v) );

  if ( !is_infinite(v0) && !is_infinite(v1) &&
       !is_infinite(v2) ) {
    return incircle(v0->site(), v1->site(),
		    v2->site(), v->site());
  }

  if ( is_infinite(v0) ) {
    CGAL_precondition( !is_infinite(v1) && !is_infinite(v2) );
    return incircle( v1->site(), v2->site(), v->site());
  }
  if ( is_infinite(v1) ) {
    CGAL_precondition( !is_infinite(v0) && !is_infinite(v2) );
    return incircle( v2->site(), v0->site(), v->site());
  }

  CGAL_assertion( is_infinite(v2) );
  CGAL_precondition( !is_infinite(v0) && !is_infinite(v1) );
  return incircle( v0->site(), v1->site(), v->site());
}


template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_interior(const Site_2& p1,
		     const Site_2& p2,
		     const Site_2& p3,
		     const Site_2& p4,
		     const Site_2& q, bool b) const
{
  if ( is_hidden(q, p1) ) { return true; }
  if ( is_hidden(q, p2) ) { return true; }
  return
    geom_traits().finite_edge_interior_conflict_2_object()(p1,p2,p3,p4,q,b);
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_interior(const Face_handle& f, int i,
		     const Site_2& p, bool b) const
{
  CGAL_precondition( !is_infinite(f) &&
		     !is_infinite(f->neighbor(i)) );
  return finite_edge_interior( f->vertex( ccw(i) )->site(),
			       f->vertex(  cw(i) )->site(),
			       f->vertex(     i  )->site(),
			       tds().mirror_vertex(f, i)->site(), p, b);
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_interior(const Vertex_handle& v1,
		     const Vertex_handle& v2,
		     const Vertex_handle& v3,
		     const Vertex_handle& v4,
		     const Vertex_handle& v, bool b) const
{
  CGAL_precondition( !is_infinite(v1) && !is_infinite(v2) &&
		     !is_infinite(v3) && !is_infinite(v4) &&
		     !is_infinite(v) );
  return finite_edge_interior( v1->site(), v2->site(),
			       v3->site(), v4->site(),
			       v->site(), b);
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_interior_degenerated(const Site_2& p1,
				 const Site_2& p2,
				 const Site_2& p3,
				 const Site_2& q,
				 bool b) const
{
  if ( is_hidden(q, p1) ) { return true; }
  if ( is_hidden(q, p2) ) { return true; }
  return
    geom_traits().finite_edge_interior_conflict_2_object()(p1,p2,p3,q,b);
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_interior_degenerated(const Site_2& p1,
				 const Site_2& p2,
				 const Site_2& q,
				 bool b) const
{
  if ( is_hidden(q, p1) ) { return true; }
  if ( is_hidden(q, p2) ) { return true; }
  return
    geom_traits().finite_edge_interior_conflict_2_object()(p1, p2, q, b);
}


template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_interior_degenerated(const Face_handle& f, int i,
				 const Site_2& p, bool b) const
{
  if ( !is_infinite( tds().mirror_vertex(f, i) ) ) {
    CGAL_precondition( is_infinite(f->vertex(i)) );

    Face_handle g = f->neighbor(i);
    int j = tds().mirror_index(f, i);

    return finite_edge_interior_degenerated(g, j, p, b);
  }

  CGAL_precondition( is_infinite( tds().mirror_vertex(f, i) ) );

  Site_2 p1 = f->vertex( ccw(i) )->site();
  Site_2 p2 = f->vertex(  cw(i) )->site();

  if ( is_infinite(f->vertex(i)) ) {
    return finite_edge_interior_degenerated(p1, p2, p, b);
  }

  Site_2 p3 = f->vertex(i)->site();
  return finite_edge_interior_degenerated(p1, p2, p3, p, b);
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
finite_edge_interior_degenerated(const Vertex_handle& v1,
				 const Vertex_handle& v2,
				 const Vertex_handle& v3,
				 const Vertex_handle& v4,
				 const Vertex_handle& v, bool b) const
{
  CGAL_precondition( !is_infinite(v1) && !is_infinite(v2) && 
		     !is_infinite(v) );
  if ( !is_infinite( v4 ) ) {
    CGAL_precondition( is_infinite(v3) );

    return
      finite_edge_interior_degenerated(v2, v1, v4, v3, v, b);
  }

  CGAL_precondition( is_infinite( v4 ) );

  Site_2 p1 = v1->site();
  Site_2 p2 = v2->site();
  Site_2 p = v->site();

  if ( is_infinite(v3) ) {
    return finite_edge_interior_degenerated(p1, p2, p, b);
  }

  Site_2 p3 = v3->site();
  return finite_edge_interior_degenerated(p1, p2, p3, p, b);
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
infinite_edge_interior(const Site_2& p2,
		       const Site_2& p3,
		       const Site_2& p4,
		       const Site_2& q,
		       bool b) const
{
  if ( is_hidden(q, p2) ) { return true; }
  return
    geom_traits().infinite_edge_interior_conflict_2_object()(p2,p3,p4,q,b);
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
infinite_edge_interior(const Face_handle& f, int i,
		       const Site_2& p, bool b) const
{
  if ( !is_infinite( f->vertex(ccw(i)) ) ) {
    CGAL_precondition( is_infinite( f->vertex(cw(i)) ) );
    Face_handle g = f->neighbor(i);
    int j = tds().mirror_index(f, i);

    return infinite_edge_interior(g, j, p, b);
  }

  CGAL_precondition( is_infinite( f->vertex(ccw(i)) ) );

  Site_2 p2 = f->vertex(  cw(i) )->site();
  Site_2 p3 = f->vertex(     i  )->site();
  Site_2 p4 = tds().mirror_vertex(f, i)->site();

  return infinite_edge_interior(p2, p3, p4, p, b);
}


template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
infinite_edge_interior(const Vertex_handle& v1,
		       const Vertex_handle& v2,
		       const Vertex_handle& v3,
		       const Vertex_handle& v4,
		       const Vertex_handle& v, bool b) const
{
  CGAL_precondition( !is_infinite(v3) && !is_infinite(v4) && 
		     !is_infinite(v) );

  if ( !is_infinite( v1 ) ) {
    CGAL_precondition( is_infinite( v2 ) );

    return infinite_edge_interior(v2, v1, v4, v3, v, b);
  }

  CGAL_precondition( is_infinite( v1 ) );

  Site_2 p2 = v2->site();
  Site_2 p3 = v3->site();
  Site_2 p4 = v4->site();
  Site_2 p = v->site();

  return infinite_edge_interior(p2, p3, p4, p, b);
}




template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
edge_interior(const Vertex_handle& v1,
	      const Vertex_handle& v2,
	      const Vertex_handle& v3,
	      const Vertex_handle& v4,
	      const Vertex_handle& v, bool b) const
{
  CGAL_precondition( !is_infinite(v) );

  bool is_inf_v1 = is_infinite(v1);
  bool is_inf_v2 = is_infinite(v2);
  bool is_inf_v3 = is_infinite(v3);
  bool is_inf_v4 = is_infinite(v4);