conic_arc_2.h

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

    for (i = 0; i < n_tps; i++)
    {
      if (CGAL::to_double(tps[i].x()) < x_min)
        x_min = CGAL::to_double(tps[i].x());
      if (CGAL::to_double(tps[i].x()) > x_max)
        x_max = CGAL::to_double(tps[i].x());
    }

    // Go over the horizontal tangency points and try to update the y-points.
    n_tps = horizontal_tangency_points (tps);
    for (i = 0; i < n_tps; i++)
    {
      if (CGAL::to_double(tps[i].y()) < y_min)
        y_min = CGAL::to_double(tps[i].y());
      if (CGAL::to_double(tps[i].y()) > y_max)
        y_max = CGAL::to_double(tps[i].y());
    }
    
    // Return the resulting bounding box.
    return (Bbox_2 (x_min, y_min, x_max, y_max));
  }

  /*!
   * Check whether the given point is on the conic arc.
   * \param q The query point.
   * \return (true) if the arc contains the point q.
   */
  bool contains_point (const Point_2& q) const
  { 
    // Check whether the conic contains the point (x,y).
    if (q.is_generating_conic_id(_conic_id) ||
        _conic_has_on_boundary(q))
    {
      // If the point is on the conic boundary, it is contained in the arc
      // either if the arc is a full conic, or if it is between the two
      // endpoints of the arc.      
      return (is_full_conic() || _is_between_endpoints(q));
    }

    // If the point is not on the conic boundary, it cannot be on the arc.
    return (false);
  }

  /*!
   * Calculate the vertical tangency points of the arc.
   * \param vpts The vertical tangency points -- should be allocated at the 
   * size of 2).
   * \return The number of vertical tangency points.
   */
  int vertical_tangency_points (Point_2* vpts) const
  {
    // No vertical tangency points for segments or for x-monotone curves:
    if ((_info & DEGREE_MASK) < 2 ||
        (_info & X_MON_UNDEFINED) == X_MONOTONE)
    {
      return (0);
    }

    // Calculate the vertical tangency points of the conic.
    Point_2 ps[2];
    int     n;

    n = _conic_vertical_tangency_points (ps);

    // Return only the points that are contained in the arc interior.
    int    m = 0;
    int    i;

    for (i = 0; i < n; i++)
    {
      if (is_full_conic() || _is_strictly_between_endpoints(ps[i]))
      {
        vpts[m] = ps[i];
        m++;
      }
    }

    // Return the number of vertical tangency points found.
    return (m);
  }

  /*!
   * Calculate the horizontal tangency points of the arc.
   * \param hpts The horizontal tangency points -- should be allocated at the 
   * size of 2).
   * \return The number of horizontal tangency points.
   */
  int horizontal_tangency_points (Point_2* hpts) const
  {
    // No horizontal tangency points for segments:
    if ((_info & DEGREE_MASK) < 2)
      return (0);

    // Calculate the horizontal tangency points of the conic.
    Point_2    ps[2];
    int        n;

    n = _conic_horizontal_tangency_points (ps);

    // Return only the points that are contained in the arc interior.
    int    m = 0;
    int    i;

    for (i = 0; i < n; i++)
    {
      if (is_full_conic() || _is_strictly_between_endpoints(ps[i]))
      {
        hpts[m] = ps[i];
        m++;
      }
    }

    // Return the number of horizontal tangency points found.
    return (m);
  }

  /*!
   * Check whether the arc is x-monotone.
   * \return (true) if the arc is x-monotone.
   */
  bool is_x_monotone() const 
  {
    // If the answer is pre-calculated (and stored in the _info field), just
    // return it:
    int    is_x_mon = _info & X_MON_UNDEFINED;

    if (is_x_mon == 0)
      return (false);
    else if (is_x_mon == X_MONOTONE)
      return (true);

    // Check the number of vertical tangency points.
    Point_2 vpts[2];

    return (vertical_tangency_points(vpts) == 0);
  }

  /*!
   * Find all points on the arc with a given x-coordinate.
   * \param p A placeholder for the x-coordinate.
   * \param ps The point on the arc at x(p) -- should be allocated at the 
   * size of 2.
   * \return The number of points found.
   */
  int get_points_at_x (const Point_2& p,
                       Point_2 *ps) const
  {
    // Get the y coordinates of the points on the conic.
    CoNT    ys[2];
    int     n;

    n = _conic_get_y_coordinates (p.x(), ys);
    
    // Find all the points that are contained in the arc.
    int   m = 0;
    int   i;

    for (i = 0; i < n; i++)
    {
      ps[m] = Point_2 (p.x(), ys[i], _conic_id);

      if (is_full_conic() || _is_between_endpoints(ps[m]))
        m++;
    }

    // Return the number of points on the arc.
    return (m);
  }

  /*!
   * Find all points on the arc with a given y-coordinate.
   * \param p A placeholder for the y-coordinate.
   * \param ps The point on the arc at y(p) -- should be allocated at the 
   * size of 2.
   * \return The number of points found.
   */
  int get_points_at_y (const Point_2& p,
                       Point_2 *ps) const
  {
    // Get the y coordinates of the points on the conic.
    CoNT    xs[2];
    int     n;

    n = _conic_get_x_coordinates (p.y(), xs);
    
    // Find all the points that are contained in the arc.
    int   m = 0;
    int   i;

    for (i = 0; i < n; i++)
    {
      ps[m] = Point_2 (xs[i], p.y(), _conic_id);

      if (is_full_conic() || _is_between_endpoints(ps[m]))
        m++;
    }

    // Return the number of points on the arc.
    return (m);
  }
  
  /*! 
   * Flip the conic arc: change its orientation and swap it source and target.
   * \return The flipped arc.
   */
  Self flip () const
  {

    // Create a base conic with opposite orientation:
    Self     opp_arc;

    opp_arc._r = -_r;
    opp_arc._s = -_s;
    opp_arc._t = -_t;
    opp_arc._u = -_u;
    opp_arc._v = -_v;
    opp_arc._w = -_w;
    
    if (_orient == CGAL::COUNTERCLOCKWISE)
      opp_arc._orient = CGAL::CLOCKWISE;
    else if (_orient == CGAL::CLOCKWISE)
      opp_arc._orient = CGAL::COUNTERCLOCKWISE;
    else
      opp_arc._orient = _orient;         // Linear arc (a segment).

    opp_arc._conic_id = _conic_id;

    // Exchange the source and the target.
    opp_arc._source = _target;
    opp_arc._target = _source;
    opp_arc._info = _info;         // These properties do not change.

    // Copy data for hyperbolic arcs.
    if (_hyper_P != NULL)
      opp_arc._hyper_P = new Hyperbolic_arc_data (*_hyper_P);
    else
      opp_arc._hyper_P = NULL;
 
    return (opp_arc);
  }

  /*! RWRW - Allow higher order derivatives.
   * Get the i'th order derivative by x of the conic at the point p=(x,y).
   * \param p The point where we derive.
   * \param i The order of the derivatives (either 1 or 2).
   * \param slope_numer The numerator of the slope.
   * \param slope_denom The denominator of the slope.
   * \pre i should be either 1 (first order) or 2 (second order).
   */
  void derive_by_x_at (const Point_2& p, const int& i,
                       CoNT& slope_numer, CoNT& slope_denom) const
  {
    // Make sure i is either 1 or 2.
    CGAL_precondition(i == 1 || i == 2);

    // Make sure p is contained in the arc.
    CGAL_precondition(contains_point(p));

    // The derivative by x of the conic 
    //   C: {r*x^2 + s*y^2 + t*xy + u*x + v*y + w = 0}
    // at the point p=(x,y) is given by:
    //
    //           2r*x + t*y + u       alpha 
    //   y' = - ---------------- = - -------
    //           2s*y + t*x + v       beta
    //
    const CoNT _two = 2;
    const CoNT sl_numer = _two*CoNT(_r)*p.x() + CoNT(_t)*p.y() + CoNT(_u);
    const CoNT sl_denom = _two*CoNT(_s)*p.y() + CoNT(_t)*p.x() + CoNT(_v);

    if (i == 1)
    {
      if (CGAL_NTS compare (sl_denom, 0) == LARGER)
      {
        slope_numer = -sl_numer;
        slope_denom = sl_denom;
      }
      else
      {
        slope_numer = sl_numer;
        slope_denom = -sl_denom;
      }

      return;
    }

    // The second derivative is given by:
    //
    //             s*alpha^2 - t*alpha*beta + r*beta^2
    //   y'' = -2 -------------------------------------
    //                           beta^3
    //
    const CoNT sl2_numer = CoNT(_s) * sl_numer * sl_numer -
                           CoNT(_t) * sl_numer * sl_denom +
                           CoNT(_r) * sl_denom * sl_denom;
    const CoNT sl2_denom = sl_denom * sl_denom * sl_denom;

    if (CGAL_NTS compare(sl_denom, 0) == LARGER) // So sl2_denom > 0 as well.
    {
      slope_numer = -_two *sl2_numer;
      slope_denom = sl2_denom;
    }
    else
    {
      slope_numer = _two *sl2_numer;
      slope_denom = -sl2_denom;
    }

    return;
  }

  /*! RWRW - Allow higher order derivatives.
   * Get the i'th order derivative by y of the conic at the point p=(x,y).
   * \param p The point where we derive.
   * \param i The order of the derivatives (either 1 or 2).
   * \param slope_numer The numerator of the slope.
   * \param slope_denom The denominator of the slope.
   * \pre i should be either 1 (first order) or 2 (second order).
   */
  void derive_by_y_at (const Point_2& p, const int& i,
                       CoNT& slope_numer, CoNT& slope_denom) const
  {
    // Make sure i is either 1 or 2.
    CGAL_precondition(i == 1 || i == 2);

    // Make sure p is contained in the arc.
    CGAL_precondition(contains_point(p));

    // The derivative by y of the conic 
    //   C: {r*x^2 + s*y^2 + t*xy + u*x + v*y + w = 0}
    // at the point p=(x,y) is given by:
    //
    //           2s*y + t*x + v     alpha 
    //   x' = - ---------------- = -------
    //           2r*x + t*y + u      beta
    //
    const CoNT _two = 2;
    const CoNT sl_numer = _two*CoNT(_s)*p.y() + CoNT(_t)*p.x() + CoNT(_v);
    const CoNT sl_denom = _two*CoNT(_r)*p.x() + CoNT(_t)*p.y() + CoNT(_u);

    if (i == 1)
    {
      if (CGAL_NTS compare(sl_denom, 0) == LARGER)
      {
        slope_numer = -sl_numer;
        slope_denom = sl_denom;
      }
      else
      {
        slope_numer = sl_numer;
        slope_denom = -sl_denom;
      }

      return;
    }

    // The second derivative is given by:
    //
    //             r*alpha^2 - t*alpha*beta + s*beta^2
    //   x'' = -2 -------------------------------------
    //                           beta^3
    //
    const CoNT sl2_numer = CoNT(_r) * sl_numer * sl_numer -
                           CoNT(_t) * sl_numer * sl_denom +
                           CoNT(_s) * sl_denom * sl_denom;
    const CoNT sl2_denom = sl_denom * sl_denom * sl_denom;

    if (CGAL_NTS compare(sl_denom, 0) == LARGER) // So sl2_denom > 0 as well.
    {
      slope_numer = -_two *sl2_numer;
      slope_denom = sl2_denom;
    }
    else
    {
      slope_numer = _two *sl2_numer;
      slope_denom = -sl2_denom;
    }

    return;
  }

  /*!
   * Calculate the intersection points with the given arc.
   * \param arc The arc to intersect.
   * \param ps The output intersection points. 
   *           This area must be allocated at the size of 4.
   * \param inter_list_P For caching purposes.
   * \pre The two arcs do not lie on the same conic.
   * \return The number of the actual intersection points.
   */
  int intersections_with (const Self& arc,
                          Point_2* ps
#ifdef CGAL_CONIC_ARC_USE_CACHING
                          ,std::list<Intersections> *inter_list_P = NULL
#endif
                          ) const
  {
    // The two conics must not be the same.
    CGAL_precondition (! has_same_base_conic(arc));

    // First make sure that (this->degree) is >= than (arc.degree).
    if ((arc._info & DEGREE_MASK) == DEGREE_2 && 
        (_info & DEGREE_MASK) == DEGREE_1)
    {
      return (arc.intersections_with (*this, ps
#ifdef CGAL_CONIC_ARC_USE_CACHING
                                      ,inter_list_P
#endif
                                      ));
    }

    // Deal with vertical segments.
    if (arc.is_vertical_segment())
    {
      if (is_vertical_segment())
      {
        // Two vertical segments intersect only if they overlap.
        return (0);
      }
      
      // Find all points on our arc that have the same x coordinate as
      // the other vertical segment.
      int         n_ys;
      Point_2     xps[2];
      int         j;
      int         n = 0;

      n_ys = get_points_at_x (arc._source, xps);
      
      for (j = 0; j < n_ys; j++)
      {
        // Store this point only if it is contained on the other arc.
        if (arc.contains_point(xps[j]))
        {
          ps[n] = Point_2 (xps[j].x(), xps[j].y(),
                           _conic_id, arc._conic_id);
          n++;
        }
      }