internal_functions_on_circular_arc_2.h

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

  OutputIterator
  advanced_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 std::pair<CGAL::Object,bool >         S_pair;


    int cmp_begin_y = CGAL::compare
      (A.source().y(), A.supporting_circle().center().y());
    int cmp_end_y   = CGAL::compare
      (A.target().y(), A.supporting_circle().center().y());
    
    int cmp_x=compare_x(A.source(),A.target());
    
    // We don't need to split
    if (cmp_begin_y != opposite(cmp_end_y) &&
        (((cmp_begin_y > 0 || cmp_end_y > 0) && cmp_x > 0) ||
	 (cmp_begin_y < 0 || cmp_end_y < 0) && cmp_x < 0) ) {
      
      *res++ = S_pair(make_object(A),(cmp_begin_y>0 || cmp_end_y>0) );
      return res; 
    }
    
    // Half circles
    if (cmp_begin_y == 0 && cmp_end_y == 0 && cmp_x != 0) {
      *res++ = std::make_pair(make_object(A), cmp_x>0 );
      return res; 
    }

    // We need to split
    //assert(!A.is_x_monotone());
    if (cmp_begin_y > 0) {
    
      *res++ = S_pair
	(make_object(Circular_arc_2(A.supporting_circle(), A.source(),
				    CircularFunctors::x_extremal_point<CK>
				    (A.supporting_circle(),true))),
	 true);
			       
      if (cmp_end_y > 0) {
        // We must cut in 3 parts.
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),true),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),false))),
	   false);
			
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),false),
				       A.target())),
	   true);
      } else {    
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),true),
				       A.target())), 
	   false);
      }
    }
    else if (cmp_begin_y < 0) {
      // Very similar to the previous case.
      *res++ = std::make_pair
	(make_object(Circular_arc_2 (A.supporting_circle(),
				     A.source(),
				     CircularFunctors::x_extremal_point<CK>
				     (A.supporting_circle(),false))),
	 false);
			 
      if (cmp_end_y < CGAL::EQUAL) {
        // We must cut in 3 parts.
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),false), 
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),true))) ,
	   true );
				     					     
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),true),
				       A.target())),
	   false);
      } else {
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),false),
				       A.target())),
	   true);
      }
    }
    else { // cmp_begin_y == 0
      if ( compare(A.source().x(),A.supporting_circle().center().x())< 0) {
        assert (cmp_end_y >= 0);
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       A.source(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),false))),
	   false);
	
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),false),
				       A.target())),
	   true);
      }
      else {
        assert( compare(A.source().x(),A.supporting_circle().center().x())< 0);
        assert (cmp_end_y != LARGER);
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       A.source(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),true))),
	   true);		   
			   
        *res++ = std::make_pair
	  (make_object(Circular_arc_2 (A.supporting_circle(),
				       CircularFunctors::x_extremal_point<CK>
				       (A.supporting_circle(),true),
				       A.target())),
	   false);
      }
    }

    return res;
  }

/////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////


// In the same as the advanced_make_x_monotone works, this make_xy_function
// returns extra information, descriptive of the position of the returned 
// xy-monotone arcs on the circle: The output iterator refers to pairs, the 
// first part of which is the object containing tha arc and the second part
// is another pair containing 2 booleans which equavalently describe whether the
// returned xy-monotone arc is on the upper part and the left side of the circle

