segment_delaunay_graph_2_impl.h

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

  expand_conflict_region(start_f, t, ss, l, fm, sign_map, vcross);

  CGAL_assertion( !vcross.first );

  Vertex_handle v = create_vertex(ss);

  retriangulate_conflict_region(v, l, fm);

  return v;
}

//--------------------------------------------------------------------
// insertion of a point that lies on a segment
//--------------------------------------------------------------------

template<class Gt, class ST, class DS, class LTag>
typename Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::Face_pair
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
find_faces_to_split(const Vertex_handle& v, const Site_2& t) const
{
  CGAL_precondition( v->is_segment() );

#ifndef CGAL_NO_ASSERTIONS
  {
    // count number of adjacent infinite faces
    Face_circulator fc = incident_faces(v);
    Face_circulator fc_start = fc;
    int n_inf = 0;
    do {
      if ( is_infinite(fc) ) { n_inf++; }
      fc++;
    } while ( fc != fc_start );
    CGAL_assertion( n_inf == 0 || n_inf == 2 || n_inf == 4 );
  }
#endif

  Face_circulator fc1 = incident_faces(v);
  Face_circulator fc2 = fc1; ++fc2;
  Face_circulator fc_start = fc1;
  Face_handle f1, f2;
  bool found_f1 = false, found_f2 = false;
  Site_2 sitev_supp = v->site().supporting_site();
  do {
    Face_handle ff1(fc1), ff2(fc2);

    Oriented_side os1, os2;

    if ( is_infinite(ff1) ) {
      int id_v = ff1->index(v);
      int cw_v = this->cw( id_v );
      int ccw_v = this->ccw( id_v );

      Site_2 sv_ep;
      if ( is_infinite( ff1->vertex(cw_v) ) ) {
	CGAL_assertion(  !is_infinite( ff1->vertex(ccw_v) )  );
	CGAL_assertion( ff1->vertex(ccw_v)->site().is_point() );
	sv_ep = ff1->vertex(ccw_v)->site();
      } else {
	CGAL_assertion(  !is_infinite( ff1->vertex( cw_v) )  );
	CGAL_assertion( ff1->vertex( cw_v)->site().is_point() );
	sv_ep = ff1->vertex( cw_v)->site();
      }

      os1 = oriented_side(sv_ep, sitev_supp, t);
    } else {
      os1 = oriented_side(fc1->vertex(0)->site(),
			  fc1->vertex(1)->site(),
			  fc1->vertex(2)->site(),
			  sitev_supp, t);
    }

    if ( is_infinite(ff2) ) {
      int id_v = ff2->index(v);
      int cw_v = this->cw( id_v );
      int ccw_v = this->ccw( id_v );

      Site_2 sv_ep;
      if ( is_infinite( ff2->vertex(cw_v) ) ) {
	CGAL_assertion(  !is_infinite( ff2->vertex(ccw_v) )  );
	CGAL_assertion( ff2->vertex(ccw_v)->site().is_point() );
	sv_ep = ff2->vertex(ccw_v)->site();
      } else {
	CGAL_assertion(  !is_infinite( ff2->vertex( cw_v) )  );
	CGAL_assertion( ff2->vertex( cw_v)->site().is_point() );
	sv_ep = ff2->vertex( cw_v)->site();
      }

      os2 = oriented_side(sv_ep, sitev_supp, t);
    } else {
      os2 = oriented_side(fc2->vertex(0)->site(),
			  fc2->vertex(1)->site(),
			  fc2->vertex(2)->site(),
			  sitev_supp, t);
    }

    if ( !found_f1 &&
	 os1 != ON_POSITIVE_SIDE && os2 == ON_POSITIVE_SIDE ) {
      f1 = ff2;
      found_f1 = true;
    }

    if ( !found_f2 &&
	 os1 == ON_POSITIVE_SIDE && os2 != ON_POSITIVE_SIDE ) {
      f2 = ff2;
      found_f2 = true;
    }

    if ( found_f1 && found_f2 ) { break; }

    ++fc1, ++fc2;
  } while ( fc_start != fc1 ); 


  CGAL_assertion( found_f1 && found_f2 );
  CGAL_assertion( f1 != f2 );

  return Face_pair(f1, f2);
}

