circular_arc_2.h

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

      return circle_table.find<T>(c1.id_of_my_supporting_circle, 
                                  c2.id_of_my_supporting_circle, 
                                  res);
    }

    template < class T >
    static void put_intersection_circle_circle(const Circular_arc_2& c1, 
      const Circular_arc_2& c2,
      const T& res) {
      circle_table.put<T>(c1.circle_number(), 
                          c2.circle_number(), 
                          res);
    }
#endif

    // to remember if the arc was constructed from a full circle
    const Circular_arc_point_2 & left() const
    {
      CGAL_kernel_precondition(is_x_monotone());
      CGAL_kernel_precondition(on_upper_part() ? compare_xy(_end,_begin)<0
      			       : compare_xy(_begin,_end)<0);
      if (on_upper_part()) return _end;
      return  _begin;
    }

    const Circular_arc_point_2 & right() const
    {
      CGAL_kernel_precondition(is_x_monotone());
      CGAL_kernel_precondition(on_upper_part() ? compare_xy(_end,_begin)<0
      			       : compare_xy(_begin,_end)<0);
      if (on_upper_part()) return _begin;
      return  _end;
    }

    const Circular_arc_point_2 & source() const
    {
      return _begin;
    }
    
    const Circular_arc_point_2 & target() const
    {
      return _end;
    }
    
    bool is_full() const {
      return flags.is_full == 2;
    }

private:
    
#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    void _get_id_number() {
      my_id = table.get_new_id();
    }
#endif

    bool _is_x_monotone() const {
      if (is_full()) return false;
      
      int cmp_begin = CGAL::compare(_begin.y(), center().y());
      int cmp_end   = CGAL::compare(_end.y(),   center().y());

      // XXX : be careful, this may be surprising if the return value
      // is not -1/1 but some random int...

      if (cmp_begin == opposite(cmp_end) && cmp_begin != 0)
        return false;

      // Maybe the complementar is x_monotone
      // but we have to go further to know
      // see is_x_monotone()
      flags.is_complementary_x_monotone = 1;

      int cmp_x = compare_x(_begin, _end);
      
      // Is the arc on the upper part ?
      if (cmp_begin > 0 || cmp_end > 0)
        return cmp_x > 0;

      // Is the arc on the lower part ?
      if (cmp_begin < 0 || cmp_end < 0)
        return cmp_x < 0;

      // There remains the case :
      CGAL_kernel_assertion(cmp_begin == 0 && cmp_end == 0);

      return cmp_x != 0; // full circle or half circle.
    }

    bool _is_y_monotone() const {
      if (is_full()) return false;

      int cmp_begin = CGAL::compare(_begin.x(), center().x());
      int cmp_end   = CGAL::compare(_end.x(),   center().x());
      
      // XXX : be careful, this may be surprising if the return value
      // is not -1/1 but some random int...
      if (cmp_begin == opposite(cmp_end) && cmp_begin != 0)
        return false;

      // Maybe the complementar is y_monotone
      // but we have to go further to know
      // see is_y_monotone()
      flags.is_complementary_y_monotone = 1;

      int cmp_y = compare_y(_begin, _end);
      
      // Is the arc on the right part ?
      if (cmp_begin > 0 || cmp_end > 0)
        return cmp_y < 0;

      // Is the arc on the left part ?
      if (cmp_begin < 0 || cmp_end < 0)
        return cmp_y > 0;
      
      // There remains the case :
      assert(cmp_begin == 0 && cmp_end == 0);

      return cmp_y != 0; // full circle or half circle.
    }

    // if the 2 points are on x-extremals
    // true if the arc is on upper-part
    bool _two_end_points_on_upper_part() const {
      int c1y = CGAL::compare(_begin.y(),
        supporting_circle().center().y());
      if(c1y > 0) return true;
      if(c1y < 0) return false;
      int c2y = CGAL::compare(_end.y(),
        supporting_circle().center().y());
      if(c2y > 0) return true;
      if(c2y < 0) return false;
      return compare_x(_begin, _end) > 0;
    }

    // if the 2 points are on y-extremals
    // true if the arc is on left-part
    bool _two_end_points_on_left_part() const
    { 
      int c1x = CGAL::compare(_begin.x(), 
        supporting_circle().center().x());
      if(c1x < 0) return true;
      if(c1x > 0) return false;
      int c2x = CGAL::compare(_end.x(), 
        supporting_circle().center().x());
      if(c2x < 0) return true;
      if(c2x > 0) return false;
      return compare_y(_begin, _end) > 0;
    }