template < typename CK , typename Output_iterator>
Output_iterator 
advanced_make_xy_monotone( const typename CK::Circular_arc_2 &a, 
			   Output_iterator res)
{
  
  typedef typename CK::Circular_arc_2            Circular_arc_2;
  typedef std::pair<bool, bool>                  relat_pos;
  typedef std::pair< CGAL::Object, bool>         Obj_descr_1;
  typedef std::pair< CGAL::Object, relat_pos>    Obj_descr_2;
  typedef std::vector<Obj_descr_1>               Obj_vector_1;
  typedef std::vector<Obj_descr_2>               Obj_vector_2;
  
  Obj_vector_1 vec;
  Obj_vector_2 vec2;
  Obj_descr_2  dscr2;
  
  advanced_make_x_monotone<CK>(a,std::back_inserter(vec));
  
  for(unsigned int i=0;i<vec.size();i++) {
    const Circular_arc_2 *tmp_arc =
      CGAL::object_cast<Circular_arc_2>(&vec.at(i).first);
    
    int cmp_begin_x = CGAL::compare
      (tmp_arc->source().x(), tmp_arc->supporting_circle().center().x());
    int cmp_end_x   = CGAL::compare
      (tmp_arc->target().x(), tmp_arc->supporting_circle().center().x());
		
    if(cmp_begin_x!=opposite(cmp_end_x) || cmp_begin_x==CGAL::EQUAL) {
      dscr2.first=vec.at(i).first;
      dscr2.second.first=vec.at(i).second;
      dscr2.second.second= (cmp_begin_x==CGAL::SMALLER ||
			    cmp_end_x==CGAL::SMALLER   ) ? 
	true : false;
      *res++=dscr2; // The arc is xy_monotone
    }	   
    else{ //We have to split the x_monotone_arc into 2 y_monotone arcs
		
      Obj_descr_1 tmp=vec.at(i);
      Obj_descr_2 tmp1,tmp2;
      const Circular_arc_2 *tmp_arc =
	CGAL::object_cast<Circular_arc_2>(&tmp.first);
					 			 
      tmp1.first = make_object
	(Circular_arc_2(a.supporting_circle(),tmp_arc->source(),
			CircularFunctors::y_extremal_point<CK>
			(a.supporting_circle(),!tmp.second)));
			    	    
      tmp1.second.first=tmp.second;
      tmp1.second.second= (tmp.second)? false : true ;
		
      tmp2.first = make_object
	(Circular_arc_2(a.supporting_circle(),
			CircularFunctors::y_extremal_point<CK>
			(a.supporting_circle(),!tmp.second),
			tmp_arc->target()));
      
      tmp2.second.first=tmp.second;
      tmp2.second.second= (tmp.second)? true  : false ;
      
      *res++=tmp1;
      *res++=tmp2;
    }
    
  }
  
  return res;
	
}	
	
  template <class CK>
  CGAL::Bbox_2 circular_arc_bbox
  ( const typename CK::Kernel_base::Circular_arc_2 & a)
  {	
    typedef typename CK::Root_of_2 	   Root_of_2;
    typedef typename CK::FT 		   FT;
    typedef CGAL::Interval_nt<false>::Protector IntervalProtector;
    typedef CGAL::Interval_nt<false> Interval; 

    if(a.is_x_monotone()) {
	// The arc is xy-monotone so we just add the bboxes of the endpoints
      if(a.is_y_monotone())
	return a.left().bbox() + a.right().bbox();
      
      // Just x-monotone, so we have to find the y-critical point
      
      bool is_on_upper = a.on_upper_part();
      
      Bbox_2 
	left_bb  = a.left().bbox(), 
	right_bb = a.right().bbox();

      IntervalProtector ip;
      Interval cy = to_interval(a.center().y());
      Interval r2 = to_interval(a.squared_radius());
      Interval r = CGAL::sqrt(r2);

      double ymin, ymax;

      if(is_on_upper) {
        ymin = (CGAL::min)(left_bb.ymin(),right_bb.ymin());
        ymax = cy.sup() + r.sup();
      } else {
        ymin = cy.inf() - r.sup();
        ymax = (CGAL::max)(left_bb.ymax(),right_bb.ymax());
      }
      /*
      double ymin = (is_on_upper) ? 
	(CGAL::min)(left_bb.ymin(),right_bb.ymin()) :
	to_interval
	( CircularFunctors::y_extremal_point<CK>(a.supporting_circle(),true).y()).first;
      double ymax = (is_on_upper) ? 
	to_interval
	( CircularFunctors::y_extremal_point<CK>(a.supporting_circle(),false).y() ).second :
	CGAL::max(left_bb.ymax(),right_bb.ymax()); 
      */
      return Bbox_2(left_bb.xmin(),ymin,right_bb.xmax(),ymax);
    }

    if(a.is_y_monotone()) {
      bool is_on_left = a.on_left_part();
      IntervalProtector ip;
      Bbox_2 
	    source_bb  = a.source().bbox(), 
	    target_bb = a.target().bbox();
      Interval cx = to_interval(a.center().x());
      Interval r2 = to_interval(a.squared_radius());
      Interval r = CGAL::sqrt(r2); 
      double xmin, xmax;
      if(is_on_left) {
        xmax = (CGAL::max)(source_bb.xmax(), target_bb.xmax()); 
        xmin = cx.inf() - r.sup();
      } else {
        xmax = cx.sup() + r.sup();
        xmin = (CGAL::min)(source_bb.xmin(), target_bb.xmin()); 
      }
      return Bbox_2(xmin,
                    (CGAL::min)(source_bb.ymin(),target_bb.ymin()),
                    xmax,
                    (CGAL::max)(source_bb.ymax(),target_bb.ymax()));
    }
	
    // Else return the bounding box of the circle.
    return a.supporting_circle().bbox();
    /*  More precise version for non-x-monotone arcs.
	double xmin,xmax,ymin,ymax;
	
	// In this case, we can't avoid doing these heavy comparisons
	
	Comparison_result cmp_source_x=compare(a.source().x(),a.supporting_circle().center().x()),
	cmp_target_x=compare(a.target().x(),a.supporting_circle().center().x()),
	cmp_source_y=compare(a.source().y(),a.supporting_circle().center().y()),	
	cmp_target_y=compare(a.target().y(),a.supporting_circle().center().y());
	
	//Since it's not x-monotone, it must include at least one x-critical point
	
	if(cmp_source_y==cmp_target_y || cmp_source_y==0 || cmp_target_y==0)
	{
	if(cmp_source_x==cmp_target_x || cmp_source_x==0 || cmp_target_x==0)
	return a.supporting_circle().bbox();					
	
	xmin=to_interval( x_extremal_points<CK>(a.supporting_circle(),true).x() ).first;
	xmax=to_interval( x_extremal_points<CK>(a.supporting_circle(),false).x() ).second;
	
	if( cmp_source_y==LARGER || cmp_target_y==LARGER)
	{
	ymin=to_interval( y_extremal_point<CK>(a.supporting_circle(),true).y() ).first;
	ymax=(CGAL::max)(to_interval(a.source().y()).second,to_interval(a.target().y()).second);
	}
	else{
	ymax=to_interval( y_extremal_point<CK>(a.supporting_circle(),false).y() ).second;
	ymin=(CGAL::min)(to_interval(a.source().y()).first,to_interval(a.target().y()).first);
	}
	
	return Bbox_2(xmin,ymin,xmax,ymax);
	}
	
	if(cmp_source_y > EQUAL)
	{
	xmin=to_interval(x_extremal_points<CK>(a.supporting_circle(),true).x()).first;
	xmax=(CGAL::max)(to_interval(a.source().x()).second,to_interval(a.target().x()).second);
	}
	else
	{
	xmin=(CGAL::min)(to_interval(a.source().x()).first,to_interval(a.target().x()).first);
	xmax=to_interval(x_extremal_points<CK>(a.supporting_circle(),false).x()).second;
	}
	
	
	if( ( cmp_source_y== LARGER && cmp_source_x>= EQUAL) ||		
	( cmp_target_y== LARGER && cmp_target_x<= EQUAL) )
	ymax=to_interval(y_extremal_point<CK>(a.supporting_circle(),false).y()).second;
	else
	ymax=(CGAL::max)(to_interval(a.source().y()).second,to_interval(a.target().y()).second);
	
	
	if( ( cmp_source_y== SMALLER && cmp_source_x<= EQUAL) ||		
	( cmp_target_y== SMALLER && cmp_target_x>= EQUAL) )
	ymin=to_interval(y_extremal_point<CK>(a.supporting_circle(),true).y()).first;
	else
	ymin=(CGAL::min)(to_interval(a.source().y()).first,to_interval(a.target().y()).first);
	
	return Bbox_2(xmin,ymin,xmax,ymax);
    */
  }
  
} // namespace CircularFunctors 
} // namespace CGAL

#endif // CGAL_CIRCULAR_KERNEL_PREDICATES_ON_CIRCULAR_ARC_2_H