apollonius_graph_2_impl.h

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

  if ( ct == NO_CONFLICT ) {
    Oriented_side os =
      side_of_bisector(v1->site(), v2->site(), p.point());

    CGAL_assertion( os != ON_ORIENTED_BOUNDARY );
    Vertex_handle vv = ( os == ON_NEGATIVE_SIDE ) ? v1 : v2;

    Face_circulator fc = incident_faces(v);
    while ( true ) {
      Face_handle f(fc);
      int k = f->index(v);
      Vertex_handle vh = f->vertex(ccw(k));
      if ( vh == vv ) {
	flip(f, cw(k));
	break;
      }
      ++fc;
    }
  } else if ( ct == INTERIOR ) {
    Edge_circulator ec = incident_edges(v);

    while ( true ) {
      if ( is_infinite(ec) ) {
	flip(*ec);
	break;
      }
      ec++;
    }
  } else if ( ct == ENTIRE_EDGE ) {
    Face_circulator fc = incident_faces(v);

    while ( true ) {
      Face_handle f(fc);
      if ( !is_infinite(f) ) {
	flip(f, f->index(v));
	break;
      }
      ++fc;
    }
  } else if ( ct == BOTH_VERTICES ) {


    Conflict_type ct1 =
      finite_edge_conflict_type_degenerated(v1->site(), p, v2->site());

    Edge_circulator ec;
    ec = ( ct1 == INTERIOR ) ? incident_edges(v2) : incident_edges(v1);
    while ( true ) {
      if ( is_infinite(ec) ) {
	flip(*ec);
	break;
      }
      ec++;
    }
  } else {
    CGAL_assertion( ct == RIGHT_VERTEX || ct == LEFT_VERTEX );
    // do nothing here
  }

  //  CGAL_triangulation_assertion( is_valid() );

  return v;
}


template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
insert(const Site_2& p, Vertex_handle vnear)
{
  if ( number_of_vertices() == 0 ) {
    return insert_first(p);
  }
  if ( number_of_vertices() == 1 ) {
    return insert_second(p);
  }
  if ( number_of_vertices() == 2 ) {
    return insert_third(p);
  }

  // first find the nearest neighbor
  Vertex_handle vnearest = nearest_neighbor(p.point(), vnear);

  CGAL_assertion( vnearest != Vertex_handle() );


  // check if it is hidden
  Site_2 wp_nearest = vnearest->site();
  if ( is_hidden(wp_nearest, p) ) {
    vnearest->add_hidden_site(p);
    return Vertex_handle();
  }

  // find the first conflict

  // first look for conflict with vertex
  Face_circulator fc_start = incident_faces(vnearest);
  Face_circulator fc = fc_start;
  Face_handle start_f;
  Sign s;
  do {
    Face_handle f(fc);
    s = incircle(f, p);

    if ( s == NEGATIVE ) {
      start_f = f;
      break;
    }
    ++fc;
  } while ( fc != fc_start );

  // we are not in conflict with an Apollonius vertex, so we have to
  // be in conflict with the interior of an Apollonius edge
  if ( s != NEGATIVE ) {
    Edge_circulator ec_start = incident_edges(vnearest);
    Edge_circulator ec = ec_start;

    bool interior_in_conflict(false);
    Edge e;
    do {
      e = *ec;
      interior_in_conflict = edge_interior(e, p, false);

      if ( interior_in_conflict ) { break; }
      ++ec;
    } while ( ec != ec_start );

    CGAL_assertion( interior_in_conflict );

    return insert_degree_2(e, p);
  }


  // we are in conflict with an Apollonius vertex; start from that and 
  // find the entire conflict region and then repair the diagram
  List l;
  Face_map fm;
  Vertex_map vm;

  // MK:: NEED TO WRITE A FUNCTION CALLED find_conflict_region WHICH
  // IS GIVEN A STARTING FACE, A LIST, A FACE MAP, A VERTEX MAP AND A
  // LIST OF FLIPPED EDGES AND WHAT IS DOES IS INITIALIZE THE CONFLICT 
  // REGION AND EXPANDS THE CONFLICT REGION.
  initialize_conflict_region(start_f, l);
  expand_conflict_region(start_f, p, l, fm, vm, NULL);

  //  retriangulate_conflict_region(v, l, fm, vm);
  Vertex_handle v = retriangulate_conflict_region(p, l, fm, vm);

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


  return v;
}


