internal_functions_on_circular_arc_2.h

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

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        Circular_arc_2::template 
          put_intersection_circle_circle< std::vector < CGAL::Object > >
          (a1,a2,solutions);
      }
#endif
      
      if(solutions.size() == 0) return res;
      else {
        // The supporting circles are not the same and intersects
        for (typename solutions_container::iterator it = solutions.begin(); 
	 it != solutions.end(); ++it) {
          const std::pair<typename CK::Circular_arc_point_2, unsigned> 
            *result = CGAL::object_cast
              <std::pair<typename CK::Circular_arc_point_2, unsigned> > (&(*it));          

#ifdef CGAL_CK_TEST_BBOX_BEFORE_HAS_ON
	  Bbox_2 rb = result->first.bbox();
	  if(do_overlap(a1.bbox(), rb) && do_overlap(a2.bbox(),rb)){
	    if (has_on<CK>(a1,result->first,true) && 
		has_on<CK>(a2,result->first,true)) {
	      *res++ = *it;
	    }
	  }
#else 
	  if (has_on<CK>(a1,result->first,true) && 
              has_on<CK>(a2,result->first,true)) {
            *res++ = *it;
          }
#endif
        }
      //return res;
      }
    }
    return res;
  }


  // !!!! a lot of useless assertions for debug
  /*template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Circular_arc_2 &a1,
	       const typename CK::Circular_arc_2 &a2,
	       OutputIterator res )
  {
    typedef typename CK::Circular_arc_point_2  Circular_arc_point_2;
    typedef typename CK::Circular_arc_2        Circular_arc_2;

    if (a1.is_x_monotone() && a2.is_x_monotone()) {
      // Overlapping curves.
      if ( (a1.supporting_circle() == a2.supporting_circle()) ||
	   (a1.supporting_circle() == a2.supporting_circle().opposite()) ) {
	// The ranges need to overlap in order for the curves to overlap.
	if ( CircularFunctors::compare_x<CK>(a1.left(), a2.right()) > 0 ||
	    CircularFunctors::compare_x<CK>(a2.left(), a1.right()) > 0)
	  return res;
	  
	// They both need to be on the same upper/lower part.
	if (a1.on_upper_part() != a2.on_upper_part()) {
	  // But they could share the left vertical tangent point.
	  if (a1.left() == a2.left())
	    *res++ = make_object(std::make_pair(a1.left(),1u));
	  // Or they could share the right vertical tangent point.
	  if (a1.right() == a2.right())
	    *res++ = make_object(std::make_pair(a1.right(),1u));
	  return res;
	}
	
	// We know they overlap, determine the extremities of 
	// the common subcurve
	// TODO : We should use std::max and std::min, but they 
	// require less_x_2.
	const Circular_arc_2 & arctmp = 
	  CircularFunctors::compare_x<CK>(a1.right(), a2.right()) < 0 ? a1 : a2;
	// we know that the right endpoint is correct, let us look for
	// the left now:
	
	
	//? a1.left() : a2.left();
	if (CircularFunctors::compare_x<CK>(a1.left(), a2.left()) > 0) {
	  //the left endpoint is a1's
	  if (CircularFunctors::compare_x<CK>(a1.left(), a2.right()) < 0){
	    if (a1.on_upper_part()) {
	      const Circular_arc_2 & arc =
		Circular_arc_2(a1.supporting_circle(),a2.right(),a1.left());
	      CGAL_kernel_assertion(arc.is_x_monotone());
	      *res++ = make_object(arc);
	    }
	    else {
	      const Circular_arc_2 & arc =
		Circular_arc_2(a1.supporting_circle(),a1.left(), a2.right());
	      CGAL_kernel_assertion(arc.is_x_monotone());
	      *res++ = make_object(arc);
	    }
	  }
	  else
	    *res++ = make_object(std::make_pair(arctmp.right(),1u));
	}
	else if( CircularFunctors::compare_x<CK>(a1.left(), a2.left()) < 0 ) {
	  //the left endpoint is a2's
	  if(CircularFunctors::compare_x<CK>(a1.right(), a2.left()) > 0) {
	    if(a1.on_upper_part()){
	      const Circular_arc_2 & arc =
		Circular_arc_2(a1.supporting_circle(), a1.right(), a2.left());
	      CGAL_kernel_assertion(arc.is_x_monotone());
	      *res++ = make_object(arc);
	    }
	    else {
	      const Circular_arc_2 & arc =
		Circular_arc_2(a1.supporting_circle(), a2.left(), a1.right());
	      CGAL_kernel_assertion(arc.is_x_monotone());
	      *res++ = make_object(arc);
	    }
	  }
	  else
	    *res++ = make_object(std::make_pair(arctmp.right(),1u));
	}
	else {
	  if(CircularFunctors::compare_x<CK>(a1.right(), a2.right()) >= 0)
	    *res++ = make_object(a2);
	  else if(CircularFunctors::compare_x<CK>(a1.right(), a2.right()) < 0)
	    *res++ = make_object(a1);
	  else
	    *res++ = make_object(std::make_pair(arctmp.right(),1u));
	}
	return res;
      }

//      // We need to check that the supporting circles
//      // do intersect before going further.
//      if (! do_intersect(a1.supporting_circle(), a2.supporting_circle())) 
//	{ return res; }
//      
//      // Get the two intersection points of the supporting circles.
//      
//      std::vector<CGAL::Object > intersection_points;
//      CGAL::intersect_2<CK>
//	( a1.supporting_circle(), a2.supporting_circle(),
//	  std::back_inserter(intersection_points) );
      
      std::vector<CGAL::Object > intersection_points;
      CGAL::intersect_2<CK> ( a1.supporting_circle(), a2.supporting_circle(),
			      std::back_inserter(intersection_points) );
      if(intersection_points.size() == 0) return res;

      const Circular_arc_point_2 &left =
	(CGAL::object_cast< std::pair<Circular_arc_point_2, unsigned> >
	 (&(intersection_points[0])))->first;
      if (intersection_points.size() < 2){// multiplicity 2
	if (CircularFunctors::has_on<CK>(a1, left) && CircularFunctors::has_on<CK>(a2, left)) 
	  *res++ = make_object(std::make_pair(left,2u));
      }
      else {// multiplicity 1
	const Circular_arc_point_2 &right = 
	  (CGAL::object_cast< std::pair<Circular_arc_point_2, unsigned> >
	   (&(intersection_points[1])))->first;
	// We also need to check that these intersection points are on the arc.
	if (CircularFunctors::has_on<CK>(a1, left) && CircularFunctors::has_on<CK>(a2, left))
	  *res++ = make_object(std::make_pair(left,1u));
	if (CircularFunctors::has_on<CK>(a1, right) && CircularFunctors::has_on<CK>(a2, right))
	  *res++ = make_object(std::make_pair(right,1u));
      }
      return res;
    }
    else {//a1 or a2 are not x_monotone
      std::vector< CGAL::Object > arcs_a1_x_monotone;
      make_x_monotone( a1, std::back_inserter(arcs_a1_x_monotone));
      std::vector< CGAL::Object > arcs_a2_x_monotone;
      make_x_monotone( a2, std::back_inserter(arcs_a2_x_monotone));
      std::vector< Circular_arc_2 > circle_arcs;
      std::vector< Circular_arc_point_2 > circle_arc_endpoints;
      
      for ( std::vector< CGAL::Object >::iterator it1 = 
	      arcs_a1_x_monotone.begin(); 
	    it1 != arcs_a1_x_monotone.end(); ++it1 ) {
	//CGAL_kernel_assertion(assign( a1_aux, *it1));
	const Circular_arc_2 *a1_aux = 
	  CGAL::object_cast< Circular_arc_2 >(&*it1);

	for ( std::vector< CGAL::Object >::iterator it2 = 
		arcs_a2_x_monotone.begin(); 
	      it2 != arcs_a2_x_monotone.end(); ++it2 ) {
	  //CGAL_kernel_assertion(assign( a2_aux, *it2));
	  //assign( a2_aux, *it2);
	  const Circular_arc_2 *a2_aux = 
	    CGAL::object_cast<Circular_arc_2>(&*it2);
	  std::vector< CGAL::Object > res_aux;
	  CircularFunctors::intersect_2<CK>( *a1_aux, *a2_aux, std::back_inserter(res_aux));
	  if(res_aux.size() == 2){
	    //it can't be a circular_arc_2
	    //CGAL_kernel_assertion(assign(the_pair, res_aux[0]));
	    const std::pair<Circular_arc_point_2, unsigned int> *the_pair1 = 
	      CGAL::object_cast<std::pair<Circular_arc_point_2, unsigned int> >
	      (&res_aux[0]);
	    Circular_arc_point_2 arc_end1 = the_pair1->first;
	    //assign(the_pair, res_aux[1]);
	    const std::pair<Circular_arc_point_2, unsigned int> *the_pair2 = 
	      CGAL::object_cast<std::pair<Circular_arc_point_2, unsigned int> >
	      (&res_aux[1]);
	    Circular_arc_point_2 arc_end2 = the_pair2->first;
	    bool exist = false;
	    for (typename std::vector< Circular_arc_point_2 >::iterator it 
		   = circle_arc_endpoints.begin(); 
		 it != circle_arc_endpoints.end(); ++it ) {
	      if (arc_end1 == *it) {
		exist = true;
		break;
	      }
	    }
	    if (!exist) {
	      circle_arc_endpoints.push_back(arc_end1);
	    }
	    else exist = false;
	    for ( typename std::vector< Circular_arc_point_2 >::iterator it
		    = circle_arc_endpoints.begin(); 
		  it != circle_arc_endpoints.end(); ++it ) {
	      if (arc_end2 == *it) {
		exist = true;
		break;
	      }
	    }
	    if (!exist)
	      circle_arc_endpoints.push_back(arc_end2);
	  }
	  else if( res_aux.size() == 1){
	    //it can be a Circular_arc_point_2 or a Circular_arc_2
	    if(const Circular_arc_2 *arc = 
	       CGAL::object_cast<Circular_arc_2>(&res_aux[0])) {
	      //if(assign(arc,res_aux[0])){
	      circle_arcs.push_back(*arc);
	    }
	    else {
	      //CGAL_kernel_assertion(assign(the_pair, res_aux[0]));
	      //assign(the_pair, res_aux[0]);
	      const std::pair<Circular_arc_point_2, unsigned int> *the_pair = 
		CGAL::object_cast<std::pair<Circular_arc_point_2, unsigned int> >
		(&res_aux[0]);
	      Circular_arc_point_2 arc_end = the_pair->first;
	      if (the_pair->second == 2u) {//there are only one tangent point
		*res++ = res_aux[0];
		return res;
	      }
	      bool exist = false;
	      for (typename std::vector< Circular_arc_point_2 >::iterator it 
		     = circle_arc_endpoints.begin(); 
		   it != circle_arc_endpoints.end(); ++it ) {
		if (arc_end == *it) {
		  exist = true;
		  break;
		}
	      }
	      if (!exist)
		circle_arc_endpoints.push_back(arc_end);
	    }
	  }
	}
      }
      //there are not double
      if (circle_arcs.size() > 0){
	std::size_t i = 1;
	while((i < circle_arcs.size()) && 
	      (circle_arcs[i-1].target().x() == circle_arcs[i].source().x()) &&
	      (circle_arcs[i-1].target().y() == circle_arcs[i].source().y())
	      ) 
	  {i++;}

	*res++ = make_object
	  (Circular_arc_2(circle_arcs[0].supporting_circle(),
			  circle_arcs[0].source(),
			  circle_arcs[i-1].target()
			  ));
	if (i < circle_arcs.size()) {//there are 2 circle arcs
	  std::size_t j = i;
	  i++;
	  while((i < circle_arcs.size()) 
		&& (circle_arcs[i-1].target() == circle_arcs[i].source()))
	    i++;
	  *res++ = make_object
	    (Circular_arc_2(circle_arcs[j].supporting_circle(),
			    circle_arcs[j].source(),
			    circle_arcs[i-1].target()
			    ));
	  return res;
	}
	else {//There are one circle arc and there can be maximum one endpoint
	  for (typename std::vector< Circular_arc_point_2 >::iterator it1 
		 = circle_arc_endpoints.begin(); 
	       it1 != circle_arc_endpoints.end(); ++it1 ) {
	    bool other_point = true;
	    for (typename std::vector< Circular_arc_2 >::iterator it2 
		   = circle_arcs.begin(); 
		 it2 != circle_arcs.end(); ++it2 )
	      {
		if (CircularFunctors::has_on<CK>(*it2, *it1)) {
		  other_point = false;
		  break;
		}
	      }
	    if (other_point) {
	      *res++ = make_object(std::make_pair(*it1,1u));
	      break;
	    }
	  }
	  return res;
	}
      }
      else{//there are one or two endpoint
	if (circle_arc_endpoints.size() > 1){
	  *res++ = make_object(std::make_pair(circle_arc_endpoints[0],1u));
	  *res++ = make_object(std::make_pair(circle_arc_endpoints[1],1u));
	}
	else if (circle_arc_endpoints.size() == 1) 
	  *res++ = make_object(std::make_pair(circle_arc_endpoints[0],1u));
	return res;
      }
    }
  }*/

  template < class CK >
  bool
  is_vertical(const typename CK::Circular_arc_2 &)
  {
    return false; 
  }

