internal_functions_on_circular_arc_2.h

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

//     return equal<CK>( A1.source(), A2.source() ) 
//         && equal<CK>( A1.target(), A2.target() );
//   }

  // Small accessory function
  // Tests whether a given point is on an arc, with the precondition that
  // it's (symbolically) on the supporting circle.
  /*template < class CK >
  bool
  has_on(const typename CK::Circular_arc_2 &a,
	 const typename CK::Circular_arc_point_2 &p,
         const bool has_on_supporting_circle = false)
  {
    CGAL_kernel_precondition(a.is_x_monotone());
    
//     typedef typename CK::Polynomial_for_circles_2_2 Polynomial_for_circles_2_2;
//     Polynomial_for_circles_2_2 
//       equation = get_equation<CK>(a.supporting_circle());
    
//     if(CGAL::sign_at<typename CK::Algebraic_kernel>
//        (equation,p.coordinates())!= ZERO)
//       return false;
    if(!has_on_supporting_circle) {
      if ( ! CircularFunctors::has_on<CK>(a.supporting_circle(),p) ) 
        return false;
    }
    
    if (! CircularFunctors::point_in_x_range<CK>(a, p) )
      return false;
    
    int cmp = CGAL::compare(p.y(), a.supporting_circle().center().y());

    return  cmp == 0 || (cmp > 0 &&  a.on_upper_part())
                     || (cmp < 0 && !a.on_upper_part());
  }*/

  template < class CK >
  bool
  has_on(const typename CK::Circular_arc_2 &a,
	 const typename CK::Circular_arc_point_2 &p,
         const bool has_on_supporting_circle = false)
  {
    if( (p.equal_ref(a.source())) || (p.equal_ref(a.source()))) {
      return true;
    }

    if(!has_on_supporting_circle) {
      if ( ! CircularFunctors::has_on<CK>(a.supporting_circle(),p) ) 
        return false;
    }

    if(a.is_full()) return true;
    
    if(a.is_x_monotone()) {
      int cmp_ps = CircularFunctors::compare_x<CK>(p,a.source());
      int cmp_pt = CircularFunctors::compare_x<CK>(p,a.target());
      if(cmp_ps == cmp_pt) return false;
      int cmp = CGAL::compare(p.y(), a.supporting_circle().center().y());
      return  cmp == 0 || (cmp > 0 &&  a.on_upper_part())
                       || (cmp < 0 && !a.on_upper_part());
    } else if(a.is_complementary_x_monotone())  {
      int cmp_ps = CircularFunctors::compare_x<CK>(p,a.source());
      int cmp_pt = CircularFunctors::compare_x<CK>(p,a.target());
      if(cmp_ps == cmp_pt) return true;
      if((!cmp_ps) || (!cmp_pt)) return true;
      int cmp = CGAL::compare(p.y(), a.supporting_circle().center().y());
      return  cmp == 0 || (cmp < 0 &&  a.complementary_on_upper_part())
                     || (cmp > 0 && !a.complementary_on_upper_part());
    } else if(a.is_y_monotone()) {
      int cmp_ps = CircularFunctors::compare_y<CK>(p,a.source());
      int cmp_pt = CircularFunctors::compare_y<CK>(p,a.target());
      if(cmp_ps == cmp_pt) return false;
      int cmp = CGAL::compare(p.x(), a.supporting_circle().center().x());
      return  cmp == 0 || (cmp < 0 &&  a.on_left_part())
                       || (cmp > 0 && !a.on_left_part());
    } else if(a.is_complementary_y_monotone()) {      
      int cmp_ps = CircularFunctors::compare_y<CK>(p,a.source());
      int cmp_pt = CircularFunctors::compare_y<CK>(p,a.target());
      if(cmp_ps == cmp_pt) return true;
      if((!cmp_ps) || (!cmp_pt)) return true;       
      int cmp = CGAL::compare(p.x(), a.supporting_circle().center().x());
      return  cmp == 0 || (cmp > 0 && a.complementary_on_left_part())
                     || (cmp < 0 && !a.complementary_on_left_part());
    } else {
      int cmp_scy = CGAL::compare(a.source().y(), a.supporting_circle().center().y());
      int cmp = CGAL::compare(p.y(), a.supporting_circle().center().y());
      if(cmp_scy < 0) {
        if(cmp > 0) return CGAL::compare(p.x(), a.target().x()) >= 0;
        else return CGAL::compare(p.x(), a.source().x()) >= 0;
      } else {
        if(cmp > 0) return CGAL::compare(p.x(), a.source().x()) <= 0;
        else return CGAL::compare(p.x(), a.target().x()) <= 0; 
      }
    }
  }

  template < class CK >
  bool
  do_overlap(const typename CK::Circular_arc_2 &A1,
	     const typename CK::Circular_arc_2 &A2)
  {
    //CGAL_kernel_precondition (A1.is_x_monotone());
    //CGAL_kernel_precondition (A2.is_x_monotone());

    /*if ( (A1.supporting_circle() != A2.supporting_circle()) &&
	 (A1.supporting_circle() != A2.supporting_circle().opposite()) )
      return false;*/
    if(!CircularFunctors::non_oriented_equal<CK>(
      A1.supporting_circle(), A2.supporting_circle()))
      return false;

    //if ( A1.on_upper_part() != A2.on_upper_part() ) return false;

    //return CircularFunctors::compare_x<CK>(A1.right(), A2.left()) > 0
    //    && CircularFunctors::compare_x<CK>(A1.left(), A2.right()) < 0;
    if(A1.is_full()) return true;
    if(A2.is_full()) return true;
    if((has_on<CK>(A1,A2.target(),true)) || 
       (has_on<CK>(A1,A2.source(),true))) return true;
    return has_on<CK>(A2,A1.source(),true);
  }
  

  template < class CK >
  void
  split(const typename CK::Circular_arc_2 &A,
	const typename CK::Circular_arc_point_2 &p,
	typename CK::Circular_arc_2 &ca1,
	typename CK::Circular_arc_2 &ca2)
  {
    //CGAL_kernel_precondition( A.is_x_monotone() );
    //CGAL_kernel_precondition( CircularFunctors::point_in_x_range<CK>( A, p ) );
    //CGAL_kernel_precondition( A.on_upper_part() == (p.y() >
    //			      A.supporting_circle().center().y()) );
    //CGAL_kernel_precondition( CircularFunctors::has_on<CK>(A, p) );
   
    typedef typename CK::Circular_arc_2  Circular_arc_2;

    const Circular_arc_2 &rc1 = 
      Circular_arc_2( A.supporting_circle(), A.source(), p);
    const Circular_arc_2 &rc2 = 
      Circular_arc_2( A.supporting_circle(), p, A.target());

    if ( CircularFunctors::compare_x<CK>(rc1.source(), rc2.source()) != SMALLER) {
      ca1 = rc2;
      ca2 = rc1;
    } else {
      ca1 = rc1;
      ca2 = rc2;
    }
#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    std::vector < CGAL::Object > res;

    if(A.is_full()) {
      res.push_back(make_object(std::make_pair(ca1.source(),1u)));
      res.push_back(make_object(std::make_pair(ca2.source(),1u)));
    } else {
      res.push_back(make_object(std::make_pair(p,1u)));
    }

    Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
      (ca1,ca2,res);
#endif

    /*ca1 = Circular_arc_2( A.supporting_circle(), A.source(), p);
    ca2 = Circular_arc_2( A.supporting_circle(), p, A.target());
    //if ( ca1.right()!=ca2.left() )
    if ( CircularFunctors::compare_x<CK>(ca1.left(), ca2.left()) != SMALLER )
      {
	//std::cout << " SWAP " << std::endl;
	std::swap(ca1,ca2);
      }*/
  }

  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 std::vector<CGAL::Object> solutions_container; 
    typedef typename CK::Circular_arc_2 Circular_arc_2; 
    typedef typename CK::Circular_arc_point_2 Circular_arc_point_2; 

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    // same curve
    if(a1.number() == a2.number()) {
      *res++ = make_object(a1); 
       return res;
    }

    // intersection found on the map
    solutions_container early_sols;
    if(Circular_arc_2::template find_intersection< solutions_container >
      (a1,a2,early_sols)) {
      for (typename solutions_container::iterator it = early_sols.begin(); 
	 it != early_sols.end(); ++it) {
        *res++ = *it;
      }
      return res;
    }