public:

    bool is_x_monotone() const {
      if(flags.is_x_monotonic == 0) {
        bool b = _is_x_monotone();
        if(b) { 
          flags.is_x_monotonic = 2;
          flags.is_complementary_x_monotone = 0;
        } else flags.is_x_monotonic = 1;
        return b;
      } else {
        return (flags.is_x_monotonic == 1) ? false : true;
      }
    } 

    // Returns true if the complementary arc is x_monotone()
    // note: if semi-cercle -> false
    bool is_complementary_x_monotone() const {
      // is_x_monotone calculates also if 
      // the complementary is x-monotone if needed
      is_x_monotone();
      return (flags.is_complementary_x_monotone == 0) ? false : true;
    } 

    bool is_y_monotone() const {
      if(flags.is_y_monotonic == 0) {
        bool b = _is_y_monotone();
        if(b) {
          flags.is_y_monotonic = 2;
          flags.is_complementary_y_monotone = 0;
        } else flags.is_y_monotonic = 1;
        return b;
      } else {
        return (flags.is_y_monotonic == 1) ? false : true;
      }
    }

    // Returns true if the complementary arc is y_monotone()
    // note: if semi-cercle -> false
    bool is_complementary_y_monotone() const {
      // is_y_monotone calculates also if 
      // the complementary is y-monotone if needed
      is_y_monotone();
      return (flags.is_complementary_y_monotone == 0) ? false : true;
    }

    // check whether 2 endpoints are at upper or not from the center 
    bool two_end_points_on_upper_part() const {
      if(flags.two_end_points_on_upper_part == 0) {
        bool b = _two_end_points_on_upper_part();
        if(b) flags.two_end_points_on_upper_part = 2;
        else flags.two_end_points_on_upper_part = 1;
        return b;
      } else {
        return (flags.two_end_points_on_upper_part == 1) ? false : true;
      }
    }

    // check whether the arc is at upper or not from the center 
    bool on_upper_part() const {
      CGAL_kernel_precondition(is_x_monotone());
      return two_end_points_on_upper_part();
    }

    // Returns true if the complementary arc is on_upper_part()
    bool complementary_on_upper_part() const {
      if(is_x_monotone()) return false;
      return two_end_points_on_upper_part();
    }

    // check whether the 2 endpoints are at left or right from the center
    bool two_end_points_on_left_part() const {
      if(flags.two_end_points_on_left_part == 0) {
        bool b = _two_end_points_on_left_part();
        if(b) flags.two_end_points_on_left_part = 2;
        else flags.two_end_points_on_left_part = 1;
        return b;
      } else {
        return (flags.two_end_points_on_left_part == 1) ? false : true;
      }
    }

    // check whether the arc is at left or right from the center 
    bool on_left_part() const {      
      CGAL_kernel_precondition(is_y_monotone());
      return two_end_points_on_left_part();
    }

    // Returns true if the complementary arc is on_left_part()
    bool complementary_on_left_part() const {
      if(is_y_monotone()) return false;
      return two_end_points_on_left_part();
    }

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
    unsigned int number() const {
      return my_id;
    }
#endif

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
    unsigned int circle_number() const {
      if(!id_of_my_supporting_circle)
        id_of_my_supporting_circle = circle_table.get_new_id();
      return id_of_my_supporting_circle;
    }

    void set_circle_number(unsigned int i) const {
      id_of_my_supporting_circle = i;
    }
#endif

    const Circle_2 & supporting_circle() const
    {
       return _support;
    }

    const Point_2 & center() const           
    {
       return supporting_circle().center();
    }

    const FT & squared_radius() const           
    {
       return supporting_circle().squared_radius();
    }

    Bbox_2 bbox() const
    {
      return CGAL::CircularFunctors::circular_arc_bbox<CK>(*this);
    }    

    // Dont use this function, it is only for internal use
    void _setx_info(unsigned short int v_is_x_monotone,
                  unsigned short int v_two_end_points_on_upper_part,
                  unsigned short int v_is_complementary_x_monotone) const {
      flags.is_x_monotonic = v_is_x_monotone;
      flags.two_end_points_on_upper_part = v_two_end_points_on_upper_part;
      flags.is_complementary_x_monotone = v_is_complementary_x_monotone;
    }
    
  };

#ifdef CGAL_INTERSECTION_MAP_FOR_XMONOTONIC_ARC_WITH_SAME_SUPPORTING_CIRCLE
  template < typename CK >
  CGALi::Intersection_line_2_circle_2_map Circular_arc_2< CK >::table = 
    CGALi::Intersection_line_2_circle_2_map();
#endif

#ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 
  template < typename CK >
  CGALi::Intersection_line_2_circle_2_map Circular_arc_2< CK >::circle_table = 
    CGALi::Intersection_line_2_circle_2_map();
#endif

  template < typename CK >
  std::ostream &
  operator<<(std::ostream & os, const Circular_arc_2<CK> &a)
  {
    // The output format is :
    // - supporting circle
    // - circle c1
    // - bool b1
    // - circle c2
    // - bool b2
    return os << a.supporting_circle() << " "
	      << a.source() << " "
	      << a.target() << " ";
  }

  template < typename CK >
  std::istream &
  operator>>(std::istream & is, Circular_arc_2<CK> &a)
  {
    typename CK::Circle_2 s;
    typename CK::Circular_arc_point_2 p1;
    typename CK::Circular_arc_point_2 p2;
    is >> s >> p1 >> p2 ;
    if (is)
      a = Circular_arc_2<CK>(s, p1, p2);
    return is;
  }

  template < typename CK >
  std::ostream &
  print(std::ostream & os, const Circular_arc_2<CK> &a)
  {
    if(a.is_x_monotone()) {
      return os << "Circular_arc_2( " << std::endl
                << "left : " << a.left() << " , " << std::endl
                << "right : " << a.right() << " , " << std::endl
                << "upper part : " << a.on_upper_part() << std::endl
                << "  [[ approximate circle is (x,y,r) : "
                << CGAL::to_double(a.supporting_circle().center().x()) << ""
                << CGAL::to_double(a.supporting_circle().center().y()) << ""
                << std::sqrt(CGAL::to_double(a.supporting_circle().squared_radius()))
                << " ]])" << std::endl;
    } else {
      return os << "Circular_arc_2( " << std::endl
                << "  [[ approximate circle is (x,y,r) : "
                << CGAL::to_double(a.supporting_circle().center().x()) << ""
                << CGAL::to_double(a.supporting_circle().center().y()) << ""
                << std::sqrt(CGAL::to_double(a.supporting_circle().squared_radius()))
                << " ]])" << std::endl;
    }
  }     

} // namespace CGALi
} // namespace CGAL

#undef CGAL_USEFUL_MAPS_FOR_THE_CIRCULAR_KERNEL
#endif // CGAL_CIRCULAR_KERNEL_CIRCULAR_ARC_2_H