conic_arc_2.h

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

    if (turn == LEFT_TURN)
    {
      _orient = CGAL::COUNTERCLOCKWISE;
      same_turn = (orient_f(p1, p3, p5) == LEFT_TURN) &&
                  (orient_f(p1, p4, p5) == LEFT_TURN);
    }
    else
    {
      _orient = CGAL::CLOCKWISE;
      same_turn = (orient_f(p1, p3, p5) != LEFT_TURN) &&
                  (orient_f(p1, p4, p5) != LEFT_TURN);
    }

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

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

    // Make sure that all midpoints are strictly between the
    // source and the target.
    bool      valid_midpoints = true;
    Point_2   mp2 (CoNT(p2.x()), CoNT(p2.y()));

    if (! _is_strictly_between_endpoints (mp2))
    {
      valid_midpoints = false;
    }
    else
    {
      Point_2   mp3 (CoNT(p3.x()), CoNT(p3.y()));

      if (! _is_strictly_between_endpoints (mp3))
      {
        valid_midpoints = false;
      }
      else
      {
        Point_2   mp4 (CoNT(p4.x()), CoNT(p4.y()));

        if (! _is_strictly_between_endpoints (mp4))
          valid_midpoints = false;
      }
    }

    // If the midpoints are not valid, mark the arc as invalid.
    if (! valid_midpoints)
      _info = (_info & ~IS_VALID);
  }

  // Construct a conic arc which lies on the conic:
  //   C: r*x^2 + s*y^2 + t*xy + u*x + v*y + w = 0
  // The source and the target are specified by the intersection of the
  // conic with:
  //   C_1: r_1*x^2 + s_1*y^2 + t_1*xy + u_1*x + v_1*y + w_1 = 0
  //   C_2: r_2*x^2 + s_2*y^2 + t_2*xy + u_2*x + v_2*y + w_2 = 0
  // The user must also specify the source and the target with approximated
  // coordinates. The actual intersection points that best fits the source 
  // (or the target) will be selected.
  Conic_arc_2 (const CfNT& r, const CfNT& s, const CfNT& t,
               const CfNT& u, const CfNT& v, const CfNT& w,
               const Orientation& orient,
               const Point_2& app_source,
               const CfNT& r_1, const CfNT& s_1, const CfNT& t_1,
               const CfNT& u_1, const CfNT& v_1, const CfNT& w_1,
               const Point_2& app_target,
               const CfNT& r_2, const CfNT& s_2, const CfNT& t_2,
               const CfNT& u_2, const CfNT& v_2, const CfNT& w_2) :
    _r(r), _s(s), _t(t), _u(u), _v(v), _w(w),
    _info(X_MON_UNDEFINED),
    _hyper_P(NULL)
  {
    // Create the two auxiliary conic arcs.
    Conic_arc_2    aux_s_arc, aux_t_arc;

    aux_s_arc._r = r_1;       aux_t_arc._r = r_2;
    aux_s_arc._s = s_1;       aux_t_arc._s = s_2;
    aux_s_arc._t = t_1;       aux_t_arc._t = t_2;
    aux_s_arc._u = u_1;       aux_t_arc._u = u_2;
    aux_s_arc._v = v_1;       aux_t_arc._v = v_2;
    aux_s_arc._w = w_1;       aux_t_arc._w = w_2;

    // Compute the source and the target.
    const CfNT _zero = 0;
    int        my_info;
    CoNT       xs[4];        // The x coordinates of intersection points.
    int        n_xs;         // Number of x coordinates.
    CoNT       ys[4];        // The y coordinates of intersection points.
    int        n_ys;         // Number of y coordinates.
    Point_2    ipts[4];      // The intersection points.
    int        n_points;     // Their number.
    CoNT       dist, best_dist;
    int        ind, best_ind;
    int        k;

    if (CGAL_NTS compare(r, _zero) == EQUAL && 
        CGAL_NTS compare(s, _zero) == EQUAL &&
        CGAL_NTS compare(t, _zero) == EQUAL)
    {
      my_info = DEGREE_1;
    }
    else
    {
      my_info = DEGREE_2;
    }

    for (k = 0; k < 2; k++)
    {
      // Get the x- and y-coordinates of the intersection points with the
      // first (if k == 0) or the second (if k == 1) auxiliary curves.
      const Conic_arc_2& arc = (k == 0) ? aux_s_arc : aux_t_arc;
      int         arc_info;

      if (CGAL_NTS compare(arc._r, _zero) == EQUAL && 
          CGAL_NTS compare(arc._s, _zero) == EQUAL &&
          CGAL_NTS compare(arc._t, _zero) == EQUAL)
      {
        arc_info = DEGREE_1;
      }
      else
      {
        arc_info = DEGREE_2;
      }

      n_xs = _x_coordinates_of_intersection_points (_r, _s, _t, _u, _v, _w,
                                                    my_info,
                                                    arc._r, arc._s, arc._t, 
                                                    arc._u, arc._v, arc._w,
                                                    arc_info,
                                                    xs);
      
      n_ys = _y_coordinates_of_intersection_points (_r, _s, _t, _u, _v, _w,
                                                    my_info,
                                                    arc._r, arc._s, arc._t, 
                                                    arc._u, arc._v, arc._w,
                                                    arc_info,
                                                    ys);

      // Perform the pairing process of the x and y coordinates.
      n_points = _pair_intersection_points (arc,
                                            xs, n_xs,
                                            ys, n_ys,
                                            ipts);

      
      if (n_points == 0)
        // In this case, the arc is invalid.
        return;

      // Choose the intersection point closest to the source
      // (or the target point).
      const Point_2&  p = (k == 0) ? app_source : app_target;

      best_ind = -1;
      for (ind = 0; ind < n_points; ind++)
      {
        dist = CGAL::squared_distance (p, ipts[ind]);

        if (best_ind < 0 || CGAL_NTS compare(best_dist, dist) == LARGER)
        {
          best_dist = dist;
          best_ind = ind;
        }
      }

      // Set the source (or the target).
      if (k == 0)
        _source = ipts[best_ind];
      else
        _target = ipts[best_ind];
    }

    // Make sure that the source and the taget are not the same.
    if (_source == _target)
      // In this case, the arc is invalid.
      return;

    // Set the prescribed orientation.
    _orient = orient;    

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

  /*!
   * Destructor.
   */
  virtual ~Conic_arc_2 ()
  {
    if (_hyper_P)
      delete _hyper_P;
    _hyper_P = NULL;
  }

  /*!
   * Assignment operator.
   * \param arc The copied arc.
   */
  const Self& operator= (const Self& arc)
  {
    if (this == &arc)
      return (*this);

    // Free any existing data.
    if (_hyper_P != NULL)
      delete _hyper_P;
    _hyper_P = NULL;

    // Copy the arc's attributes.
    _r = arc._r;
    _s = arc._s;
    _t = arc._t;
    _u = arc._u;
    _v = arc._v;
    _w = arc._w;

    _orient = arc._orient;
    _conic_id = arc._conic_id;
    _source = arc._source;
    _target = arc._target;
    _info = arc._info;

    // Duplicate the data for hyperbolic arcs.
    if (arc._hyper_P != NULL)
      _hyper_P = new Hyperbolic_arc_data (*(arc._hyper_P));

    return (*this);
  }

  /*! 
   * Get the coefficients of the underlying conic.
   */
  const CfNT& r () const {return (_r);}
  const CfNT& s () const {return (_s);}
  const CfNT& t () const {return (_t);}
  const CfNT& u () const {return (_u);}
  const CfNT& v () const {return (_v);}
  const CfNT& w () const {return (_w);}

  /*!
   * Check if the arc is valid.
   * \return Whether the arc is valid.
   */
  bool is_valid () const
  {
    return ((_info & IS_VALID) != 0);
  }

  /*!
   * Get the arc's source.
   * \return The source point.
   */
  const Point_2& source () const
  {
    return (_source);
  }

  /*!
   * Get the arc's target.
   * \return The target point.
   */
  const Point_2& target () const
  {
    return (_target);
  }

  /*!
   * Get the arc's orientation.
   * \return The orientation.
   */
  Orientation orientation () const
  {
    return (_orient);
  }

  /*!
   * Check whether the two arcs are the same (have the same graph).
   * \param arc The compared arc.
   * \return (true) if the two arcs are equal.
   */
  bool equals (const Self& arc) const
  {
    // Check if (*this) and arc are really the same object:
    if (this == &arc)
      return (true);

    // Check whether all arc features are the same.
    if (_orient == arc._orient)
    {
      // Same orientation: The base conics must be the same and the sources
      // and targets must be equal.
      return (this->has_same_base_conic(arc) &&
              _source.equals(arc._source) &&
              _target.equals(arc._target));
    }
    else
    {
      // Opposite orientation: The base conics must be the same and the sources
      // and targets must be flipped.
      return (this->has_same_base_conic(arc) &&
              _source.equals(arc._target) &&
              _target.equals(arc._source));
    }
  }

  /*!
   * Check whether the two arcs have the same base conic.
   * \param arc The compared arc.
   * \return (true) if the two base conics are the same (have the same graph).
   */
  bool has_same_base_conic (const Self& arc) const
  {
    // In case the two arcs originiat from the same base conic:
    if (_conic_id == arc._conic_id)
      return (true);

    // In case both arcs are collinear, check if they have the same
    // supporting lines.
    if (_orient == CGAL::COLLINEAR && arc._orient == CGAL::COLLINEAR)
    {
      // Construct the two supporting lines and compare them.
      typename Alg_kernel::Line_2  l1 (_source, _target);
      typename Alg_kernel::Line_2  l2 (arc._source, arc._target);
      Alg_kernel                   ker;
      typename Alg_kernel::Equal_2 equal_f = ker.equal_2_object();

      if (equal_f (l1, l2))
        return (true);
      
      // Try to compare l1 with the opposite of l2.
      typename Alg_kernel::Line_2  op_l2 (arc._target, arc._source);

      return (equal_f (l1, op_l2));
    }

    // Check whether arc equals (*this) up to a constant factor.
    const CfNT _zero = 0;
    CfNT       factor1 = 1, factor2 = 1;

    if (CGAL_NTS compare(_r, _zero) != EQUAL)
      factor1 = _r;
    else if (CGAL_NTS compare(_s, _zero) != EQUAL)
      factor1 = _s;
    else if (CGAL_NTS compare(_t, _zero) != EQUAL)
      factor1 = _t;
    else if (CGAL_NTS compare(_u, _zero) != EQUAL)
      factor1 = _u;
    else if (CGAL_NTS compare(_v, _zero) != EQUAL)
      factor1 = _v;
    else if (CGAL_NTS compare(_w, _zero) != EQUAL)
      factor1 = _w;

    if (CGAL_NTS compare(arc._r, _zero) != EQUAL)
      factor2 = arc._r;
    else if (CGAL_NTS compare(arc._s, _zero) != EQUAL)
      factor2 = arc._s;
    else if (CGAL_NTS compare(arc._t, _zero) != EQUAL)
      factor2 = arc._t;
    else if (CGAL_NTS compare(arc._u, _zero) != EQUAL)
      factor2 = arc._u;
    else if (CGAL_NTS compare(arc._v, _zero) != EQUAL)
      factor2 = arc._v;
    else if (CGAL_NTS compare(arc._w, _zero) != EQUAL)
      factor2 = arc._w;

    return (CGAL_NTS compare (_r * factor2, arc._r * factor1) == EQUAL && 
            CGAL_NTS compare (_s * factor2, arc._s * factor1) == EQUAL &&
            CGAL_NTS compare (_t * factor2, arc._t * factor1) == EQUAL &&
            CGAL_NTS compare (_u * factor2, arc._u * factor1) == EQUAL &&
            CGAL_NTS compare (_v * factor2, arc._v * factor1) == EQUAL &&
            CGAL_NTS compare (_w * factor2, arc._w * factor1) == EQUAL);
  }

  /*!
   * Check whether the arc is a full conic (i.e. a non-degenerate ellipse).
   * \return (true) if the arc represents a full conic.
   */
  bool is_full_conic () const
  {
    return ((_info & FULL_CONIC) != 0);
  }

  /*!
   * Check whether the arc is a circular arc.
   * \return (true) if the underlying conic curve is a circle.
   */
  bool is_circular() const
  {
    return (CGAL_NTS compare(_r, _s) == EQUAL && 
            CGAL_NTS compare(_t, 0) == EQUAL);
  }
  
  /*!
   * Check whether the arc is a line segment.
   * \return (true) if the underlying conic curve is linear.
   */
  bool is_segment () const
  {
    // Notice that the orientation is COLLINEAR if the underlying curve has
    // a degree 1, or when it is a line-pair.
    return (_orient == CGAL::COLLINEAR);
  }

  /*!
   * Check whether the arc is a vertical segment.
   * \return (true) if the arc is a vertical segment.
   */
  bool is_vertical_segment () const
  {
    return ((_info & IS_VERTICAL_SEGMENT) != 0);
  }

  /*!
   * Get a bounding box for the conic arc.
   * \return The bounding box.
   */
  Bbox_2 bbox () const
  {
    // Use the source and target to initialize the exterme points.
    bool   source_left = 
      CGAL::to_double(_source.x()) < CGAL::to_double(_target.x());
    double x_min = source_left ?
      CGAL::to_double(_source.x()) : CGAL::to_double(_target.x());
    double x_max = source_left ?
      CGAL::to_double(_target.x()) : CGAL::to_double(_source.x());
    bool   source_down = 
      CGAL::to_double(_source.y()) < CGAL::to_double(_target.y());
    double y_min = source_down ?
      CGAL::to_double(_source.y()) : CGAL::to_double(_target.y());
    double y_max = source_down ?
      CGAL::to_double(_target.y()) : CGAL::to_double(_source.y());

    // Go over the vertical tangency points and try to update the x-points.
    Point_2 tps[2];
    int        n_tps;
    int        i;

    n_tps = vertical_tangency_points (tps);