#endif

#ifdef  CGAL_CK_EXPLOIT_IDENTITY
    bool a1s_a2s = a1.source().equal_ref(a2.source());
    bool a1s_a2t = a1.source().equal_ref(a2.target());
    bool a1t_a2s = a1.target().equal_ref(a2.source());
    bool a1t_a2t = a1.target().equal_ref(a2.target());
    
    if((a1s_a2s && a1t_a2t) || (a1s_a2t && a1t_a2s)){ // Case 1
      if( (a1.supporting_circle() == a2.supporting_circle()) && ((a1.on_upper_part() && a2.on_upper_part())|| (! a1.on_upper_part() && (! a2.on_upper_part())))){ 
	*res++ = make_object(a1);
      } else {
	if(compare_x<CK>(a1.source(), a1.target()) == SMALLER){
	  *res++ = make_object(std::make_pair(a1.source(),1u));
	  *res++ = make_object(std::make_pair(a1.target(),1u));
	} else {	  
	  *res++ = make_object(std::make_pair(a1.target(),1u));
	  *res++ = make_object(std::make_pair(a1.source(),1u));
	}
      }
      return res;
    } else if (a1s_a2s || a1t_a2t || a1s_a2t || a1t_a2s) {
      Circular_arc_point_2 p,q,r;
      
      // Make that q is the middle vertex
      if(a1s_a2s){
	p = a1.target();
	q = a1.source();
	r = a2.target();
      } else if(a1s_a2t){
	p = a1.target();
	q = a1.source();
	r = a2.source();
      } else if(a1t_a2s){
	p = a1.source();
	q = a1.target();
	r = a2.target();
      } else { // a1t_a2t
	p = a1.source();
	q = a1.target();
	r = a2.source();
      }

      bool return_q = false;
      if(CircularFunctors::compare_x<CK>(r,q) == LARGER){
	if (CircularFunctors::point_in_x_range<CK>(p,r,q)){ // Case 2
	  return_q = true;
	}  else if (((a1.on_upper_part() && ! a2.on_upper_part()) && CircularFunctors::compare_y_to_right<CK>(a1,a2,q) == SMALLER)
		    || ((! a1.on_upper_part() && a2.on_upper_part()) && CircularFunctors::compare_y_to_right<CK>(a1,a2,q) == LARGER)){
	  return_q = true;
	} else if ((a1.on_upper_part() && ! a2.on_upper_part()) && CircularFunctors::compare_y_to_right<CK>(a1,a2,q)==LARGER){
	  typename CK::Linear_kernel::Bounded_side p_a2_bs = CircularFunctors::bounded_side<CK>(a2.supporting_circle(),p);
	  typename CK::Linear_kernel::Bounded_side r_a1_bs = CircularFunctors::bounded_side<CK>(a1.supporting_circle(),r);
	  if(p_a2_bs || r_a1_bs){
	    return_q = true;
	  } else {
	  }
	}
      } else {
	// TODO: treat the cases where the common endpoint is on the right
      }
	
      if(return_q){

	*res++ = make_object(std::make_pair(q,1u));
	return res;
      }

    }
