internal_functions_on_line_arc_2.h

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

    if ( CircularFunctors::compare_xy<CK>(ca1.left(), ca2.left()) != SMALLER )
        {
          std::swap(ca1,ca2);
        }

    return;
  }

  template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Line_arc_2 &a1,
	       const typename CK::Line_arc_2 &a2,
	       OutputIterator res )
  {
    typedef typename CK::Circular_arc_point_2  Circular_arc_point_2;
    typedef typename CK::Line_arc_2               Line_arc_2;
    typedef typename CK::Point_2                  Point_2;
    typedef typename CK::Root_of_2                Root_of_2;
    typedef typename CK::Root_for_circles_2_2     Root_for_circles_2_2;

#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)){

      *res++ = make_object(a1); 
      return res;
    }
    if(a1s_a2s || a1s_a2t || a1t_a2s || a1t_a2t) {
      if(! LinearFunctors::non_oriented_equal<CK>(a1.supporting_line(),a2.supporting_line())){
	if(a1s_a2s || a1s_a2t) *res++ = make_object(std::make_pair(a1.source(), 1u));
	if(a1t_a2s || a1t_a2t) *res++ = make_object(std::make_pair(a1.target(), 1u));
      return res;
      }
    }
#endif
    
    if(LinearFunctors::non_oriented_equal<CK>(
      a1.supporting_line(),a2.supporting_line())) {
      if(compare_xy(a1.left(),a2.left()) < 0) {
	int comparison = compare_xy(a2.left(),a1.right());
	if(comparison < 0){
	  if(compare_xy(a1.right(),a2.right()) <= 0){
	    *res++ = make_object
	      (Line_arc_2(a1.supporting_line(), a2.left(), a1.right() ));
	  } else{
	    *res++ = make_object
	      (Line_arc_2(a1.supporting_line(), a2.left(), a2.right() ));
	  }
	}
	else if (comparison == 0){
	  *res++ =make_object
	    ( std::make_pair(a2.left(),1u));
	}
	return res;
      }
      else{
	int comparison = compare_xy(a1.left(),a2.right());
	if(comparison < 0){
	  if(compare_xy(a1.right(),a2.right()) <= 0){
	    *res++ = make_object
	      (Line_arc_2(a1.supporting_line(), a1.left(), a1.right() ));
	  }
	  else{
	    *res++ = make_object
	      (Line_arc_2(a1.supporting_line(), a1.left(), a2.right() ));
	  }
	}
	else if (comparison == 0){
	  *res++ = make_object
	    ( std::make_pair(a1.left(),1u));
	}
	return res;
      }
    }
    
    Object obj = intersection(a1.supporting_line(), a2.supporting_line());
    const Point_2 *pt = CGAL::object_cast<Point_2>(&obj);
    if(pt == NULL) return res;
    Circular_arc_point_2 intersect_point = Circular_arc_point_2(*pt);
    //      (Root_for_circles_2_2(Root_of_2(pt->x()),Root_of_2(pt->y())));
    
    if ((CircularFunctors::compare_xy<CK>(intersect_point, a1.source()) !=
	 CircularFunctors::compare_xy<CK>(intersect_point, a1.target())) &&
	(CircularFunctors::compare_xy<CK>(intersect_point, a2.source()) !=
	 CircularFunctors::compare_xy<CK>(intersect_point, a2.target())))
      *res++ = make_object(std::make_pair(intersect_point, 1u));

    return res;
  }

  template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Line_arc_2 &l,
	       const typename CK::Circle_2 &c,
	       OutputIterator res )
  { 
    typedef std::vector<CGAL::Object> solutions_container;
    solutions_container solutions;

    CGAL::LinearFunctors::intersect_2<CK>
      ( l.supporting_line(), c, std::back_inserter(solutions) );
    
    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));
      if ( has_on<CK>(l,result->first,true))
	*res++ = *it;
    }
    return res;
  }

  /*template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Line_arc_2 &l,
	       const typename CK::Circle_2 &c,
	       OutputIterator res )
  { 
    typedef std::vector<CGAL::Object> solutions_container;
    solutions_container solutions;

    CGAL::LinearFunctors::intersect_2<CK>
      ( l.supporting_line(), c, std::back_inserter(solutions) );
    
    for (typename solutions_container::iterator it = solutions.begin(); 
	 it != solutions.end(); ++it) {
      const std::pair<typename CK::Circular_arc_point_2, unsigned> *result;
      result = CGAL::object_cast
	<std::pair<typename CK::Circular_arc_point_2, unsigned> > (&(*it));
      if ( has_on<CK>(l,result->first))
	*res++ = *it;
    }
    return res;
  }*/

  template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Circle_2 &c,
	       const typename CK::Line_arc_2 &l,
	       OutputIterator res )
  { 
    return intersect_2<CK>(l,c,res);
  }

  template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Line_arc_2 &l,
	       const typename CK::Circular_arc_2 &c,
	       OutputIterator res )
  {
    typedef typename CK::Circular_arc_2 Circular_arc_2;
    typedef typename CK::Circular_arc_point_2 Circular_arc_point_2;
    typedef typename CK::Line_arc_2 Line_arc_2;
    typedef std::vector<CGAL::Object > solutions_container;

#ifdef CGAL_CK_EXPLOIT_IDENTITY
    bool ls_cs = l.source().equal_ref(c.source());
    bool ls_ct = l.source().equal_ref(c.target());
    bool lt_cs = l.target().equal_ref(c.source());
    bool lt_ct = l.target().equal_ref(c.target());
    
    if((ls_cs && lt_ct) || (ls_ct && lt_cs)){ // Case 0
      if (compare_xy<CK>(l.source(), l.target()) == SMALLER){
	*res++ = make_object(std::make_pair(l.source(), 1u));
	*res++ = make_object(std::make_pair(l.target(), 1u));
      } else {
	*res++ = make_object(std::make_pair(l.target(), 1u));
	*res++ = make_object(std::make_pair(l.source(), 1u));
      }
      return res;
    } else if (ls_cs || lt_ct || ls_ct || lt_cs) {
      Circular_arc_point_2 p,q,r;
      
      if(ls_cs){
	p = l.target();
	q = l.source();
	r = c.target();
      } else if(ls_ct){
	p = l.target();
	q = l.source();
	r = c.source();
      } else if(lt_cs){
	p = l.source();
	q = l.target();
	r = c.target();
      } else { // lt_ct
	p = l.source();
	q = l.target();
	r = c.source();
      }
      
      if( (CircularFunctors::compare_x<CK>(p,q) == EQUAL) || CircularFunctors::point_in_x_range<CK>(p,r,q)){ // Case 1
	*res++ = make_object(std::make_pair(q,1u));
	return res;
      }
       else if(c.on_upper_part()){ // Case 2
	if(CircularFunctors::compare_x<CK>(r,q) == LARGER){
	  if(CircularFunctors::orientation<CK>(q,r,p) == RIGHT_TURN   // Case 2
	     || CircularFunctors::compare_y_to_right<CK>(l,c,q) == LARGER){ // Case 3a
	    *res++ = make_object(std::make_pair(q,1u));
	    return res;
	  }
	} else {
	  if(CircularFunctors::orientation<CK>(r,q,p) == RIGHT_TURN  // Case 2
	  || CircularFunctors::compare_y_to_left<CK>(l,c,q) == LARGER){ // Case 3c 
	    *res++ = make_object(std::make_pair(q,1u));
	    return res;
	  }
	}
       } else { // c on lower part
	if(CircularFunctors::compare_x<CK>(r,q) == LARGER){
	  if (CircularFunctors::orientation<CK>(q,r,p) == LEFT_TURN // Case 2
	    || CircularFunctors::compare_y_to_right<CK>(l,c,q) == SMALLER){  // Case 3b
	    *res++ = make_object(std::make_pair(q,1u));
	    return res;
	  } 
	} else {
	  if(CircularFunctors::orientation<CK>(r,q,p) == LEFT_TURN
	     || CircularFunctors::compare_y_to_left<CK>(l,c,q) == SMALLER){ // Case 3d 
	    *res++ = make_object(std::make_pair(q,1u));
	    return res;
	  } 
	} 
       }
       
      typename CK::Linear_kernel::Bounded_side bs = CircularFunctors::bounded_side<CK>(c.supporting_circle(),p);
      if(bs == ON_BOUNDED_SIDE){ 
	*res++ = make_object(std::make_pair(q,1u));
	return res;
      } else { //Case 4b
	solutions_container solutions;
	CGAL::LinearFunctors::intersect_2<CK>( l.supporting_line(), c.supporting_circle(),
					       std::back_inserter(solutions) );
	
	if(CircularFunctors::compare_x<CK>(r,q) == LARGER){
	  *res++ = make_object(std::make_pair(q,1u));
	  *res++ = solutions.back();
	  return res;
	} else {
	  *res++ = solutions.front();
	  *res++ = make_object(std::make_pair(q,1u));
	  return res;
	}
	
      } // Case 4b
      
      
      std::cout << "oops we missed a case" << std::endl;
      
    }
#endif // CGAL_CK_EXPLOIT_IDENTITY
    
    solutions_container solutions;

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
      if(!Line_arc_2::template 
         find_intersection_circle_line< solutions_container > 
         (c,l,solutions)) {
#endif

      CGAL::LinearFunctors::intersect_2<CK>
      ( l.supporting_line(), c.supporting_circle(),
	std::back_inserter(solutions) );
    
#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES
        Line_arc_2::template 
          put_intersection_circle_line< std::vector < CGAL::Object > >
          (c,l,solutions);
      }
#endif

    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(l.bbox(), rb) && do_overlap(c.bbox(),rb)){
	    if (has_on<CK>(l,result->first,true) && 
		has_on<CK>(c,result->first,true)) {
	      *res++ = *it;
	    }
	  }