//--------------------------------------------------------------------
// find conflict region
//--------------------------------------------------------------------
template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
find_conflict_region_remove(const Vertex_handle& v,
			    const Vertex_handle& vnearest,
			    List& l, Face_map& fm,
			    Vertex_map& vm,
			    std::vector<Vh_triple*>* fe)
{
  Site_2 p = v->site();
  // check if it is hidden
  Site_2 wp_nearest = vnearest->site();
  if ( is_hidden(wp_nearest, p) ) {
    vnearest->add_hidden_site(p);
    return;
  }

  CGAL_precondition( vnearest != Vertex_handle() );


  // find the first conflict

  // first look for conflict with vertex
  Face_circulator fc_start = incident_faces(vnearest);
  Face_circulator fc = fc_start;
  Face_handle start_f;
  Sign s;
  do {
    Face_handle f(fc);
    s = incircle(f, p);

    if ( s == NEGATIVE ) {
      start_f = f;
      break;
    }
    ++fc;
  } while ( fc != fc_start );

  CGAL_assertion( s == NEGATIVE );

  // we are not in conflict with an Apollonius vertex, so we have to
  // be in conflict with the interior of an Apollonius edge
  if ( s != NEGATIVE ) {
    Edge_circulator ec_start = incident_edges(vnearest);
    Edge_circulator ec = ec_start;

    bool interior_in_conflict(false);
    Edge e;
    do {
      e = *ec;
      interior_in_conflict = edge_interior(e, p, false);

      if ( interior_in_conflict ) { break; }
      ++ec;
    } while ( ec != ec_start );

    CGAL_assertion( interior_in_conflict );

    l.push_back(e);
    l.push_back(sym_edge(e));
    return;
  }

  initialize_conflict_region(start_f, l);
  expand_conflict_region(start_f, v->site(), l, fm, vm, fe);
}

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
initialize_conflict_region(const Face_handle& f, List& l) const
{
  l.clear();
  for (int i = 0; i < 3; i++) {
    l.push_back(sym_edge(f, i));
  }
}

template<class Gt, class Agds, class LTag>
bool
Apollonius_graph_2<Gt,Agds,LTag>::
check_edge_for_hidden_sites(const Face_handle& f, int i,
			    const Site_2& p, Vertex_map& vm) const
{
  bool found(false);

  Vertex_handle v1 = f->vertex(ccw(i));
  if ( vm.find(v1) == vm.end() ) {
    if ( !is_infinite(v1) && is_hidden(p, v1->site()) ) {
      vm[v1] = true;
      found = true;
    }
  } else {
    found = true;
  }

  Vertex_handle v2 = f->vertex(cw(i));
  if ( vm.find(v2) == vm.end() ) {
    if ( !is_infinite(v2) && is_hidden(p, v2->site()) ) {
      vm[v2] = true;
      found = true;
    }
  } else {
    found = true;
  }

  return found;
}

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
expand_conflict_region(const Face_handle& f, const Site_2& p,
		       List& l, Face_map& fm, Vertex_map& vm,
		       std::vector<Vh_triple*>* fe)
{
  // setting fm[f] to true means that the face has been reached and
  // that the face is available for recycling. If we do not want the
  // face to be available for recycling we must set this flag to
  // false.
  fm[f] = true;

  //  CGAL_assertion( fm.find(f) != fm.end() );
  for (int i = 0; i < 3; i++) {
    bool hidden_found =
      check_edge_for_hidden_sites(f, i, p, vm);

    Face_handle n = f->neighbor(i);

    if ( !hidden_found ) {
      Sign s = incircle(n, p);
      if ( s != NEGATIVE ) { continue; }

      bool interior_in_conflict = edge_interior(f, i, p, true);

      if ( !interior_in_conflict ) { continue; }
    }

    if ( fm.find(n) != fm.end() ) {
      Edge e = sym_edge(f, i);
      if ( l.is_in_list(e) ||
	   l.is_in_list(sym_edge(e)) ) {
	l.remove(e);
	l.remove(sym_edge(e));
      }
      continue;
    }

    Edge e = sym_edge(f, i);

    CGAL_assertion( l.is_in_list(e) );
    int j = tds().mirror_index(f, i);
    Edge e_before = sym_edge(n, ccw(j));
    Edge e_after = sym_edge(n, cw(j));
    if ( !l.is_in_list(e_before) ) {
      l.insert_before(e, e_before);
    }
    if ( !l.is_in_list(e_after) ) {
      l.insert_after(e, e_after);
    }
    l.remove(e);

    if ( fe != NULL ) {
      Vh_triple* vhq = new Vh_triple[1];

      (*vhq)[0] = Vertex_handle();
      (*vhq)[1] = n->vertex(     j  );
      (*vhq)[2] = n->vertex( ccw(j) );

      fe->push_back(vhq);
    }


    expand_conflict_region(n, p, l, fm, vm, fe);
  } // for-loop
}


