circle_segment_2.h

很多二维 三维几何计算算法 C++ 类库

  /// \name Accessors for circular arcs.
  //@{

  /*! Get the x-coordinate of the center of the supporting circle. */
  inline const NT& x0 () const
  {
    return (_first);
  }

  /*! Get the y-coordinate of the center of the supporting circle. */
  inline const NT& y0 () const
  {
    return (_second);
  }

  /*! Get the squared radius of the supporting circle. */
  inline const NT& sqr_r () const
  {
    return (_third);
  }

  /*!
   * Check if the circular arc lies on the upper half of the supporting circle.
   */
  inline bool _is_upper () const
  {
    Orientation  orient = orientation();
    bool         dir_right = ((_info & IS_DIRECTED_RIGHT_MASK) != 0);

    CGAL_precondition (orient != COLLINEAR);

    return ((orient == COUNTERCLOCKWISE && !dir_right) ||
            (orient == CLOCKWISE && dir_right));
  }
  //@}

  /// \name Accessors for line segments.
  //@{

  /*! Get the coefficient of x in the equation of the supporting line. */
  inline const NT& a () const
  {
    return (_first);
  }

  /*! Get the coefficient of y in the equation of the supporting line. */
  inline const NT& b () const
  {
    return (_second);
  }

  /*! Get the free coefficient in the equation of the supporting line. */
  inline const NT& c () const
  {
    return (_third);
  }
  //@}

  /// \name Auxiliary functions for the point_position predicate.
  //@{

  /*!
   * Check the position of a given point with respect to a line segment.
   */
  Comparison_result _line_point_position (const Point_2& p) const
  {
    // Check if we have a vertical segment.

    CGAL_precondition (is_in_x_range(p));

    Comparison_result    res;

    if (is_vertical())
    {
      // left() is the lower endpoint:
      res = CGAL::compare (p.y(), left().y());

      if (res != LARGER)
        return (res);

      // left() is the upper endpoint:
      res = CGAL::compare (p.y(), right().y());

      if (res != SMALLER)
        return (res);

      // p lies in the interior of the vertical segment:
      return (EQUAL);
    }

    // Compute the y-coordinate of the vertical projection of p onto the
    // supporting line.
    const CoordNT        y_proj = (a()*p.x() + c()) / (-b());

    return (CGAL::compare (p.y(), y_proj));
  }

  /*!
   * Check the position of a given point with respect to a circular arc.
   */
  Comparison_result _circ_point_position (const Point_2& p) const
  {
    Comparison_result   c_res = CGAL::compare (p.y(), y0());

    if (_is_upper())
    {
      // Check if p lies below the "equator" (while the arc lies above it):
      if (c_res == SMALLER)
        return (SMALLER);
    }
    else
    {
      // Check if p lies above the "equator" (while the arc lies below it):
      if (c_res == LARGER)
        return (LARGER);
    }

    // Check if p lies inside the supporting circle, namely we have to check
    // whether (p.x() - x0)^2 + (p.y() - y0)^2 < r^2:
    Comparison_result   res =
                         CGAL::compare (CGAL::square (p.x() - x0()),
                                        sqr_r() - CGAL::square (p.y() - y0()));

    if (res == EQUAL)
      // p lies on the circle:
      return (EQUAL);

    if (_is_upper())
    {
      // If p is inside the circle, it lies below the upper arc:
      return (res);
    }
    else
    {
      // If p is inside the circle, it lies above the lower arc:
      return (res == SMALLER ? LARGER : SMALLER);
    }
  }
  //@}

  /// \name Auxiliary functions for the compare_to_right predicate.
  //@{

  /*!
   * Compare two line segments to the right of their intersection point.
   */
  Comparison_result _lines_compare_to_right (const Self& cv,
                                             const Point_2& /* p */) const
  {
    if (_index() != 0 && _index() == cv._index())
      return (EQUAL);

    // Special treatment for vertical segments: a vertical segment is larger
    // than any other non-vertical segment.
    if (is_vertical())
    {
      if (cv.is_vertical())
        return (EQUAL);

      return (LARGER);
    }
    else if (cv.is_vertical())
    {
      return (SMALLER);
    }

    // Compare the slopes: -A1/B1 and -A2/B2. We actually negate the slopes
    // and swap the result.
    return (CGAL::compare (cv.a()/cv.b(), a()/b()));
  }

  /*!
   * Compare a circular arcs (this) and a line segment (cv) to the right of
   * their intersection point.
   */
  Comparison_result _circ_line_compare_to_right (const Self& cv,
                                                 const Point_2& p) const
  {
    // A vertical segment lies above any other circle to the right of p:
    if (cv.is_vertical())
      return (SMALLER);
    
    // We have to compare the slopes of the supporting circles and the
    // supporting line at p:
    //
    //    p.x() - x0(1)           A(2)
    //   ---------------  and  - ------
    //    y0(1) - p.y()           B(2)
    //
    const CGAL::Sign  sign_denom1 = CGAL::sign (y0() - p.y());

    // Check the case of a vertical tangent.
    if (sign_denom1 == ZERO)
    {
      // The arc lies above any line segment if it is an upper arc, or below
      // any segment if it is a lower arc.
      return (_is_upper() ? LARGER : SMALLER);
    }

    // Compare (p.x() - x0(1)) and (A(2)/B(2)*(p.y() - y0(1)).
    // Note that if the denominator is negative, we have to swap the result.
    const bool        swap_res = (sign_denom1 == NEGATIVE);
    Comparison_result slope_res = CGAL::compare (p.x() - x0(),
                                                 (p.y() - y0())*cv.a()/cv.b());

    if (slope_res != EQUAL)
    {
      if (swap_res)
        // Swap the comparison result, if necessary:
        slope_res = (slope_res == SMALLER) ? LARGER : SMALLER;
      
      return (slope_res);
    }

    // In this case we have a tangency point at p. If the circular arc is an
    // upper arc, it must lie below the tangent line, and if it is a lower arc
    // it must lie above the tangent line.
    return (_is_upper() ? SMALLER : LARGER);
  }

  /*!
   * Compare two circular arcs to the right of their intersection point.
   */
  Comparison_result _circs_compare_to_right (const Self& cv,
                                             const Point_2& p) const
  {
    if (_index() != 0 && _index() == cv._index())
    {
      // Check the case of comparing two circular arcs that originate from the
      // same supporting circle. Their comparison result is not EQUAL only if
      // one is an upper arc and the other is a lower arc.
      if (_is_upper() && ! cv._is_upper())
        return (LARGER);
      else if (! _is_upper() && cv._is_upper())
        return (SMALLER);
      else
        return (EQUAL);
    }

    // We have to compare the slopes of the two supporting circles at p:
    //
    //    p.x() - x0(1)         p.x() - x0(2)
    //   ---------------  and  ---------------
    //    y0(1) - p.y()         y0(2) - p.y()
    //
    const CGAL::Sign  sign_numer1 = CGAL::sign (p.x() - x0());
    const CGAL::Sign  sign_denom1 = CGAL::sign (y0() - p.y());
    const CGAL::Sign  sign_numer2 = CGAL::sign (p.x() - cv.x0());
    const CGAL::Sign  sign_denom2 = CGAL::sign (cv.y0() - p.y());

    // Check the case of vertical tangents.
    if (sign_denom1 == ZERO)
    {
      if (sign_denom2 == ZERO)
      {
        if (_is_upper())
        {
          if (cv._is_upper())
          {
            // The two circles have a vertical tangent:
            // The one with a larger radius is above the other.
            return (CGAL::compare (sqr_r(), cv.sqr_r()));
          }
          else
          {
            // The other curve is directed downwards:
            return (LARGER);
          }
        }
        else
        {
          if (cv._is_upper())
          {
            // The other curve is directed upwards:
            return (SMALLER);
          }
          else
          {
            // The two circles have a vertical tangent:
            // The one with a smaller radius is above the other.
            return (CGAL::compare (cv.sqr_r(), sqr_r()));
          }
        }
      }

      // The other arc does not have a vertical tangent.
      return (_is_upper() ? LARGER : SMALLER);
    }
    else if (sign_denom2 == ZERO)
    {
      return (cv._is_upper() ? SMALLER : LARGER);
    }

    // Try to act according to the slope signs.
    CGAL::Sign   sign_slope1;
    CGAL::Sign   sign_slope2;

    if (sign_numer1 == sign_denom1)
      sign_slope1 = POSITIVE;
    else if (sign_numer1 == ZERO)
      sign_slope1 = ZERO;
    else
      sign_slope1 = NEGATIVE;

    if (sign_numer2 == sign_denom2)
      sign_slope2 = POSITIVE;
    else if (sign_numer2 == ZERO)
      sign_slope2 = ZERO;
    else
      sign_slope2 = NEGATIVE;

    if ((sign_slope1 == POSITIVE && sign_slope2 != POSITIVE) ||
        (sign_slope1 == ZERO && sign_slope2 == NEGATIVE))
      return (LARGER);

    if ((sign_slope2 == POSITIVE && sign_slope1 != POSITIVE) ||
        (sign_slope2 == ZERO && sign_slope1 == NEGATIVE))
      return (SMALLER);

    // Compare the slopes of the two tangents to the circles.
    Comparison_result  slope_res;
    
    if (sign_slope1 == ZERO && sign_slope2 == ZERO)
    {
      // Special case were both circles have a horizontal tangent:
      slope_res = EQUAL;
    }
    else
    {
      // Actually compare the slopes.    
      const bool    swap_res = (sign_denom1 != sign_denom2);
      const CoordNT A = (cv.y0() - y0())*p.x() + (y0()*cv.x0() - cv.y0()*x0());
      const CoordNT B = (cv.x0() - x0())*p.y();
     
      slope_res = CGAL::compare (A, B);

      if (slope_res != EQUAL && swap_res)
      {
        // Swap the comparison result, if necessary:
        slope_res = (slope_res == SMALLER) ? LARGER : SMALLER;
      }
    }

    // In case the two circles have different tangent slopes at p:
    if (slope_res != EQUAL)
      return (slope_res);

    // In this case we have a tangency point at p.
    if (_is_upper())
    {
      if (cv._is_upper())
      {
        // The circle with a larger radius is above the other.
        return (CGAL::compare (sqr_r(), cv.sqr_r()));
      }
      else
      {
        // The other curve is above our curve:
        return (SMALLER);
      }
    }
    else
    {
      if (cv._is_upper())
      {
        // Out curve is above the other curve:
        return (LARGER);
      }
      else
      {
        // The circle with a smaller radius is above the other.
        return (CGAL::compare (cv.sqr_r(), sqr_r()));
      }
    }
  }
  //@}

  /// \name Auxiliary functions for the compare_to_left predicate.
  //@{

  /*!
   * Compare two line segments to the left of their intersection point.
   */
  Comparison_result _lines_compare_to_left (const Self& cv,
                                            const Point_2& ) const
  {
    if (_index() != 0 && _index() == cv._index())
      return (EQUAL);

    // Special treatment for vertical segments: a vertical segment is smaller
    // than any other non-vertical segment.
    if (is_vertical())
    {
      if (cv.is_vertical())
        return (EQUAL);

      return (SMALLER);
    }
    else if (cv.is_vertical())
    {
      return (LARGER);
    }

    // Compare the slopes: -A1/B1 and -A2/B2 and swap the result.
    //  We actually negate the slopes and compare them.
    return (CGAL::compare (a()/b(), cv.a()/cv.b()));
  }

  /*!
   * Compare a circular arcs (this) and a line segment (cv) to the left of
   * their intersection point.
   */
  Comparison_result _circ_line_compare_to_left (const Self& cv,
                                                const Point_2& p) const
  {
    // A vertical segment lies below any other circle to the left of p:
    if (cv.is_vertical())
      return (LARGER);
    
    // We have to compare the slopes of the supporting circles and the
    // supporting line at p, and return the swapped result:
    //
    //    p.x() - x0(1)           A(2)
    //   ---------------  and  - ------
    //    y0(1) - p.y()           B(2)
    //
    const CGAL::Sign  sign_denom1 = CGAL::sign (y0() - p.y());

    // Check the case of a vertical tangent.
    if (sign_denom1 == ZERO)
    {
      // The arc lies above any line segment if it is an upper arc, or below
      // any segment if it is a lower arc.
      return (_is_upper() ? LARGER : SMALLER);
    }

    // Compare (p.x() - x0(1)) and (A(2)/B(2)*(p.y() - y0(1)).
    // Note that if the denominator is negative, we have to swap the result.
    const bool        swap_res = (sign_denom1 == NEGATIVE);
    Comparison_result slope_res = CGAL::compare (p.x() - x0(),
                                                 (p.y() - y0())*cv.a()/cv.b());

    if (slope_res != EQUAL)
    {
      if (swap_res)
        // Swap the comparison result, if necessary:
        slope_res = (slope_res == SMALLER) ? LARGER : SMALLER;
      
      // Swap at any case to get the position to the left:
      return ((slope_res == SMALLER) ? LARGER : SMALLER);
    }

    // In this case we have a tangency point at p. If the circular arc is an
    // upper arc, it must lie below the tangent line, and if it is a lower arc
    // it must lie above the tangent line.
    return (_is_upper() ? SMALLER : LARGER);
  }

  /*!
   * Compare the two arcs to the left of their intersection point.