conic_arc_2_core.h

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

  {
    // 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 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*R - 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*R;

      _orient = CGAL::CLOCKWISE;
    }

    // Make sure the circle contains the two endpoints on its boundary.
    CGAL_precondition(_conic_has_on_boundary(source));
    CGAL_precondition(_conic_has_on_boundary(target));

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

    // Prepare the auxiliary data structure.
    Circular_arc_data    *circ_data_P = new Circular_arc_data;

    circ_data_P->x0 = CoNT(x0);
    circ_data_P->y0 = CoNT(y0);
    circ_data_P->r = CoNT(R);

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

  /*!
   * Set a circular arc that corresponds to the full circle:
   *   C: (x - x0)^2 + (y - y0)^2 = R^2
   */ 
  Conic_arc_2 (const CfNT& x0, const CfNT& y0,
	       const CfNT& R)
  {
    // 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 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*R;

    _orient = CGAL::CLOCKWISE;

    // Prepare the auxiliary data structure.
    Circular_arc_data    *circ_data_P = new Circular_arc_data;

    circ_data_P->x0 = CoNT(x0);
    circ_data_P->y0 = CoNT(y0);
    circ_data_P->r = CoNT(R);

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

  /*!
   * Construct a circular arc from the given three points, specified by the
   * coordinates (x1,y1), (x2,y2) and (x3, y3).
   * (x1,y1) is the arc source and (x3,y3) is the arc target.
   * \pre The three points must not be collinear.
   */
  Conic_arc_2 (const CfNT& x1, const CfNT& y1,
	       const CfNT& x2, const CfNT& y2,
	       const CfNT& x3, const CfNT& y3,
	       const bool& ) :
    _source(CoNT(x1),CoNT(y1)),
    _target(CoNT(x3),CoNT(y3)),
    _info(X_MON_UNDEFINED)
  {
    const CfNT _zero = 0;
    const CfNT _two  = 2;
    
    // Make sure that the source and the taget are not the same.
    CGAL_precondition(_source != _target);      

    // 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.
    CGAL_precondition_code(
    const bool points_collinear = (D == _zero);
    );
    CGAL_precondition(!points_collinear);

    // 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));

    // 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 Kernel                  ker;
    typename 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;

    // Prepare the auxiliary data structure.
    Circular_arc_data    *circ_data_P = new Circular_arc_data;

    circ_data_P->x0 = CoNT(Nx) / CoNT(D);
    circ_data_P->y0 = CoNT(Ny) / CoNT(D);
    circ_data_P->r = 
      CGAL::sqrt (CoNT((D*x2 - Nx)*(D*x2 - Nx) + (D*y2 - Ny)*(D*y2 - Ny)) /
		  CoNT(D*D));

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

  /*!
   * Destructor.
   */
  virtual ~Conic_arc_2 ()
  {
    if ((_info & IS_HYPERBOLA) != 0)
      delete _data.hyper_P;
    else if ((_info & IS_CIRCLE) != 0)
      delete _data.circ_P;
    _data.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 ((_info & IS_HYPERBOLA) != 0)
      delete _data.hyper_P;
    else if ((_info & IS_CIRCLE) != 0)
      delete _data.circ_P;
    _data.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 or circular arcs.
    if ((arc._info & IS_HYPERBOLA) != 0)
    {
      _data.hyper_P = new Hyperbolic_arc_data (*(arc._data.hyper_P));
    }
    else if ((arc._info & IS_CIRCLE) != 0)
    {
      _data.circ_P = new Circular_arc_data (*(arc._data.circ_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);}

  /*!
   * 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);
  }

  /*!
   * 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);
    
    // 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 ((_info & IS_CIRCLE) != 0);
  }
  
  /*!
   * Check whether the arc is a line segment.
   * \return (true) if the underlying conic curve is of degree 1.
   */
  bool is_segment () const
  {
    return ((_info & DEGREE_MASK) == 1);
  }

  /*!
   * Check whether the arc is a vertical segment.
   * \return (true) if the arc is a vertical segment.
   */
  bool is_vertical_segment () const
  {
    // A vertical segment is contained in the degenerate conic: u*x + w = 0.
    const CfNT _zero = 0;

    return ((_info & DEGREE_MASK) == 1 && 
	    CGAL_NTS compare(_v, _zero) == EQUAL);
  }

  /*!
   * 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);
    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);