segment_delaunay_graph_2_impl.h

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

      if ( t.is_input() ) {
	small_d.insert(t);
      } else if ( t.is_point() ) {
	small_d.insert(t.supporting_site(0));
	/*Vertex_handle vnear =*/ small_d.insert(t.supporting_site(1));
	//	vh_small = sdg_small.nearest_neighbor(t, vnear);
      } else {
	CGAL_assertion( t.is_segment() );
	/*Vertex_handle vnear =*/ small_d.insert(t.supporting_site());
	//	vh_small = sdg_small.nearest_neighbor(t, vnear);
      }
      //      CGAL_assertion( vh_small != Vertex_handle() );
      //      vmap[vh_small] = vh_large;
    }
    ++vc;
  } while ( vc != vc_start );
}

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

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
compute_vertex_map(const Vertex_handle& v, const Self& small_d,
		   std::map<Vertex_handle,Vertex_handle>& vmap) const
{
  Vertex_circulator vc_start = incident_vertices(v);
  Vertex_circulator vc = vc_start;
  Vertex_handle vh_large, vh_small;

  do {
    vh_large = Vertex_handle(vc);
    if ( is_infinite(vh_large) ) {
      vh_small = small_d.infinite_vertex();
      vmap[vh_small] = vh_large;
    } else { 
#if !defined(CGAL_NO_ASSERTIONS) && !defined(NDEBUG)
      vh_small = Vertex_handle();
#endif
      Site_2 t = vc->site();
      if ( t.is_input() ) {
	if ( t.is_segment() ) {
	  Vertex_handle vv = small_d.nearest_neighbor( t.source() );
	  Vertex_circulator vvc_start = small_d.incident_vertices(vv);
	  Vertex_circulator vvc = vvc_start;
	  do {
	    if ( small_d.same_segments(t, vvc) ) {
	      vh_small = vvc;
	      break;
	    }
	  } while ( ++vvc != vvc_start );
	  CGAL_assertion( small_d.same_segments(t, vh_small) );
	} else {
	  CGAL_assertion( t.is_point() );
	  vh_small = small_d.nearest_neighbor( t.point() );
	  CGAL_assertion( small_d.same_points(t, vh_small->site()) );
	}
      } else if ( t.is_segment() ) {
	Vertex_handle vv =
	  small_d.nearest_neighbor( t.source_site(), Vertex_handle() );
	Vertex_circulator vvc_start = small_d.incident_vertices(vv);
	Vertex_circulator vvc = vvc_start;
	do {
	  if ( small_d.same_segments(t, vvc) ) {
	    vh_small = vvc;
	    break;
	  }
	} while ( ++vvc != vvc_start );
	CGAL_assertion( small_d.same_segments(t, vh_small) );
      } else {
	CGAL_assertion( t.is_point() );
	vh_small = small_d.nearest_neighbor( t, Vertex_handle() );
	CGAL_assertion( small_d.same_points(t, vh_small->site()) );
      }
      CGAL_assertion( vh_small != Vertex_handle() );
      vmap[vh_small] = vh_large;
    }
    ++vc;
  } while ( vc != vc_start );
}


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

template<class Gt, class ST, class DS, class LTag>
void
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
remove_degree_d_vertex(const Vertex_handle& v)
{
#if 0
  Self sdg_small;
  compute_small_diagram(v, sdg_small);
  std::map<Vertex_handle,Vertex_handle> vmap;
  compute_vertex_map(v, sdg_small, vmap);

  // find nearest neighbor of v in small diagram
  Site_2 t = v->site();
  Vertex_handle vn;

  CGAL_assertion( t.is_input() );

  if ( t.is_point() ) {
    vn = sdg_small.nearest_neighbor( t.point() );
  } else {
    vn = sdg_small.nearest_neighbor( t.source() );
  }
  CGAL_assertion( vn != Vertex_handle() );

  List l;
  Face_map fm;
  Sign_map sign_map;

  sdg_small.find_conflict_region_remove(v, vn, l, fm, sign_map);

  fm.clear();
  sign_map.clear();

  equalize_degrees(v, sdg_small, vmap, l);

  fill_hole(sdg_small, v, l, vmap);

  l.clear();
  return;

#else
  minimize_degree(v);
  int deg = degree(v);
  if ( deg == 3 ) {
    remove_degree_3(v);
    return;
  }
  if ( deg == 2 ) {
    remove_degree_2(v);
    return;
  }
  
  Self sdg_small;
  compute_small_diagram(v, sdg_small);

  if ( sdg_small.number_of_vertices() <= 2 ) {
    CGAL_assertion( sdg_small.number_of_vertices() == 2 );
    CGAL_assertion( deg == 4 );
    Edge_circulator ec_start = incident_edges(v);
    Edge_circulator ec = ec_start;
    do {
      if ( is_infinite(*ec) ) { break; }
      ++ec;
    } while ( ec != ec_start );
    CGAL_assertion( is_infinite(ec) );
    flip(*ec);
    remove_degree_3(v);
    return;
  }

  std::map<Vertex_handle,Vertex_handle> vmap;
  compute_vertex_map(v, sdg_small, vmap);

  // find nearest neighbor of v in small diagram
  Site_2 t = v->site();
  Vertex_handle vn;

  CGAL_assertion( t.is_input() );

  // here we find a site in the small diagram that serves as a
  // starting point for finding all conflicts.
  // To do that we find the nearest neighbor of t if t is a point;
  // t is guarranteed to have a conflict with its nearest neighbor
  // If t is a segment, then one endpoint of t is enough; t is
  // guarranteed to have a conflict with the Voronoi edges around
  // this endpoint
  if ( t.is_point() ) {
    vn = sdg_small.nearest_neighbor( t.point() );
  } else {
    vn = sdg_small.nearest_neighbor( t.source() );
  }
  CGAL_assertion( vn != Vertex_handle() );

  List l;
  Face_map fm;
  Sign_map sign_map;

  sdg_small.find_conflict_region_remove(v, vn, l, fm, sign_map);

  fill_hole(sdg_small, v, l, vmap);

  l.clear();
  fm.clear();
  sign_map.clear();
#endif
}

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