template < class CK, class OutputIterator >
  OutputIterator
  make_x_monotone( const typename CK::Circular_arc_2 &A,
		   OutputIterator res )
  {
    typedef typename CK::Circular_arc_2           Circular_arc_2;
    typedef typename CK::Circle_2                 Circle_2;
    typedef typename CK::FT                       FT;
    typedef typename CK::Point_2                  Point_2;
    typedef typename CK::Circular_arc_point_2     Circular_arc_point_2;
    typedef typename CK::Root_for_circles_2_2     Root_for_circles_2_2;

    CGAL_kernel_precondition(A.supporting_circle().squared_radius() != 0);

    if (A.is_x_monotone()) {

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
      // get a number for its supporting circle
      A.circle_number(); 
#endif

      *res++ = make_object(A);
      return res; 
    }

    std::vector< Root_for_circles_2_2 > vector_x_extremal_points;
    CircularFunctors::x_extremal_points<CK>(A.supporting_circle(), 
			  std::back_inserter(vector_x_extremal_points));
    Circular_arc_point_2 x_extremal_point1 = vector_x_extremal_points[0];
    Circular_arc_point_2 x_extremal_point2 = vector_x_extremal_points[1];

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    std::vector < CGAL::Object > intersecs1;
    std::vector < CGAL::Object > intersecs2;
    std::vector < CGAL::Object > intersecs3;
#endif

    if (A.is_full()) {
      const Circular_arc_2 &ca1 = Circular_arc_2(A.supporting_circle(), 
                                           x_extremal_point1,