#else 
      if (has_on<CK>(l,result->first,true) &&
          has_on<CK>(c,result->first,true)) {
	*res++ = *it;
      }
#endif
    }
    return res;
  }




  /*template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Line_arc_2 &l,
	       const typename CK::Circular_arc_2 &c,
	       OutputIterator res )
  {
    typedef typename CK::Circular_arc_2 Circular_arc_2;
    typedef std::vector<CGAL::Object > solutions_container;
    
    solutions_container solutions;
    CGAL::LinearFunctors::intersect_2<CK>
      ( l.supporting_line(), c.supporting_circle(), 
	std::back_inserter(solutions) );
    
    solutions_container objects_monotone;
    std::vector<const Circular_arc_2*> arcs_x_monotone; 
    make_x_monotone( c, std::back_inserter(objects_monotone));
    for(typename solutions_container::iterator it2 = objects_monotone.begin();
	it2 != objects_monotone.end(); ++it2){
      arcs_x_monotone.push_back(CGAL::object_cast<Circular_arc_2>(&(*it2)));
    }
      
    for (typename solutions_container::iterator it = solutions.begin(); 
	 it != solutions.end(); ++it){
      const std::pair<typename CK::Circular_arc_point_2, unsigned> *result;
      result = CGAL::object_cast
	<std::pair<typename CK::Circular_arc_point_2, unsigned> > (&(*it));
      if ( has_on<CK>(l,result->first)) {
	bool is_on_arc = false;
	for(typename std::vector<const Circular_arc_2*>::iterator 
	      it2 = arcs_x_monotone.begin();
	    it2 != arcs_x_monotone.end(); ++it2){
	  if(has_on<CK>(**it2, result->first)){
	    is_on_arc = true;
	    break;
	  }
	}
	if(is_on_arc)
	  *res++ = *it;
      }
    }
    return res;
  }*/
  
  template< class CK, class OutputIterator>
  OutputIterator
  intersect_2( const typename CK::Circular_arc_2 &c,
	       const typename CK::Line_arc_2 &l,
	       OutputIterator res )
  {
    return intersect_2<CK>(l,c,res);
  }
   
  template < class CK, class OutputIterator >
  OutputIterator
  make_x_monotone( const typename CK::Line_arc_2 &A,
		   OutputIterator res )
  {
    *res++ = make_object(A);
    return res;
  }
  
} // namespace CircularFunctors 
} // namespace CGAL

#endif // CGAL_CIRCULAR_KERNEL_PREDICATES_ON_LINE_ARC_2_H