segment_delaunay_graph_2_impl.h

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

    return v;
  }

  Vertex_triple vt = insert_point_on_segment(ss, t, v, tag);

  Vertex_handle vsx = vt.first;
  
  Storage_site_2 ss3 = st_.construct_storage_site_2_object()(ss, ssitev, true);
  Storage_site_2 ss4 = st_.construct_storage_site_2_object()(ss, ssitev, false);
  Site_2 s3 = ss3.site();
  Site_2 s4 = ss4.site();

  insert_segment_interior(s3, ss3, vsx);
  insert_segment_interior(s4, ss4, vsx);
  return vsx;
}

//--------------------------------------------------------------------
//--------------------------------------------------------------------
// helper methods for insertion (find conflict region)
//--------------------------------------------------------------------
//--------------------------------------------------------------------

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
initialize_conflict_region(const Face_handle& f, List& l)
{


  l.clear();
  for (int i = 0; i < 3; i++) {
    l.push_back(sym_edge(f, i));
  }
}


template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
expand_conflict_region(const Face_handle& f, const Site_2& t,
		       const Storage_site_2& ss,
		       List& l, Face_map& fm,
		       std::map<Face_handle,Sign>& sign_map,
		       Triple<bool,Vertex_handle,Arrangement_type>& vcross)
{
  if ( fm.find(f) != fm.end() ) { return; }

  // this is done to stop the recursion when intersecting segments
  // are found
  if ( vcross.first ) { 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());

    if ( !face_registered ) {
      for (int j = 0; j < 3; j++) {
	Vertex_handle vf = n->vertex(j);

	if ( is_infinite(vf) ) { continue; }

	Arrangement_type at_res = arrangement_type(t, vf);

	CGAL_assertion( vcross.third == AT2::DISJOINT ||
			vcross.third == AT2::CROSSING ||
			vcross.third == AT2::INTERIOR );

	if ( vf->is_segment() ) {
	  CGAL_assertion( at_res != AT2::IDENTICAL );
	  CGAL_assertion( at_res != AT2::TOUCH_11_INTERIOR_1 );
	  CGAL_assertion( at_res != AT2::TOUCH_12_INTERIOR_1 );

	  if ( at_res == AT2::CROSSING ) {
	    vcross.first = true;
	    vcross.second = vf;
	    vcross.third = AT2::CROSSING;
	    l.clear();
	    fm.clear();
	    return;
	  } else {
	    CGAL_assertion ( at_res == AT2::DISJOINT ||
			     at_res == AT2::TOUCH_1 ||
			     at_res == AT2::TOUCH_2 ||
			     at_res == AT2::TOUCH_11 ||
			     at_res == AT2::TOUCH_12 ||
			     at_res == AT2::TOUCH_21 ||
			     at_res == AT2::TOUCH_22 );
	    // we do nothing in these cases
	  }
	} else {
	  CGAL_assertion( vf->is_point() );
	  if ( at_res == AT2::INTERIOR ) {
	    vcross.first = true;
	    vcross.second = vf;
	    vcross.third = AT2::INTERIOR;
	    l.clear();
	    fm.clear();
	    return;
	  }
	}
      }
    }

    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(n, t, ss, l, fm, sign_map, vcross);

    // this is done to stop the recursion when intersecting segments
    // are found
    //    if ( fm.size() == 0 && l.size() == 0 ) { return; }
    if ( vcross.first ) { return; }
  } // for-loop
}


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

template<class Gt, class ST, class DS, class LTag>
typename Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::Vertex_handle
Segment_Delaunay_graph_2<Gt,ST,DS,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 ST, class DS, class LTag>
typename Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::Vertex_list
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
add_bogus_vertices(List& l)
{
  Vertex_list vertex_list;

  std::set<Edge> edge_list;

  edge_list.clear();

  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 std::set<Edge>::iterator it;

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

  return vertex_list;
}

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,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 ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
retriangulate_conflict_region(Vertex_handle v, List& l, 
			      Face_map& fm)
{
  // 1. add the bogus vetrices
  Vertex_list dummy_vertices = add_bogus_vertices(l);

  // 2. 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 );

  // 3. copy the edge list to a vector of edges and clear the edge list
  std::vector<Edge> ve;

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

  l.clear();

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

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

  // 6. 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);
  }

  fm.clear();

  // 7. DONE!!!!
}

//====================================================================
//====================================================================
//                   METHODS FOR REMOVAL
//====================================================================
//====================================================================

template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
is_star(const Vertex_handle& v) const
{
  CGAL_precondition( v->storage_site().is_point() );

  Vertex_circulator vc_start = incident_vertices(v);
  Vertex_circulator vc = vc_start;
  Storage_site_2 p = v->storage_site();

  size_type count = 0;
  do {
    Storage_site_2 ss = vc->storage_site();
    if ( ss.is_segment() && is_endpoint_of_segment(p, ss) ) {
      ++count;
      //      if ( count == 3 ) { break; }
      if ( count == 3 ) { return true; }
    }
    ++vc;
  } while ( vc != vc_start );

  return false;
}


template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
is_linear_chain(const Vertex_handle& v0, const Vertex_handle& v1,
		const Vertex_handle& v2) const
{
  Site_2 tt[3] = { v0->site(), v1->site(), v2->site() };

  if ( tt[1].is_point() &&
       tt[0].is_segment() &&
       tt[2].is_segment() &&
       is_endpoint_of_segment(tt[1], tt[0]) &&
       is_endpoint_of_segment(tt[1], tt[2]) ) {
    typename Geom_traits::Equal_2 are_equal = geom_traits().equal_2_object();
    Site_2 s_end[2];
    if (  are_equal( tt[1], tt[0].source_site() )  ) {
      s_end[0] = tt[0].target_site();
    } else {
      s_end[0] = tt[0].source_site();
    }

    if (  are_equal( tt[1], tt[2].source_site() )  ) {
      s_end[1] = tt[2].target_site();
    } else {
      s_end[1] = tt[2].source_site();
    }

    typename Geom_traits::Orientation_2 orientation =
      geom_traits().orientation_2_object();

    return orientation(s_end[0], s_end[1], tt[1]) == COLLINEAR;
  }
  return false;
}


template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
is_flippable(const Face_handle& f, int i) const
{
  CGAL_assertion( !is_infinite(f->vertex( cw(i) )) );

  Vertex_handle v_other = f->vertex( ccw(i) );
  Vertex_handle v0 = f->vertex( i );
  Vertex_handle v1 = this->_tds.mirror_vertex( f, i );

  if ( is_infinite(v_other) || is_infinite(v0) || is_infinite(v1) ) {
    return false;
  }

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

  Storage_site_2 ss = v->storage_site();
  Storage_site_2 ss_other = v_other->storage_site();
  if ( ss_other.is_point() && ss.is_segment() &&
       is_endpoint_of_segment(ss_other,	ss) && is_star(v_other) ) {
    return false;
  }

  if ( is_linear_chain(v0, v_other, v1) ) { return false; }

  return (v0 != v1) && is_degenerate_edge(f, i);
}


template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
minimize_degree(const 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 );

    if ( is_flippable(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 );
}

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
equalize_degrees(const Vertex_handle& v, Self& small_d,
		 std::map<Vertex_handle,Vertex_handle>& vmap,
		 List& l) const
{
  size_type deg = degree(v);
  CGAL_assertion( l.size() <= deg );
  if ( l.size() == deg ) { return; }
#if 0
  std::cerr << "size of l  : " << l.size() << std::endl;
  std::cerr << "degree of v: " << deg << 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_small_start = l.front();