template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
remove_base(const Vertex_handle& v)
{
  Storage_site_2 ssv = v->storage_site();
  CGAL_precondition( ssv.is_input() );

  // first consider the case where we have up to 2 points
  size_type n = number_of_vertices();

  if ( n == 1 ) {
    return remove_first(v);
  } else if ( n == 2 ) {
    return remove_second(v);
  } 

  // secondly check if the point to be deleted is adjacent to a segment
  if ( ssv.is_point() ) {
    Vertex_circulator vc_start = incident_vertices(v);
    Vertex_circulator vc = vc_start;

    do {
      Storage_site_2 ss = vc->storage_site();
      if ( ss.is_segment() && is_endpoint_of_segment(ssv, ss) ) {
	return false;
      }
      ++vc;
    } while ( vc != vc_start );
  }

  // now do the deletion
  if ( n == 3 ) {
    return remove_third(v);
  }

  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);
  }

  return true;
}

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

template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
remove(const Vertex_handle& v)
{
  CGAL_precondition( !is_infinite(v) );
  const Storage_site_2& ss = v->storage_site();

  if ( !ss.is_input() ) { return false; }

  Point_handle h1, h2;
  bool is_point = ss.is_point();
  if ( is_point ) {
    h1 = ss.point();
  } else {
    CGAL_assertion( ss.is_segment() );   
    h1 = ss.source_of_supporting_site();
    h2 = ss.target_of_supporting_site();
  }

  bool success = remove_base(v);

  if ( success ) {
    // unregister the input site
    if ( is_point ) {
      unregister_input_site( h1 );
    } else {
      unregister_input_site( h1, h2 );
    }
  }
  return success;
}

//--------------------------------------------------------------------
//--------------------------------------------------------------------
// combinatorial operations
//--------------------------------------------------------------------
//--------------------------------------------------------------------

//--------------------------------------------------------------------
//--------------------------------------------------------------------
// point location
//--------------------------------------------------------------------
//--------------------------------------------------------------------
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>::
nearest_neighbor(const Site_2& p,
		 Vertex_handle start_vertex) const
{
  CGAL_precondition( p.is_point() );

  if ( number_of_vertices() == 0 ) {
    return Vertex_handle();
  }

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

  //  if ( start_vertex == NULL ) { 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 t0 = vclosest->site();
	Site_2 t1 = v1->site();
	if ( side_of_bisector(t0, t1, p) == ON_NEGATIVE_SIDE ) {
	  vclosest = v1;
	}
      }
    }
    return vclosest;
  }

  do {
    vclosest = v;
    Site_2 t0 = v->site();
    //    if ( t0.is_point() && same_points(p, t0) ) {
    //      return vclosest;
    //    }
    Vertex_circulator vc_start = incident_vertices(v);
    Vertex_circulator vc = vc_start;
    do {
      if ( !is_infinite(vc) ) {
	Vertex_handle v1(vc);
	Site_2 t1 = v1->site();
	Oriented_side os = side_of_bisector(t0, t1, p);

	if ( os == ON_NEGATIVE_SIDE ) {
	  v = v1;
	  break;
	}
      }
      ++vc;
    } while ( vc != vc_start );
  } while ( vclosest != v );

  return vclosest;
}

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

template<class Gt, class ST, class DS, class LTag>
Sign
Segment_Delaunay_graph_2<Gt,ST,DS,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 ST, class DS, class LTag>
Sign
Segment_Delaunay_graph_2<Gt,ST,DS,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());
}


// this the finite edge interior predicate for a degenerate edge
template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
finite_edge_interior(const Face_handle& f, int i, const Site_2& q,
		     Sign sgn, int) const
{
  if ( !is_infinite( this->_tds.mirror_vertex(f, i) ) ) {
    CGAL_precondition( is_infinite(f->vertex(i)) );

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

    return finite_edge_interior(g, j, q, sgn, 0 /* degenerate */);
  }

  CGAL_precondition( is_infinite( this->_tds.mirror_vertex(f, i) ) );

  Site_2 t1 = f->vertex( ccw(i) )->site();
  Site_2 t2 = f->vertex(  cw(i) )->site();

  if ( is_infinite(f->vertex(i)) ) {
    return finite_edge_interior(t1, t2, q, sgn);
  }

  Site_2 t3 = f->vertex(i)->site();
  return finite_edge_interior(t1, t2, t3, q, sgn);
}

template<class Gt, class ST, class DS, class LTag>
bool
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
finite_edge_