conic_arc_2.h

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

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

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

    // Find all intersection points between the two base conic curves.
    Point_2   ipts[4];             // The intersection points.
    int       n_points = 0;        // Their number.
    bool      calc_points = true;

#ifdef CGAL_CONIC_ARC_USE_CACHING
    Intersections inter;
    int           k;


    if (inter_list_P != NULL &&
        (_info & DEGREE_MASK) != DEGREE_1)
    {
      int           id1 = _conic_id;
      int           id2 = arc._conic_id;
    
      inter.id1 = id1 < id2 ? id1 : id2;
      inter.id2 = id1 > id2 ? id1 : id2;
    
      typename std::list<Intersections>::iterator iter;
      for (iter = inter_list_P->begin(); iter != inter_list_P->end(); iter++)
      {
        if ((*iter).id1 == inter.id1 && (*iter).id2 == inter.id2)
        {
          n_points = (*iter).n_points;
          for (k = 0; k < n_points; k++)
            ipts[k] = (*iter).ps[k];

          calc_points = false;
        }
      }
    }
#endif // (of ifdef CGAL_CONIC_ARC_USE_CACHING)

    if (calc_points)
    {
      // Find all potential x coordinates and y coordinates of the
      // intersection points.
      const CfNT _zero = 0;
      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.

      n_xs = _x_coordinates_of_intersection_points (_r, _s, _t, _u, _v, _w,
                                                    _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,
                                                    _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);

#ifdef CGAL_CONIC_ARC_USE_CACHING
      if (inter_list_P != NULL &&
          (_info & DEGREE_MASK) != DEGREE_1)
      {
        inter.n_points = n_points;        
        for (k = 0; k < n_points; k++)
          inter.ps[k] = ipts[k];

        inter_list_P->push_front(inter);
      }
    
#endif // (of ifdef CGAL_CONIC_ARC_USE_CACHING)
    }

    // Go over all intersection points between the two base conics and return
    // only those located on both arcs.
    int      n = 0;
    int      i;

    for (i = 0; i < n_points; i++)
    {
      // Check for an exact point.
      if (contains_point(ipts[i]) &&
          arc.contains_point(ipts[i]))
      {
        ps[n] = ipts[i];
        n++;
      }
    }

    return (n);
  }

  /*!
   * Check whether the two arcs overlap, and if so - compute the overlapping
   * portions.
   * \param arc The other conic arc.
   * \param ovlp_arc The output overlapping sub-arc.
   *                 This area should be allocated to the size of 2.
   * \return The number of overlapping sub-arcs.
   */
  int overlaps (const Self& arc,
                Self* ovlp_arcs) const
  {
    // Two arcs can overlap only if their base conics are identical.
    if (! this->has_same_base_conic (arc))
      return (0);

    // If the two arcs are completely equal, return one of them as the
    // overlapping arc.
    int       orient1 = _orient;
    int       orient2 = arc._orient;
    bool      same_or = (orient1 == orient2);
    bool      identical = false;

    if (orient1 == 0)
    {
      // That mean both arcs are really segments, so they are identical
      // if their endpoints are the same.
      if ((_source.equals(arc._source) && _target.equals(arc._target)) ||
          (_source.equals(arc._target) && _target.equals(arc._source)))
        identical = true;
    }
    else
    {
      // If those are really curves of degree 2, than the points curves
      // are identical only if their source and target are the same and the
      // orientation is the same, or vice-versa if the orientation is opposite.
      if ((same_or && 
           _source.equals(arc._source) && _target.equals(arc._target)) ||
          (!same_or && 
           _source.equals(arc._target) && _target.equals(arc._source)))
        identical = true;
    }

    if (identical)
    {
      ovlp_arcs[0] = arc;
      return (1);
    }

    // In case one of the arcs is a full conic, return the whole other conic.
    if (arc.is_full_conic())
    {
      ovlp_arcs[0] = *this;
      return (1);
    }
    else if (is_full_conic())
    {
      ovlp_arcs[0] = arc;
      return (1);
    }

    // In case the other arc has an opposite orientation, switch its source
    // and target (notice that in case of segments, when the orientation is 0,
    // we make sure the two segments have the same direction).
    const Point_2 *arc_sourceP;
    const Point_2 *arc_targetP;

    if (orient1 == 0)
      orient1 = (_source.compare_lex_xy(_target) 
                 == LARGER) ? 1 : -1;
    if (orient2 == 0)
      orient2 = (arc._source.compare_lex_xy(arc._target) 
                 == LARGER) ? 1 : -1;

    // Check the overlap cases:
    if (orient1 == orient2)
    {
      arc_sourceP = &(arc._source);
      arc_targetP = &(arc._target);
    }
    else
    {
      arc_sourceP = &(arc._target);
      arc_targetP = &(arc._source);
    }

    if (_is_strictly_between_endpoints(*arc_sourceP))
    {
      if (_is_strictly_between_endpoints(*arc_targetP))
      {
        // Check the next special case (when there are 2 overlapping arcs):
        if (arc._is_strictly_between_endpoints(_source) &&
            arc._is_strictly_between_endpoints(_target))
        {
          ovlp_arcs[0] = Self(*this,_source, *arc_targetP);
          ovlp_arcs[1] = Self(*this, *arc_sourceP, _target);
          return (2);
        }

        // Case 1 - *this:     +----------->     
        //            arc:       +=====>
        ovlp_arcs[0] = Self(*this, *arc_sourceP,*arc_targetP);
        return (1);
      }
      else
      {
        // Case 2 - *this:     +----------->     
        //            arc:               +=====>
        ovlp_arcs[0] = Self(*this, *arc_sourceP, _target);
        return (1);
      }
    }
    else if (_is_strictly_between_endpoints(*arc_targetP))
    {
      // Case 3 - *this:     +----------->     
      //            arc:   +=====>
      ovlp_arcs[0] = Self(*this, _source, *arc_targetP);
      return (1);
    }
    else if (arc._is_between_endpoints(_source) &&
             arc._is_between_endpoints(_target) &&
             (arc._is_strictly_between_endpoints(_source) ||
              arc._is_strictly_between_endpoints(_target)))
    {
      // Case 4 - *this:     +----------->     
      //            arc:   +================>
      ovlp_arcs[0] = *this;
      return (1);
    }
    
    // If we reached here, there are no overlaps:
    return (0);
  }
        
  /*!
   * Check whether the arc is facing up or facing down.
   * \return LARGER if the arcs is facing up, or SMALLER if it is facing down.
   *         If the arc is a line segment, EQUAL is returned.
   */
  Comparison_result facing () const
  {
    if ((_info & FACING_MASK) == 0)
      return (EQUAL);
    else if ((_info & FACING_UP) != 0)
      return (LARGER);
    else
      return (SMALLER);
  }

 protected:

  /*!
   * Set the properties of a conic arc (for the usage of the constructors).
   * \param comp_orient Should we compute the orientation of the given curve.
   */
  void _set (const bool& comp_orient)
  {
    // Initialize the information bits.
    _info = X_MON_UNDEFINED;

    // Set the orientation of conic arc.
    typename Cartesian<CfNT>::Conic_2   temp_conic (_r, _s, _t, _u, _v, _w);

    if (comp_orient)
    {
      // Compute the orientation.
      _orient = temp_conic.orientation();
    }
    else if (_orient != temp_conic.orientation())
    {
      // If the computed orientation does not match the current value,
      // multiply all conic coefficients by -1 (negate the curve).
      _r = - _r;
      _s = - _s;
      _t = - _t;
      _u = - _u;
      _v = - _v;
      _w = - _w;
    }

    // Find the degree and make sure the conic is not invalid.
    const CfNT _zero = 0;
    int        deg;
 
    if (CGAL_NTS compare(_r, _zero) != EQUAL || 
        CGAL_NTS compare(_s, _zero) != EQUAL ||
        CGAL_NTS compare(_t, _zero) != EQUAL)
    {
      // In case one of the coefficients of x^2,y^2 or xy is not zero, the
      // degree is 2.
      deg = 2;
    }
    else if (CGAL_NTS compare(_u, _zero) != EQUAL || 
             CGAL_NTS compare(_v, _zero) != EQUAL)
    {
      // In case of a line - the degree is 1.
      deg = 1;
      _orient = CGAL::COLLINEAR;
    }
    else
    {
      // Empty conic!
      deg = 0;
    }

    CGAL_precondition(deg > 0);

    if (deg == 0)
      // Invalid arc:
      return;

    // Store the degree information.
    _info = _info | deg;

    // In case the base conic is a hyperbola, build the hyperbolic data
    // (this happens when (4rs - t^2) < 0).
    const Comparison_result det = (CGAL_NTS compare(4*_r*_s, _t*_t));
    
    if (deg == 2 && det == SMALLER && _orient != CGAL::COLLINEAR)
      _build_hyperbolic_arc_data ();
    else
      _hyper_P = NULL;

    // In case of a non-degenerate parabola or a hyperbola, make sure 
    // the arc is not infinite.
    if (deg == 2 && det != LARGER && _orient != CGAL::COLLINEAR)
    {
      const CoNT       _two = 2;
      const Point_2    p_mid ((_source.x() + _target.x()) / _two,
                              (_source.y() + _target.y()) / _two);
      Point_2          ps[2];

      bool  finite_at_x = (get_points_at_x(p_mid, ps) > 0);
      bool  finite_at_y = (get_points_at_y(p_mid, ps) > 0);
 
      if (! finite_at_x || ! finite_at_y)
        // The arc is invalid:
        return;
    }

    // If we reached here, the conic arc is legal: Get a new id for the conic.
    _conic_id = _get_new_conic_id();

    _source.set_generating_conics (_conic_id);
    _target.set_generating_conics (_conic_id);

    // Check whether the conic is x-monotone.
    if (is_x_monotone())
    {
      _info = (_info & ~X_MON_UNDEFINED) | X_MONOTONE;

      // In case the conic is od degree 2, determine where is it facing.
      if (_orient != CGAL::COLLINEAR)
      {
        if (! _set_facing())
            // Invalid arc:
            return;
      }
    }
    else
    {
      _info = (_info & ~X_MON_UNDEFINED);
    }

    // Check if the arc is a vertical segment.
    if (_orient == CGAL::COLLINEAR)
    {
      // A vertical segment is contained in the degenerate conic: u*x + w = 0,
      // but it can also be a part of a line-pair -- in this case we just check
      // that the x-coordinates of the source and the target are the same.
      const CfNT _zero = 0;

      if (((_info & DEGREE_MASK) == 1 && 
           CGAL_NTS compare(_v, _zero) == EQUAL) ||
           _source.compare_x (_target) == EQUAL)
      {
        _info = _info | IS_VERTICAL_SEGMENT;
      }
    }

    // Mark that the arc is valid.
    _info = (_info | IS_VALID);

    return;
  }

  /*!
   * Set the properties of a conic arc that is really a full curve
   * (that is, an ellipse).
   * \param comp_orient Should we compute the orientation of the given curve.
   */
  void _set_full (const bool& comp_orient)
  {
    // Initialize the information bits.
    _info = 0;

    // Set the orientation of conic arc.
    typename Cartesian<CfNT>::Conic_2   temp_conic (_r, _s, _t, _u, _v, _w);

    if (comp_orient)
    {
      // Compute the orientation.
      _orient = temp_conic.orientation();
    }
    else if (_orient != temp_conic.orientation())
    {
      // If the computed orientation does not match the current value,
      // multiply all conic coefficients by -1 (negate the curve).
      _r = - _r;
      _s = - _s;
      _t = - _t;
      _u = - _u;
      _v = - _v;
      _w = - _w;
    }

    // Set the information: a full conic, which is obvoius