template<class Gt, class ST, class DS, class LTag>
typename Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::Vertex_triple
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
insert_exact_point_on_segment(const Storage_site_2& ss, const Site_2& t,
			      Vertex_handle v)
{
  // splits the segment site v->site() in two and inserts represented by t
  // on return the three vertices are, respectively, the vertex
  // corresponding to t and the two subsegments of v->site()

  CGAL_assertion( t.is_point() );
  CGAL_assertion( t.is_input() );

  Storage_site_2 ssitev = v->storage_site();  

  CGAL_assertion( ssitev.is_segment() );

  Face_pair fpair = find_faces_to_split(v, t);

  boost::tuples::tuple<Vertex_handle,Vertex_handle,Face_handle,Face_handle>
    qq = this->_tds.split_vertex(v, fpair.first, fpair.second);

  // now I need to update the sites for vertices v1 and v2
  Vertex_handle v1 = boost::tuples::get<0>(qq); //qq.first;
  Storage_site_2 ssv1 = split_storage_site(ssitev, ss, true);
  v1->set_site( ssv1 );

  Vertex_handle v2 = boost::tuples::get<1>(qq); //qq.second;
  Storage_site_2 ssv2 = split_storage_site(ssitev, ss, false);
  v2->set_site( ssv2 );

  Face_handle qqf = boost::tuples::get<2>(qq); //qq.third;
  Vertex_handle vsx =
    this->_tds.insert_in_edge(qqf, cw(qqf->index(v1)));

  vsx->set_site(ss);
  // merge info of point and segment; the point lies on the segment
  merge_info(vsx, ssitev);

  return Vertex_triple(vsx, v1, v2);
}

template<class Gt, class ST, class DS, class LTag>
typename Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::Vertex_triple
Segment_Delaunay_graph_2<Gt,ST,DS,LTag>::
insert_point_on_segment(const Storage_site_2& ss, const Site_2& ,
			Vertex_handle v, const Tag_true&)
{
  // splits the segment site v->site() in two and inserts the point of
  // intersection of t and v->site()
  // on return the three vertices are, respectively, the point of
  // intersection and the two subsegments of v->site()

  Storage_site_2 ssitev = v->storage_site();
  Storage_site_2 ssx = st_.construct_storage_site_2_object()(ss, ssitev);

  Site_2 sitev = ssitev.site();

  Face_pair fpair = find_faces_to_split(v, ssx.site());

  boost::tuples::tuple<Vertex_handle,Vertex_handle,Face_handle,Face_handle>
    qq = this->_tds.split_vertex(v, fpair.first, fpair.second);

  // now I need to update the sites for vertices v1 and v2
  Vertex_handle v1 = boost::tuples::get<0>(qq); //qq.first;
  Vertex_handle v2 = boost::tuples::get<1>(qq); //qq.second;

  Storage_site_2 ssv1 =
    st_.construct_storage_site_2_object()(ssitev, ss, true);

  Storage_site_2 ssv2 =
    st_.construct_storage_site_2_object()(ssitev, ss, false);

  Site_2 sv1 = ssv1.site();
  Site_2 sv2 = ssv2.site();
  v1->set_site( ssv1 );
  v2->set_site( ssv2 );

  Face_handle qqf = boost::tuples::get<2>(qq); //qq.third;
  Vertex_handle vsx =
    this->_tds.insert_in_edge(qqf, cw(qqf->index(v1)));

  vsx->set_site(ssx);

  return Vertex_triple(vsx, v1, v2);
}

