internal_functions_on_circular_arc_2.h

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

					   x_extremal_point2);
      const Circular_arc_2 &ca2 = Circular_arc_2(A.supporting_circle(), 
                                           x_extremal_point2,
					   x_extremal_point1);
      ca1._setx_info(2,1,0); //setting flags outside
      ca2._setx_info(2,2,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
      // get a number for its supporting circle
      unsigned int cn = ca1.circle_number(); 
      ca2.set_circle_number(cn);
#endif

      *res++ = make_object(ca1);
      *res++ = make_object(ca2);

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
      intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
      intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
      Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
        (ca1,ca2,intersecs1);
#endif

      return res;
    }

    int cmp_begin = CGAL::compare(A.source().y(), A.center().y());
    int cmp_end   = CGAL::compare(A.target().y(), A.center().y());
    
    // Define the 2 Circular_arc_endpoints 
    // in the 2 vertical tangent points
    
    
    if (cmp_begin > 0) {
      const Circular_arc_2 &ca1 = Circular_arc_2(A.supporting_circle(), 
                                                 A.source(), 
                                                 x_extremal_point1); 
      ca1._setx_info(2,2,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
      unsigned int cn = ca1.circle_number();
#endif

      *res++ = make_object(ca1);
      if (cmp_end > 0) {
        // We must cut in 3 parts.
        const Circular_arc_2 &ca2 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point1,
					           x_extremal_point2); 
        const Circular_arc_2 &ca3 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point2,
					           A.target()); 
        ca2._setx_info(2,1,0);
        ca3._setx_info(2,2,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        ca2.set_circle_number(cn); 
        ca3.set_circle_number(cn); 
#endif

        *res++ = make_object(ca2);
        *res++ = make_object(ca3);
#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        intersecs2.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca2,ca3,intersecs2);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca3,intersecs3); //empty - no intersection
#endif
      } 
      else {
        const Circular_arc_2 &ca2 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point1,
					           A.target()); 
        ca2._setx_info(2,1,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        ca2.set_circle_number(cn);
#endif

        *res++ = make_object(ca2);

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
#endif

      } 
    }
    else if (cmp_begin < 0) {
      const Circular_arc_2 &ca1 = Circular_arc_2(A.supporting_circle(), 
                                                 A.source(), 
                                                 x_extremal_point2); 
      ca1._setx_info(2,1,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
      unsigned int cn = ca1.circle_number();
#endif

      *res++ = make_object(ca1);
      if (cmp_end < 0) {
        const Circular_arc_2 &ca2 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point2,
					           x_extremal_point1); 
        const Circular_arc_2 &ca3 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point1,
					           A.target()); 
        ca2._setx_info(2,2,0);
        ca3._setx_info(2,1,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        ca2.set_circle_number(cn);
        ca3.set_circle_number(cn);
#endif

        *res++ = make_object(ca2);
        *res++ = make_object(ca3);

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        intersecs2.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca2,ca3,intersecs2);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca3,intersecs3);
#endif

      } 
      else {
        const Circular_arc_2 &ca2 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point2,
					           A.target()); 
        ca2._setx_info(2,2,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        ca2.set_circle_number(cn);
#endif

        *res++ = make_object(ca2);

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
#endif

      }
    }
    else { // cmp_begin == 0
      if (CGAL::compare(A.source().x(), A.center().x()) < 0) {
        CGAL_kernel_assertion (cmp_end >= 0);
        const Circular_arc_2 &ca1 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point1,
					           x_extremal_point2);
        const Circular_arc_2 &ca2 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point2,
					           A.target());
        ca1._setx_info(2,1,0);
        ca2._setx_info(2,2,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        unsigned int cn = ca1.circle_number();
        ca2.set_circle_number(cn);
#endif

        *res++ = make_object(ca1);
        *res++ = make_object(ca2);

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
#endif

      }
      else {
        CGAL_kernel_assertion 
	  (CGAL::compare(A.source().x(), A.center().x()) > 0);
        CGAL_kernel_assertion (cmp_end != LARGER);
        const Circular_arc_2 &ca1 = Circular_arc_2(A.supporting_circle(), 
                                                   x_extremal_point2,
					           x_extremal_point1);
        const Circular_arc_2 &ca2 = Circular_arc_2(A.supporting_circle(), 
                                            x_extremal_point1,
					    A.target());
        ca1._setx_info(2,2,0);
        ca2._setx_info(2,1,0);

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        unsigned int cn = ca1.circle_number();
        ca2.set_circle_number(cn);
#endif

        *res++ = make_object(ca1);
        *res++ = make_object(ca2);

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
#endif

      }
    }
    return res;
  }

  
 /* 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;

    if (A.is_x_monotone()) {
      *res++ = make_object(A);
      return res; 
    }
    
    // Define the 2 Circular_arc_endpoints 
    // in the 2 vertical tangent points
    
    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];

    std::vector < CGAL::Object > intersecs1;
    std::vector < CGAL::Object > intersecs2;
    std::vector < CGAL::Object > intersecs3;

    if (A.is_full()) {
      Circular_arc_2 ca1(A.supporting_circle(), x_extremal_point1,
					   x_extremal_point2);
      Circular_arc_2 ca2(A.supporting_circle(), x_extremal_point2,
					   x_extremal_point1);
      *res++ = make_object(ca1);
      *res++ = make_object(ca2);
      intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
      intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
      Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
        (ca1,ca2,intersecs1);
      return res;
    }

    int cmp_begin = CGAL::compare(A.source().y(), A.center().y());
    int cmp_end   = CGAL::compare(A.target().y(), A.center().y());

    if (cmp_begin > 0) {
      Circular_arc_2 ca1(A.supporting_circle(), A.source(), x_extremal_point1); 
      *res++ = make_object(ca1);
      if (cmp_end > 0) {
        // We must cut in 3 parts.
        Circular_arc_2 ca2(A.supporting_circle(), x_extremal_point1,
					    x_extremal_point2); 
        Circular_arc_2 ca3(A.supporting_circle(), x_extremal_point2,
					     A.target()); 
        *res++ = make_object(ca2);
        *res++ = make_object(ca3);
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        intersecs2.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca2,ca3,intersecs2);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca3,intersecs3); //empty - no intersection
      } 
      else {
        Circular_arc_2 ca2(A.supporting_circle(), x_extremal_point1,
					    A.target()); 
        *res++ = make_object(ca2);
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
      }
    }
    else if (cmp_begin < 0) {
      // Very similar to the previous case.
      Circular_arc_2 ca1(A.supporting_circle(), A.source(), x_extremal_point2); 
      *res++ = make_object(ca1);
      if (cmp_end > 0) {
        // We must cut in 3 parts.
        Circular_arc_2 ca2(A.supporting_circle(), x_extremal_point2,
					    x_extremal_point1); 
        Circular_arc_2 ca3(A.supporting_circle(), x_extremal_point1,
					     A.target()); 
        *res++ = make_object(ca2);
        *res++ = make_object(ca3);
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        intersecs2.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca2,ca3,intersecs2);
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca3,intersecs3); //empty - no intersection
      } 
      else {
        Circular_arc_2 ca2(A.supporting_circle(), x_extremal_point2,
					    A.target()); 
        *res++ = make_object(ca2);
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
      }
    }
    else { // cmp_begin == 0
      if (CGAL::compare(A.source().x(), A.center().x()) < 0) {
        CGAL_kernel_assertion (cmp_end >= 0);
        Circular_arc_2 ca1(A.supporting_circle(), x_extremal_point1,
					    x_extremal_point2);
        Circular_arc_2 ca2(A.supporting_circle(), x_extremal_point2,
					    A.target());
        *res++ = make_object(ca1);
        *res++ = make_object(ca2);
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point2,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
      }
      else {
        CGAL_kernel_assertion 
	  (CGAL::compare(A.source().x(), A.center().x()) > 0);
        CGAL_kernel_assertion (cmp_end != LARGER);
        Circular_arc_2 ca1(A.supporting_circle(), x_extremal_point2,
					    x_extremal_point1);
        Circular_arc_2 ca2(A.supporting_circle(), x_extremal_point1,
					    A.target());
        *res++ = make_object(ca1);
        *res++ = make_object(ca2);
        intersecs1.push_back(make_object(std::make_pair(x_extremal_point1,1u)));
        Circular_arc_2::template put_intersection< std::vector < CGAL::Object > >
          (ca1,ca2,intersecs1);
      }
    }
    return res;
  }*/

  
  
  
// This is the make_x_monotone function returning extra information: 
// The ouput iterator refers to pairs, the first part of which is an
// object containing the x-monotone arc and the second part is a 
// boolean defining whether the arc is on the upper part of the 
// circle or not. This extra information returned by make_x_monotone
// and make_xy_monotone helps us to avoid doing twice the same 
// comparisons by the functions which call these two in order to define
// the position of the returned arcs on the circle , like in the 
// construct_bounding_hexagons function

  template < class CK, class OutputIterator >