#endif // CGAL_CK_EXPLOIT_IDENTITY

    const bool sqr1_eq_sqr2 = (a1.squared_radius() == a2.squared_radius());  
    const bool c1_eq_c2 = (a1.center() == a2.center());  

    if(sqr1_eq_sqr2 && c1_eq_c2) {
      if(a1.is_full()) {
        *res++ = make_object(a2); 
        //return res;
      }
      else if(a2.is_full()) {
        *res++ = make_object(a1); 
        //return res;
      } else {
        bool t2_in_a1 = has_on<CK>(a1,a2.target(),true);
        bool s2_in_a1 = has_on<CK>(a1,a2.source(),true);      
        if(t2_in_a1 && s2_in_a1) {
          bool t1_in_a2 = has_on<CK>(a2,a1.target(),true);
          bool s1_in_a2 = has_on<CK>(a2,a1.source(),true);
          if(t1_in_a2 && s1_in_a2) {
            const Comparison_result comp = 
              CircularFunctors::compare_xy<CK>(a1.source(), a2.source());
            if(comp < 0) {
              if(a1.source() == a2.target()) {
                *res++ = make_object(std::make_pair(a1.source(),1u));
              } else {
                const Circular_arc_2 & arc =
	        Circular_arc_2(a1.supporting_circle(),a1.source(),a2.target());
	        *res++ = make_object(arc);
              }
              if(a2.source() == a1.target()) {
                *res++ = make_object(std::make_pair(a2.source(),1u));
              } else {
                const Circular_arc_2 & arc =
	        Circular_arc_2(a1.supporting_circle(),a2.source(),a1.target());
	        *res++ = make_object(arc);
              }
            } else if (comp > 0) {
              if(a2.source() == a1.target()) {
                *res++ = make_object(std::make_pair(a2.source(),1u));
              } else {
                const Circular_arc_2 & arc =
	        Circular_arc_2(a1.supporting_circle(),a2.source(),a1.target());
	        *res++ = make_object(arc);
              }
              if(a1.source() == a2.target()) {
                *res++ = make_object(std::make_pair(a1.source(),1u));
              } else {
                const Circular_arc_2 & arc =
	        Circular_arc_2(a1.supporting_circle(),a1.source(),a2.target());
	        *res++ = make_object(arc);
              } 
            } else {
              *res++ = make_object(a1);
            } 
          } else {
            *res++ = make_object(a2);
          //return res;
          }
        }
        else if(t2_in_a1) {
          if(a1.source() == a2.target()) 
            *res++ = make_object(std::make_pair(a1.source(),1u));
          else {
            const Circular_arc_2 & arc =
	      Circular_arc_2(a1.supporting_circle(),a1.source(),a2.target());
	    *res++ = make_object(arc);
          } //return res;
        } else if(s2_in_a1) {
          if(a2.source() == a1.target()) {
            *res++ = make_object(std::make_pair(a2.source(),1u));
          } else {
            const Circular_arc_2 & arc =
	      Circular_arc_2(a1.supporting_circle(),a2.source(),a1.target());
	    *res++ = make_object(arc);
          } //return res;
        } else if(has_on<CK>(a2,a1.source(),true)) {
          *res++ = make_object(a1);
        //return res;
        } 
      //return res;
      }
    } else if(!c1_eq_c2) {
      solutions_container solutions;

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
      if(!Circular_arc_2::template 
         find_intersection_circle_circle< solutions_container > 
         (a1,a2,solutions)) {
#endif

      CGAL::intersect_2<CK> ( a1.supporting_circle(), a2.supporting_circle(),
        std::back_inserter(solutions) );