//--------------------------------------------------------------------
// insertion of a segment
//--------------------------------------------------------------------
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>::
insert_segment(const Storage_site_2& ss, const Site_2& t, Vertex_handle vnear)
{
  CGAL_precondition( t.is_segment() );
  CGAL_precondition( t.is_input() );

  if ( is_degenerate_segment(t) ) {
    Storage_site_2 ss_src = ss.source_site();
    convert_info(ss_src, ss, true);
    return insert_point(ss_src, t.source(), vnear);
  }

  Storage_site_2 ss_src = ss.source_site();
  convert_info(ss_src, ss, true);
  Storage_site_2 ss_trg = ss.target_site();
  convert_info(ss_trg, ss, false);

  Vertex_handle v0 = insert_point( ss_src, t.source(), vnear );
  CGAL_assertion( is_valid() );
  Vertex_handle v1 = insert_point( ss_trg, t.target(), v0 );
  CGAL_assertion( is_valid() );

  if ( number_of_vertices() == 2 ) {
    return insert_third(ss, v0, v1);
  }

  return insert_segment_interior(t, ss, v0);
}


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>::
insert_segment_interior(const Site_2& t, const Storage_site_2& ss,
			Vertex_handle vnearest)
{
  CGAL_precondition( t.is_segment() );
  CGAL_precondition( number_of_vertices() > 2 );

  CGAL_assertion( vnearest != Vertex_handle() );

  // find the first conflict

  // first look if there are intersections...
  Vertex_circulator vc = incident_vertices(vnearest);
  Vertex_circulator vc_start = vc;
  do {
    Vertex_handle vv(vc);
    if ( is_infinite(vv) ) {
      vc++;
      continue;
    }

    Arrangement_type at_res = arrangement_type(t, vv);

    if ( vv->is_segment() ) {
      if ( 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 ) {
	// do nothing
      } else if ( at_res == AT2::IDENTICAL ) {
	// merge info of identical items
	merge_info(vv, ss);
	return vv;
      } else if ( at_res == AT2::CROSSING ) {
	Intersections_tag itag;
	return insert_intersecting_segment(ss, t, vv, itag);
      } else if ( at_res == AT2::TOUCH_11_INTERIOR_1 ) {
	Vertex_handle vp = second_endpoint_of_segment(vv);	
	Storage_site_2 ssvp = vp->storage_site();
	Storage_site_2 sss = split_storage_site(ss, ssvp, false);

	Storage_site_2 sss1 = split_storage_site(ss, ssvp, true);
	// merge the info of the first (common) subsegment
	merge_info(vv, sss1);
	// merge the info of the (common) splitting endpoint
	merge_info(vp, ss);

	return insert_segment_interior(sss.site(), sss, vp);
      } else if ( at_res == AT2::TOUCH_12_INTERIOR_1 ) {
	Vertex_handle vp = first_endpoint_of_segment(vv);	
	Storage_site_2 ssvp = vp->storage_site();
	Storage_site_2 sss = split_storage_site(ss, ssvp, true);

	Storage_site_2 sss1 = split_storage_site(ss, ssvp, false);
	// merge the info of the second (common) subsegment
	//	merge_info(vv, sss);
	// merge the info of the (common) splitting endpoint
	merge_info(vp, ss);

	return insert_segment_interior(sss.site(), sss, vp);
      } else {
	// this should never be reached; the only possible values for
	// at_res are DISJOINT, CROSSING, TOUCH_11_INTERIOR_1
	// and TOUCH_12_INTERIOR_1
	CGAL_assertion( false );
      }
    } else {
      CGAL_assertion( vv->is_point() );
      if ( at_res == AT2::INTERIOR ) {
	Storage_site_2 ssvv = vv->storage_site();
	if ( ssvv.is_input() ) {
	  Storage_site_2 ss1 = split_storage_site(ss, ssvv, true);
	  Storage_site_2 ss2 = split_storage_site(ss, ssvv, false);
	  // merge the info of the splitting point and the segment
	  merge_info(vv, ss);
	  insert_segment_interior(ss1.site(), ss1, vv);
	  return insert_segment_interior(ss2.site(), ss2, vv);
	} else {
	  // this should never be reached; the only possible values for
	  // at_res are DISJOINT and INTERIOR
	  CGAL_assertion( false );
	}
      }
    }
    ++vc;
  } while ( vc != vc_start );

  // first look for conflict with vertex
  Face_circulator fc_start = incident_faces(vnearest);
  Face_circulator fc = fc_start;
  Face_handle start_f;
  Sign s;

  std::map<Face_handle,Sign> 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 );

  // segments must have a conflict with at least one vertex
  CGAL_assertion( s == NEGATIVE );

  // we are in conflict with a Voronoi vertex; start from that and 
  // find the entire conflict region and then repair the diagram
  List l;
  Face_map fm;

  Triple<bool, Vertex_handle, Arrangement_type>
    vcross(false, Vertex_handle(), AT2::DISJOINT);

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

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

  // the following condition becomes true only if intersecting
  // segments are found
  if ( vcross.first ) {
    if ( t.is_segment() ) {
      if ( vcross.third == AT2::CROSSING ) {
	Intersections_tag itag;
	return insert_intersecting_segment(ss, t, vcross.second, itag);
      } else if ( vcross.third == AT2::INTERIOR ) {
	Storage_site_2 ssvv = vcross.second->storage_site();
	Storage_site_2 ss1 = split_storage_site(ss, ssvv, true);
	Storage_site_2 ss2 = split_storage_site(ss, ssvv, false);
	// merge the info of the splitting point and the segment
	merge_info(vcross.second, ss);
	insert_segment_interior(ss1.site(), ss1, vcross.second);
	return insert_segment_interior(ss2.site(), ss2, vcross.second);
      } else {
	// this should never be reached; the only possible values for
	// vcross.third are CROSSING, INTERIOR and DISJOINT
	CGAL_assertion( false );
      }
    }
  }

  // no intersecting segment has been found; we insert the segment as
  // usual...
  Vertex_handle v = create_vertex(ss);

  retriangulate_conflict_region(v, l, fm);

  return v;
}


//--------------------------------------------------------------------
// insertion of an intersecting segment
//--------------------------------------------------------------------
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>::
insert_intersecting_segment_with_tag(const Storage_site_2& /* ss */,
				     const Site_2& /* t */, Vertex_handle /* v */,
				     Tag_false)
{
#if defined(__POWERPC__) && \
  defined(__GNUC__) && (__GNUC__ == 3) && (__GNUC_MINOR__ == 4)
  // hack to avoid nasty warning for G++ 3.4 on Darwin
  static int i;
#else
  static int i = 0;
#endif
  if ( i == 0 ) {
    i = 1;
    print_error_message();
  }
  return Vertex_handle();
}

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>::
insert_intersecting_segment_with_tag(const Storage_site_2& ss,
				     const Site_2& t, Vertex_handle v,
				     Tag_true tag)
{
  CGAL_precondition( t.is_segment() && v->is_segment() );

  const Storage_site_2& ssitev = v->storage_site();
  Site_2 sitev = ssitev.site();

  if ( same_segments(t, sitev) ) {
    merge_info(v, ss);