//--------------------------------------------------------------------
// retriangulate conflict region
//--------------------------------------------------------------------

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
add_bogus_vertex(Edge e, List& l)
{
  Edge esym = sym_edge(e);
  Face_handle g1 = e.first;
  Face_handle g2 = esym.first;

  Vertex_handle v = insert_degree_2(e);
  Face_circulator fc(v);
  Face_handle f1(fc);
  Face_handle f2(++fc);
  int i1 = f1->index(v);
  int i2 = f2->index(v);

  CGAL_assertion( ((f1->neighbor(i1) == g1) && (f2->neighbor(i2) == g2)) ||
		  ((f1->neighbor(i1) == g2) && (f2->neighbor(i2) == g1)) );

  Edge ee, eesym;
  if ( f1->neighbor(i1) == g1 ) {
    ee = Edge(f2, i2);
    eesym = Edge(f1, i1);
  } else {
    ee = Edge(f1, i1);
    eesym = Edge(f2, i2);
  }

  l.replace(e, ee);
  l.replace(esym, eesym);

  return v;
}

template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_list
Apollonius_graph_2<Gt,Agds,LTag>::
add_bogus_vertices(List& l)
{
  Vertex_list vertex_list;
  Edge_list edge_list;

  Edge e_start = l.front();
  Edge e = e_start;
  do {
    Edge esym = sym_edge(e);
    if ( l.is_in_list(esym) &&
	 edge_list.find(esym) == edge_list.end() ) {
      edge_list.insert(e);
    }
    e = l.next(e);
  } while ( e != e_start );

  typename Edge_list::iterator it;

  for (it = edge_list.begin();  it != edge_list.end(); ++it) {
    e = *it;
    Vertex_handle v = add_bogus_vertex(e, l);
    vertex_list.push_back(v);
  }

  return vertex_list;
}

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_bogus_vertices(Vertex_list& vl)
{
  while ( vl.size() > 0 ) {
    Vertex_handle v = vl.front();
    vl.pop_front();
    remove_degree_2(v);
  }
}


template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
move_hidden_sites(Vertex_handle& vold, Vertex_handle& vnew)
{
  typename Vertex::Hidden_sites_iterator wpit;

  for (wpit = vold->hidden_sites_begin();
       wpit != vold->hidden_sites_end(); ++wpit) {
    vnew->add_hidden_site(*wpit);
  }

  vold->clear_hidden_sites_container();
}




template<class Gt, class Agds, class LTag>
std::vector<typename Apollonius_graph_2<Gt,Agds,LTag>::Face*>
Apollonius_graph_2<Gt,Agds,LTag>::
get_faces_for_recycling(Face_map& fm, unsigned int n_wanted)
{
  std::vector<Face*> vf;

  typename Face_map::iterator fmit;
  for (fmit = fm.begin(); fmit != fm.end(); ++fmit) {
    Face_handle f = (*fmit).first;
    if ( fm[f] == true ) { vf.push_back( f ); }
  }

  while ( vf.size() < n_wanted ) {
    Face* fp = static_cast<Face*>(this->_tds.create_face());
    vf.push_back(fp);
  }

  while ( vf.size() > n_wanted ) {
    Face* fp = vf.back();
    vf.pop_back();
    this->_tds.delete_face(fp);
  }
  
  return vf;
}

template<class Gt, class Agds, class LTag>
void
Apollonius_graph_2<Gt,Agds,LTag>::
remove_hidden_vertices(Vertex_map& vm)
{
  typename Vertex_map::iterator it;

  for (it = vm.begin(); it != vm.end(); ++it) {
    Vertex_handle vhidden = (*it).first;
    this->_tds.delete_vertex( vhidden );
  }
  vm.clear();
}


template<class Gt, class Agds, class LTag>
typename Apollonius_graph_2<Gt,Agds,LTag>::Vertex_handle
Apollonius_graph_2<Gt,Agds,LTag>::
retriangulate_conflict_region(const Site_2& p,	List& l, 
			      Face_map& fm, Vertex_map& vm)
{
  size_type vmsize = vm.size();
  size_type num_vert = number_of_vertices();

  if ( num_vert - vmsize == 0 ) {
    // 1. copy all hidden sites to a temporary list
    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. clear the current Apollonius diagram
    clear();

    // 3. add a new vertex
    Vertex_handle v = insert_first(p);

    // 4. add all old sites to the hidden site list of the
    // new site
    Site_list_iterator wpit;
    for (wpit = wp_list.begin(); wpit != wp_list.end(); ++wpit) {
      v->add_hidden_site(*wpit);
    }

    return v;
  } else if ( num_vert - vmsize == 1 ) {
    // 1. copy all hidden sites to a temporary list