conic_arc_2.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 2,200 行 · 第 1/5 页

                                            xs);

      found_two_intersection_points = (n_xs == 2);

      if (! found_two_intersection_points)
        // The arc is invalid:
        return;
      
      _source = Point_2 (xs[0],
                         -(a*xs[0] + c) / CoNT(b));
      _target = Point_2 (xs[1],
                         -(a*xs[1] + c) / CoNT(b));

      // Get the conic points whose x-coordinate are in the middle of the
      // two endpoints.
      CoNT      x_mid = (xs[0] + xs[1]) / 2;
      CoNT      ys[2];
      int       n_ys;

      n_ys = _conic_get_y_coordinates (x_mid, ys);

      CGAL_precondition(n_ys > 0);

      if (CGAL_NTS compare (CoNT(a)*x_mid + CoNT(b)*ys[0] + CoNT(c), 
                            0) == LARGER)
      {
        pmid = Point_2 (x_mid, ys[0]);
      }
      else
      {
        CGAL_assertion(CGAL_NTS
                       compare (CoNT(a)*x_mid + CoNT(b)*ys[1] + CoNT(c),
                                0) == LARGER);
        pmid = Point_2 (x_mid, ys[1]);
      }
    }
    else
    {
      CGAL_precondition(CGAL_NTS compare(a, 0) != EQUAL);

      // Find the intersection of the vertical line x = -c / a:
      CoNT       _x = CoNT(-c) / CoNT(a);
      CoNT       ys[2];
      int        n_ys;

      n_ys = _conic_get_y_coordinates (_x, ys);

      found_two_intersection_points = (n_ys == 2);

      if (! found_two_intersection_points)
        // The arc is invalid:
        return;

      _source = Point_2 (_x, ys[0]);
      _target = Point_2 (_x, ys[1]);

      // Get the conic points whose y-coordinate are in the middle of the
      // two endpoints.
      CoNT      y_mid = (ys[0] + ys[1]) / 2;
      CoNT      xs[2];
      int       n_xs;

      n_xs = _conic_get_x_coordinates (y_mid, xs);

      CGAL_precondition(n_xs > 0);

      if (CGAL_NTS compare(CoNT(a)*xs[0] + CoNT(b)*y_mid + CoNT(c), 
                           0) == LARGER)
      {
        pmid = Point_2 (xs[0], y_mid);
      }
      else
      {
        CGAL_assertion(CGAL_NTS
                       compare (CoNT(a)*xs[1] + CoNT(b)*y_mid + CoNT(c),
                                0) == LARGER);
        pmid = Point_2 (xs[1], y_mid);
      }
    }

    // Determine the orientation: If the mid-point forms a left-turn with
    // the source and the target points, the orientation is positive (going
    // counterclockwise).
    // Otherwise, it is negative (going clockwise).
    static Alg_kernel                  ker;
    typename Alg_kernel::Orientation_2 orient_f = ker.orientation_2_object();
    
    if (orient_f(_source, pmid, _target) == LEFT_TURN)
      _orient = CGAL::COUNTERCLOCKWISE;
    else
      _orient = CGAL::CLOCKWISE;

    // Set the arc properties (no need to compute the orientation).
    _set (false);
  }

  /*! 
   * Construct a conic arc which is the full conic:
   *   C: r*x^2 + s*y^2 + t*xy + u*x + v*y + w = 0
   * \param r,s,t,u,v,w The coefficients of the conic curve.
   * \pre The conic C must be an ellipse (so 4rs - t^2 > 0).
   */
  Conic_arc_2 (const CfNT& r, const CfNT& s, const CfNT& t,
               const CfNT& u, const CfNT& v, const CfNT& w) :
    _r(r), _s(s), _t(t), _u(u), _v(v), _w(w),
    _hyper_P(NULL)
  {
    // Make sure the given curve is an ellipse.
    bool    is_ellipse = (CGAL_NTS compare(4*r*s - t*t, CfNT(0)) == LARGER);
    CGAL_precondition(is_ellipse);
        
    if (! is_ellipse)
      // In this case, the arc is invalid.
      return;

    // Set the arc to be the full conic (and compute the orientation).
    _set_full (true);
  }

  /*!
   * Construct a conic arc from the given line segment.
   * \param seg The line segment.
   */
  Conic_arc_2 (const Int_segment_2& seg) :
    _hyper_P(NULL)
  {
    // Get the coordinates of the endpoints.
    const Int_point_2 src = seg.source();
    const Int_point_2 trg = seg.target();
    const CfNT        x1 = src.x(), y1 = src.y();
    const CfNT        x2 = trg.x(), y2 = trg.y();

    _source = Point_2 (CoNT(x1),CoNT(y1));
    _target = Point_2 (CoNT(x2),CoNT(y2));

    // Make sure that the source and the taget are not the same.
    CGAL_precondition(_source != _target);      

    // The supporting conic is r=s=t=0, and u*x + v*y + w = 0 should hold
    // for both the source (x1,y1) and the target (x2, y2).
    const CfNT _zero = 0;
    const CfNT _one = 1;

    if (CGAL_NTS compare (x1, x2) == EQUAL)
    {
      // The supporting conic is a vertical line, of the form x = CONST.
      _r = _zero;    _s = _zero;    _t =  _zero;
      _u = _one;
      _v = _zero;
      _w = -x1;
    }
    else
    {
      // The supporting line is A*x + B*y + C = 0, where:
      //
      //  A = y2 - y1,    B = x1 - x2,    C = x2*y1 - x1*y2 
      //
      _r = _zero;    _s = _zero;    _t =  _zero;
      _u = y2 - y1;
      _v = x1 - x2;
      _w = x2*y1 - x1*y2;
    }

    // The orientation is zero in case of a linear object.
    _orient = CGAL::COLLINEAR;

    // Set the arc properties (no need to compute the orientation).
    _set (false);
  }

  /*!
   * Set a circular arc that lies on a given circle.
   * \param circ The supporting circle.
   * \param orient The orientation of the circle.
   * \param source The source point.
   * \param target The target point.
   * \pre The source and the target must be on the conic boundary and must
   * not be the same.
   */  
  Conic_arc_2 (const Int_circle_2& circ,
               const Orientation& orient,
               const Point_2& source, const Point_2& target) :
    _source(source),
    _target(target),
    _info(X_MON_UNDEFINED),
    _hyper_P(NULL)
  {
    // Produce the correponding conic: if the circle centre is (x0,y0)
    // and it radius is R, that its equation is:
    //   x^2 + y^2 - 2*x0*x - 2*y0*y + (x0^2 + y0^2 - R^2) = 0
    // Since this equation describes a curve with a negative (clockwise) 
    // orientation, we multiply it by -1 if necessary to obtain a positive
    // (counterclockwise) orientation.
    const Int_point_2 cc = circ.center();
    const CfNT        x0 = cc.x(), y0 = cc.y();
    const CfNT        R_sq = circ.squared_radius();
    const CfNT        _zero = 0;

    if (orient == CGAL::COUNTERCLOCKWISE)
    {
      const CfNT _minus_one = -1;
      const CfNT _two       = 2;

      _r = _minus_one;
      _s = _minus_one;
      _t = _zero;
      _u = _two*x0;
      _v = _two*y0;
      _w = R_sq - x0*x0 - y0*y0;

      _orient = CGAL::COUNTERCLOCKWISE;
    }
    else
    {
      const CfNT _one       = 1;
      const CfNT _minus_two = -2;

      _r = _one;
      _s = _one;
      _t = _zero;
      _u = _minus_two*x0;
      _v = _minus_two*y0;
      _w = x0*x0 + y0*y0 - R_sq;

      _orient = CGAL::CLOCKWISE;
    }

    // Make sure the conic contains the two end-points on its boundary.
    const bool    source_on_boundary = _conic_has_on_boundary(source);
    CGAL_precondition(source_on_boundary);

    const bool    target_on_boundary = _conic_has_on_boundary(target);
    CGAL_precondition(target_on_boundary);

    // Make sure that the source and the target are not the same.
    const bool    source_not_equals_target = (source != target);
    CGAL_precondition(source_not_equals_target);      

    if (! (source_on_boundary && target_on_boundary && 
           source_not_equals_target))
    {
      // In this case, the arc is invalid.
      return;
    }

    // Set the arc properties (no need to compute the orientation).
    _set (false);
  }

  /*!
   * Set a circular arc that corresponds a full circle:
   * \param circ The circle.
   */ 
  Conic_arc_2 (const Int_circle_2& circ) :
    _hyper_P(NULL)
  {
    // Produce the correponding conic: if the circle centre is (x0,y0)
    // and it radius is R, that its equation is:
    //   x^2 + y^2 - 2*x0*x - 2*y0*y + (x0^2 + y0^2 - R^2) = 0
    // Note that this equation describes a curve with a negative (clockwise) 
    // orientation.
    const Int_point_2 cc = circ.center();
    const CfNT        x0 = cc.x(), y0 = cc.y();
    const CfNT        R_sq = circ.squared_radius();
    const CfNT        _zero      = 0;
    const CfNT        _one       = 1;
    const CfNT        _minus_two = -2;

    _r = _one;
    _s = _one;
    _t = _zero;
    _u = _minus_two*x0;
    _v = _minus_two*y0;
    _w = x0*x0 + y0*y0 - R_sq;

    _orient = CGAL::CLOCKWISE;

    // Set the arc to be the full conic (no need to compute the orientation).
    _set_full (false);
  }

  /*!
   * Construct a circular arc from the given three points.
   * \param p1 The source point of the circular arc.
   * \param p2 A point between p1 and p3 on the arc.
   * \param p3 The target point of the circular arc.
   * \pre The three points must not be collinear.
   */
  Conic_arc_2 (const Int_point_2& p1,
               const Int_point_2& p2,
               const Int_point_2& p3) :
    _info(X_MON_UNDEFINED),
    _hyper_P(NULL)
  {
    // Make sure that the source and the target are not the same.
    const bool    source_not_equals_target = (p1 != p3);
    CGAL_precondition(source_not_equals_target);      

    if (!source_not_equals_target)
    {
      // In this case, the arc is invalid.
      return;
    }

    // Get the coordinates of the points.
    const CfNT        x1 = p1.x(), y1 = p1.y();
    const CfNT        x2 = p2.x(), y2 = p2.y();
    const CfNT        x3 = p3.x(), y3 = p3.y();
    const CfNT        _zero = 0;
    const CfNT        _two  = 2;
 
    // Compute the lines: A1*x + B1*y + C1 = 0,
    //               and: A2*x + B2*y + C2 = 0,
    // where:
    const CfNT A1 = _two*(x1 - x2);
    const CfNT B1 = _two*(y1 - y2);
    const CfNT C1 = y2*y2 - y1*y1 + x2*x2 - x1*x1;

    const CfNT A2 = _two*(x2 - x3);
    const CfNT B2 = _two*(y2 - y3);
    const CfNT C2 = y3*y3 - y2*y2 + x3*x3 - x2*x2;

    // Compute the coordinates of the intersection point between the
    // two lines, given by (Nx / D, Ny / D), where:
    const CfNT Nx = B1*C2 - B2*C1;
    const CfNT Ny = A2*C1 - A1*C2;
    const CfNT D = A1*B2 - A2*B1;

    // Make sure the three points are not collinear.
    const bool points_collinear = (CGAL_NTS compare(D, _zero) == EQUAL);
    
    CGAL_precondition(!points_collinear);      

    if (points_collinear)
    {
      // In this case, the arc is invalid.
      return;
    }

    // The equation of the underlying circle is given by:
    _r = D*D;
    _s = D*D;
    _t = _zero;
    _u = -_two*D*Nx;
    _v = -_two*D*Ny;
    _w = Nx*Nx + Ny*Ny - ((D*x2 - Nx)*(D*x2 - Nx) + (D*y2 - Ny)*(D*y2 - Ny));

    // Set the endpoints.
    _source = Point_2 (CoNT(x1),CoNT(y1));
    _target = Point_2 (CoNT(x3),CoNT(y3));

    // Determine the orientation: If the mid-point forms a left-turn with
    // the source and the target points, the orientation is positive (going
    // counterclockwise).
    // Otherwise, it is negative (going clockwise).
    static Alg_kernel                  ker;
    typename Alg_kernel::Orientation_2 orient_f = ker.orientation_2_object();
    Point_2                            pmid = Point_2(CoNT(x2), CoNT(y2));
    
    if (orient_f(_source, pmid, _target) == LEFT_TURN)
      _orient = CGAL::COUNTERCLOCKWISE;
    else
      _orient = CGAL::CLOCKWISE;

    // Set the arc properties (no need to compute the orientation).
    _set (false);
  }

  /*!
   * Construct a conic arc from the given five points, specified by the
   * points p1, p2, p3, p4 and p5.
   * \param p1 The source point of the given arc.
   * \param p2,p3,p4 Points lying on the conic arc, between p1 and p5.
   * \param p5 The target point of the given arc.
   * \pre No three points are collinear.
   */
  Conic_arc_2 (const Int_point_2& p1,
               const Int_point_2& p2,
               const Int_point_2& p3,
               const Int_point_2& p4,
               const Int_point_2& p5) :
    _info(X_MON_UNDEFINED),
    _hyper_P(NULL)
  {
    // Make sure that the source and the target are not the same.
    const bool    source_not_equals_target = (p1 != p5);
    CGAL_precondition(source_not_equals_target);      

    if (!source_not_equals_target)
    {
      // In this case, the arc is invalid.
      return;
    }

    // Make sure that no three points are collinear.
    Int_kernel                         ker;
    typename Int_kernel::Orientation_2 orient_f = ker.orientation_2_object();

    if (orient_f (p1, p2, p3) == CGAL::COLLINEAR ||
        orient_f (p1, p2, p4) == CGAL::COLLINEAR ||
        orient_f (p1, p2, p5) == CGAL::COLLINEAR ||
        orient_f (p1, p3, p4) == CGAL::COLLINEAR ||
        orient_f (p1, p3, p5) == CGAL::COLLINEAR ||
        orient_f (p1, p4, p5) == CGAL::COLLINEAR ||
        orient_f (p2, p3, p4) == CGAL::COLLINEAR ||
        orient_f (p2, p3, p5) == CGAL::COLLINEAR ||
        orient_f (p2, p4, p5) == CGAL::COLLINEAR ||
        orient_f (p3, p4, p5) == CGAL::COLLINEAR)
    {
      // Invalid arc:
      return;
    }

    // Get the coordinates of the points.
    const CfNT        x1 = p1.x(), y1 = p1.y();
    const CfNT        x5 = p5.x(), y5 = p5.y();

    // Set a conic curve that passes through the five given point.
    typename Int_kernel::Conic_2   temp_conic;

    temp_conic.set (p1, p2, p3, p4, p5);

    // Get the conic coefficients.
    _r = temp_conic.r();
    _s = temp_conic.s();
    _t = temp_conic.t();
    _u = temp_conic.u();
    _v = temp_conic.v();
    _w = temp_conic.w();

    // Set the source and target points.
    _source = Point_2 (CoNT(x1), CoNT(y1));
    _target = Point_2 (CoNT(x5), CoNT(y5));

    // Determine the orientation: If one of the midpoints forms a left-turn
    // with the source and the target points, the orientation is positive
    // (going counterclockwise).
    // Otherwise, it is negative (going clockwise).
    const Orientation                  turn = orient_f(p1, p2, p5);
    bool                               same_turn;