segment_delaunay_graph_2_impl.h

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

  Edge e_small = e_small_start;
  bool found;
  Edge e_small_begin;
  Edge e_large_begin;
  do {
    found = false;
    Vertex_handle v_sml_src = e_small.first->vertex(cw(e_small.second));
    Vertex_handle v_sml_trg = e_small.first->vertex(ccw(e_small.second));

    // first we find a first edge in common
    Face_circulator fc_start = incident_faces(v);
    Face_circulator fc = fc_start;

    do {
      int id = fc->index(v);
      Vertex_handle v_lrg_src = fc->vertex(ccw(id));
      Vertex_handle v_lrg_trg = fc->vertex(cw(id));
      if ( vmap[v_sml_src] == v_lrg_src && vmap[v_sml_trg] == v_lrg_trg ) {
	found = true;
	e_large_begin = Edge(fc, id);
	e_small_begin = e_small;
	break;
      }
    } while ( ++fc != fc_start );
    if ( found ) { break; }
    e_small = l.next(e_small);
  } while ( e_small != e_small_start );

  CGAL_assertion( found );

  Face_circulator fc_start = incident_faces(v, e_large_begin.first);
  Face_circulator fc = fc_start;
  e_small = e_small_begin;
  do {
    int id = fc->index(v);
    Vertex_handle vsml_src = e_small.first->vertex(cw(e_small.second));
    Vertex_handle vsml_trg = e_small.first->vertex(ccw(e_small.second));
    Vertex_handle vlrg_src = fc->vertex(ccw(id));
    Vertex_handle vlrg_trg = fc->vertex(cw(id));
    if ( vmap[vsml_src] != vlrg_src || vmap[vsml_trg] != vlrg_trg ) {
      Edge e_small_prev = l.previous(e_small);
      std::cerr << "size of l: " << l.size() << std::endl;
      l.remove(e_small);

      std::cerr << "size of l: " << l.size() << std::endl;

      Edge e_small_new = small_d.flip(e_small);
      Edge e_small_new_sym = small_d.sym_edge(e_small_new);
      Face_handle f1 = e_small_new.first;
      Face_handle f2 = e_small_new_sym.first;

      if ( f2->vertex(e_small_new_sym.second) == vsml_src ) {
	std::swap(f1, f2);
	std::swap(e_small_new, e_small_new_sym);
	CGAL_assertion( f1->vertex(e_small_new.second) == vsml_src );
	CGAL_assertion( f2->vertex(e_small_new_sym.second) == vsml_trg );
      }

      Edge to_list1(f1, cw(e_small_new.second));
      Edge to_list2(f2, ccw(e_small_new_sym.second));

      e_small = small_d.sym_edge(to_list1);

      l.insert_after(e_small_prev, e_small);
      std::cerr << "size of l: " << l.size() << std::endl;
      l.insert_after(e_small, small_d.sym_edge(to_list2));
      std::cerr << "size of l: " << l.size() << std::endl;
    } else {
      e_small = l.next(e_small);
      ++fc;
    }
    CGAL_assertion( l.size() <= deg );
  } while ( fc != fc_start );

#if 0
  std::cerr << "size of l  : " << l.size() << std::endl;
  std::cerr << "degree of v: " << deg << std::endl;
#endif

#if !defined(CGAL_NO_ASSERTIONS) && !defined(NDEBUG)  
  // we go around the boundary of the conflict region verify that all
  // edges are there
  CGAL_assertion( l.size() == degree(v) );
  e_small = e_small_begin;
  fc_start = incident_faces(v, e_large_begin.first);
  fc = fc_start;
  do {
    int id = fc->index(v);
    Vertex_handle vsml_src = e_small.first->vertex(cw(e_small.second));
    Vertex_handle vsml_trg = e_small.first->vertex(ccw(e_small.second));
    Vertex_handle vlrg_src = fc->vertex(ccw(id));
    Vertex_handle vlrg_trg = fc->vertex(cw(id));
    CGAL_assertion(vmap[vsml_src] == vlrg_src && vmap[vsml_trg] == vlrg_trg );

    // go to next edge
    e_small = l.next(e_small);
  } while ( ++fc != fc_start );
#endif
}

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
expand_conflict_region_remove(const Face_handle& f, const Site_2& t,
			      const Storage_site_2& ss,
			      List& l, Face_map& fm, Sign_map& sign_map)
{
  if ( fm.find(f) != fm.end() ) { return; }

  // 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++) {
    Face_handle n = f->neighbor(i);

    bool face_registered = (fm.find(n) != fm.end());

    Sign s = incircle(n, t);

    sign_map[n] = s;

    Sign s_f = sign_map[f];

    if ( s == POSITIVE ) { continue; }
    if ( s != s_f ) { continue; }

    bool interior_in_conflict = edge_interior(f, i, t, s);

    if ( !interior_in_conflict ) { continue; }

    if ( face_registered ) { continue; }

    Edge e = sym_edge(f, i);

    CGAL_assertion( l.is_in_list(e) );
    int j = this->_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);

    expand_conflict_region_remove(n, t, ss, l, fm, sign_map);
  } // for-loop
}


template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
find_conflict_region_remove(const Vertex_handle& v,
			    const Vertex_handle& vnearest,
			    List& l, Face_map& fm, Sign_map&)
{
  CGAL_precondition( vnearest != Vertex_handle() );
  Storage_site_2 ss = v->storage_site();
  Site_2 t = ss.site();

  // 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;

  Sign_map sign_map;

  do {
    Face_handle f(fc);

    s = incircle(f, t);

    sign_map[f] = s;

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

  CGAL_assertion( s == NEGATIVE );

  // we are not in conflict with a Voronoi vertex, so we have to
  // be in conflict with the interior of a Voronoi 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;

      Sign s1 = sign_map[e.first];
      Sign s2 = sign_map[e.first->neighbor(e.second)];

      if ( s1 == s2 ) {
	interior_in_conflict = edge_interior(e, t, s1);
      } else {
	// It seems that there was a problem here when one of the
	// signs was positive and the other zero. In this case we
	// still check pretending that both signs where positive
	interior_in_conflict = edge_interior(e, t, POSITIVE);
      }

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

    sign_map.clear();

    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_remove(start_f, t, ss,	l, fm, sign_map);
}


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

template<class Gt, class ST, class DS, class LTag>
typename Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::size_type
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
count_faces(const List& l) const
{
  std::vector<Face_handle> flist;
  get_faces(l, std::back_inserter(flist));
  return flist.size();
}

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

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
fill_hole(const Self& small_d, const Vertex_handle& v, const List& l,
	  std::map<Vertex_handle,Vertex_handle>& vmap)
{
#if 0
  std::cerr << "size of l  : " << l.size() << std::endl;
  std::cerr << "degree of v: " << degree(v) << std::endl;
#endif

  typedef std::map<Edge,Edge>  Edge_map;
  // maps edges on the boundary of the conflict region from the small
  // diagram to edges of the star of v in the small diagram
  Edge_map emap;

  Edge e_sml_sym = sym_edge(l.front());

  Vertex_handle v_sml_src = e_sml_sym.first->vertex(ccw(e_sml_sym.second));
  Vertex_handle v_sml_trg = e_sml_sym.first->vertex(cw(e_sml_sym.second));

  // first we find a first edge in common
  Face_circulator fc_start = incident_faces(v);
  Face_circulator fc = fc_start;
  Face_circulator fc_begin;
  bool found = false;
  do {
    int id = fc->index(v);
    Vertex_handle v_lrg_src = fc->vertex(ccw(id));
    Vertex_handle v_lrg_trg = fc->vertex(cw(id));
    if ( vmap[v_sml_src] == v_lrg_src && vmap[v_sml_trg] == v_lrg_trg ) {
      found = true;
      fc_begin = fc;
      break;
    }
  } while ( ++fc != fc_start );
  CGAL_assertion( found );

  // container of faces to delete
  std::list<Face_handle> to_delete;

  // next we go around the boundary of the conflict region and map all edges
  Edge e_small = l.front();
  fc_start = incident_faces(v, fc_begin);
  fc = fc_start;
  do {
    int id = fc->index(v);
#if !defined(CGAL_NO_ASSERTIONS) && !defined(NDEBUG)
    Vertex_handle vsml_src = e_small.first->vertex(cw(e_small.second));
    Vertex_handle vsml_trg = e_small.first->vertex(ccw(e_small.second));
    Vertex_handle vlrg_src = fc->vertex(ccw(id));
    Vertex_handle vlrg_trg = fc->vertex(cw(id));
    CGAL_assertion(vmap[vsml_src] == vlrg_src && vmap[vsml_trg] == vlrg_trg );
#endif
    // set mapping
    emap[e_small] = sym_edge(fc, id);
    // keep face for deletion
    to_delete.push_back(fc);
    // go to next edge
    e_small = l.next(e_small);
  } while ( ++fc != fc_start );


  // map the faces of the small diagram with the new faces of the
  // large diagram
  std::map<Face_handle,Face_handle> fmap;
  std::vector<Face_handle> f_small, f_large;

  small_d.get_faces(l, std::back_inserter(f_small));
  for (unsigned int i = 0; i < f_small.size(); i++) {
    Face_handle f = this->_tds.create_face();
    fmap[ f_small[i] ] = f;
    f_large.push_back(f);
  }

  CGAL_assertion( l.size() == degree(v) );
  CGAL_assertion( f_small.size() == f_large.size() );
  CGAL_assertion( f_small.size() == l.size() - 2 );
  CGAL_assertion( f_small.size() == count_faces(l) );

  // set the vertices for the new faces; also set the face for each
  // vertex
  for (typename std::vector<Face_handle>::iterator fit = f_small.begin();
       fit != f_small.end(); ++fit) {
    Face_handle ff_small = *fit;
    Face_handle f = fmap[ff_small];

    for (int i = 0; i < 3; ++i) {
      CGAL_assertion( vmap.find(ff_small->vertex(i)) != vmap.end() );
      f->set_vertex(i, vmap[ff_small->vertex(i)]);
      // we are setting the face for each vertex a lot of times; we
      // could possibly do it faster if we use the edges on the
      // boundary of the conflict region
      // in fact we may not even need it since the make_hole method
      // updates the faces of the vertices of the boundary of the
      // hole, and we do not introduce any new vertices
      f->vertex(i)->set_face(f);
    }
  }

  // set the neighbors for each face
  for (typename std::vector<Face_handle>::iterator fit = f_small.begin();
       fit != f_small.end(); ++fit) {
    Face_handle ff_small = *fit;

    for (int i = 0; i < 3; i++) {
      Face_handle f = fmap[ff_small];
      Face_handle n_small = ff_small->neighbor(i);
      if ( fmap.find(n_small) != fmap.end() ) {
	// this is one of the new faces
	f->set_neighbor(i, fmap[n_small]);
      } else {
	// otherwise it is one of the old faces outside the conflict
	// region; we have to use the edge map in this case
	Edge e_small_sym = small_d.sym_edge(ff_small, i);
	CGAL_assertion(emap.find(e_small_sym) != emap.end());

	Edge e_large = emap[e_small_sym];
	f->set_neighbor(i, e_large.first);
	e_large.first->set_neighbor(e_large.second, f);
      }
    }
  }

  // delete the unused faces and the vertex
  while ( !to_delete.empty() ) {
    delete_face(to_delete.front());
    to_delete.pop_front();
  }
  delete_vertex(v);
}

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

template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
remove_first(const Vertex_handle& v)
{
  Delaunay_graph::remove_first(v);
  return true;
}

template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
remove_second(const Vertex_handle& v)
{
  Delaunay_graph::remove_second(v);
  return true;
}

template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
remove_third(const Vertex_handle& v)
{
  if ( is_degree_2(v) ) {
    CGAL_assertion( v->storage_site().is_point() );
    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 );
  return true;
}

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

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
compute_small_diagram(const Vertex_handle& v, Self& small_d) const
{
  Vertex_circulator vc_start = incident_vertices(v);
  Vertex_circulator vc = vc_start;

  // insert all neighboring sites
  do {
    if ( !is_infinite(vc) ) {
      Site_2 t = vc->site();