kernel_ftc2.h

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

   if (CGAL_NTS is_zero(l2b)) return SMALLER;
   int l1_sign = - CGAL_NTS sign(l1a) * CGAL_NTS sign(l1b);
   int l2_sign = - CGAL_NTS sign(l2a) * CGAL_NTS sign(l2b);

   if (l1_sign < l2_sign) return SMALLER;
   if (l1_sign > l2_sign) return LARGER;

   if (l1_sign > 0)
     return CGAL_NTS compare ( CGAL_NTS abs(l1a * l2b),
			       CGAL_NTS abs(l2a * l1b) );

   return CGAL_NTS compare ( CGAL_NTS abs(l2a * l1b),
			     CGAL_NTS abs(l1a * l2b) );
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Compare<FT>::result_type
compare_slopesC2(const FT &s1_src_x, const FT &s1_src_y, const FT &s1_tgt_x, 
                 const FT &s1_tgt_y, const FT &s2_src_x, const FT &s2_src_y, 
                 const FT &s2_tgt_x, const FT &s2_tgt_y) 
{
   typedef typename Compare<FT>::result_type  Cmp;
   typedef typename Sgn<FT>::result_type      Sg;
   Cmp cmp_y1 = CGAL_NTS compare(s1_src_y, s1_tgt_y);
   if (cmp_y1 == EQUAL) // horizontal
   {
      Cmp cmp_x2 = CGAL_NTS compare(s2_src_x, s2_tgt_x);

      if (cmp_x2 == EQUAL) return SMALLER;
      return enum_cast<Comparison_result>(- CGAL_NTS sign((s2_src_y - s2_tgt_y) *
                                                          (s2_src_x - s2_tgt_x)) );
   }

   Cmp cmp_y2 = CGAL_NTS compare(s2_src_y, s2_tgt_y);
   if (cmp_y2 == EQUAL)
   {
      Cmp cmp_x1 = CGAL_NTS compare(s1_src_x, s1_tgt_x);

      if (cmp_x1 == EQUAL) return LARGER;
      return enum_cast<Comparison_result>( CGAL_NTS sign((s1_src_y - s1_tgt_y) *
                                                         (s1_src_x - s1_tgt_x)) );
   }

   Cmp cmp_x1 = CGAL_NTS compare(s1_src_x, s1_tgt_x);
   Cmp cmp_x2 = CGAL_NTS compare(s2_src_x, s2_tgt_x);

   if (cmp_x1 == EQUAL) return cmp_x2 == EQUAL ? EQUAL : LARGER;

   if (cmp_x2 == EQUAL) return SMALLER;

   FT s1_xdiff = s1_src_x - s1_tgt_x;
   FT s1_ydiff = s1_src_y - s1_tgt_y;
   FT s2_xdiff = s2_src_x - s2_tgt_x;
   FT s2_ydiff = s2_src_y - s2_tgt_y;
   Sg s1_sign = enum_cast<Sign>(CGAL_NTS sign(s1_ydiff) * CGAL_NTS sign(s1_xdiff));
   Sg s2_sign = enum_cast<Sign>(CGAL_NTS sign(s2_ydiff) * CGAL_NTS sign(s2_xdiff));

   if (s1_sign < s2_sign) return SMALLER;
   if (s1_sign > s2_sign) return LARGER;

   if (s1_sign > 0)
     return CGAL_NTS compare( CGAL_NTS abs(s1_ydiff * s2_xdiff),
                              CGAL_NTS abs(s2_ydiff * s1_xdiff));

   return CGAL_NTS compare( CGAL_NTS abs(s2_ydiff * s1_xdiff),
                            CGAL_NTS abs(s1_ydiff * s2_xdiff));
}


#if 0
// Unused, undocumented, un-functorized.
template < class FT >
inline
typename Compare<FT>::result_type
compare_deltax_deltayC2(const FT &px, const FT &qx,
                        const FT &ry, const FT &sy)
{
  return CGAL_NTS compare(CGAL_NTS abs(px-qx), CGAL_NTS abs(ry-sy));
}
#endif

template < class FT >
inline
typename Compare<FT>::result_type
compare_lexicographically_xyC2(const FT &px, const FT &py,
                               const FT &qx, const FT &qy)
{
  typename Compare<FT>::result_type c = CGAL_NTS compare(px,qx);
  return (c != EQUAL) ? c : CGAL_NTS compare(py,qy);
}

template < class FT >
inline
typename Same_uncertainty_nt<Orientation, FT>::type
orientationC2(const FT &px, const FT &py,
              const FT &qx, const FT &qy,
              const FT &rx, const FT &ry)
{
  return enum_cast<Orientation>(sign_of_determinant2x2(qx-px, qy-py,
                                                       rx-px, ry-py));
}

template < class FT >
inline
typename Same_uncertainty_nt<Orientation, FT>::type
orientationC2(const FT &ux, const FT &uy, const FT &vx, const FT &vy)
{
  return enum_cast<Orientation>(sign_of_determinant2x2(ux, uy, vx, vy));
}

template < class FT >
inline
typename Same_uncertainty_nt<Angle, FT>::type
angleC2(const FT &px, const FT &py,
        const FT &qx, const FT &qy,
        const FT &rx, const FT &ry)
{
  return enum_cast<Angle>(CGAL_NTS sign((px-qx)*(rx-qx)+(py-qy)*(ry-qy)));
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Equal_to<FT>::result_type
collinear_are_ordered_along_lineC2(const FT &px, const FT &py,
                                   const FT &qx, const FT &qy,
                                   const FT &rx, const FT &ry)
{
  if (px < qx) return !(rx < qx);
  if (qx < px) return !(qx < rx);
  if (py < qy) return !(ry < qy);
  if (qy < py) return !(qy < ry);
  return true; // p==q
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Equal_to<FT>::result_type
collinear_are_strictly_ordered_along_lineC2(const FT &px, const FT &py,
                                            const FT &qx, const FT &qy,
                                            const FT &rx, const FT &ry)
{
  if (px < qx) return (qx < rx);
  if (qx < px) return (rx < qx);
  if (py < qy) return (qy < ry);
  if (qy < py) return (ry < qy);
  return false;
}

template < class FT >
CGAL_KERNEL_LARGE_INLINE
typename Same_uncertainty_nt<Oriented_side, FT>::type
side_of_oriented_circleC2(const FT &px, const FT &py,
                          const FT &qx, const FT &qy,
                          const FT &rx, const FT &ry,
                          const FT &tx, const FT &ty)
{
  // Oriented_side(
  //  sign_of_determinant4x4(px, py, px*px + py*py, 1,
  //                         qx, qy, qx*qx + qy*qy, 1,
  //                         rx, ry, rx*rx + ry*ry, 1,
  //                         tx, ty, tx*tx + ty*ty, 1));
  // We first translate so that p is the new origin.
  FT qpx = qx-px;
  FT qpy = qy-py;
  FT rpx = rx-px;
  FT rpy = ry-py;
  FT tpx = tx-px;
  FT tpy = ty-py;
// The usual 3x3 formula can be simplified a little bit to a 2x2.
//         - sign_of_determinant3x3(qpx, qpy, square(qpx) + square(qpy),
//                                  rpx, rpy, square(rpx) + square(rpy),
//                                  tpx, tpy, square(tpx) + square(tpy)));
  return enum_cast<Oriented_side>(sign_of_determinant2x2<FT>(
                             qpx*tpy - qpy*tpx, tpx*(tx-qx) + tpy*(ty-qy),
                             qpx*rpy - qpy*rpx, rpx*(rx-qx) + rpy*(ry-qy)));
}

template < class FT >
CGAL_KERNEL_LARGE_INLINE
typename Same_uncertainty_nt<Bounded_side, FT>::type
side_of_bounded_circleC2(const FT &px, const FT &py,
                         const FT &qx, const FT &qy,
                         const FT &rx, const FT &ry,
                         const FT &tx, const FT &ty)
{
  return enum_cast<Bounded_side>( side_of_oriented_circleC2(px,py,qx,qy,rx,ry,tx,ty)
                                 * orientationC2(px,py,qx,qy,rx,ry) );
}

template < class FT >
CGAL_KERNEL_LARGE_INLINE
typename Same_uncertainty_nt<Bounded_side, FT>::type
side_of_bounded_circleC2(const FT &px, const FT &py,
                         const FT &qx, const FT &qy,
                         const FT &tx, const FT &ty)
{
  // Returns whether T lies inside or outside the circle which diameter is PQ.
  return enum_cast<Bounded_side>(
                      CGAL_NTS compare((tx-px)*(qx-tx), (ty-py)*(ty-qy)) );
}

template < class FT >
inline
typename Compare<FT>::result_type
cmp_dist_to_pointC2(const FT &px, const FT &py,
                    const FT &qx, const FT &qy,
                    const FT &rx, const FT &ry)
{
  return CGAL_NTS compare(squared_distanceC2(px,py,qx,qy),
                          squared_distanceC2(px,py,rx,ry));
}

template < class FT >
inline
typename Equal_to<FT>::result_type
has_larger_dist_to_pointC2(const FT &px, const FT &py,
                           const FT &qx, const FT &qy,
                           const FT &rx, const FT &ry)
{
  return cmp_dist_to_pointC2(px,py,qx,qy,rx,ry) == LARGER;
}

template < class FT >
inline
typename Equal_to<FT>::result_type
has_smaller_dist_to_pointC2(const FT &px, const FT &py,
                            const FT &qx, const FT &qy,
                            const FT &rx, const FT &ry)
{
  return cmp_dist_to_pointC2(px,py,qx,qy,rx,ry) == SMALLER;
}

template < class FT >
inline
typename Compare<FT>::result_type
cmp_signed_dist_to_directionC2(const FT &la, const FT &lb,
                               const FT &px, const FT &py,
                               const FT &qx, const FT &qy)
{
  return CGAL_NTS compare(scaled_distance_to_directionC2(la,lb,px,py),
                          scaled_distance_to_directionC2(la,lb,qx,qy));
}

template < class FT >
inline
typename Equal_to<FT>::result_type
has_larger_signed_dist_to_directionC2(const FT &la, const FT &lb,
                                      const FT &px, const FT &py,
                                      const FT &qx, const FT &qy)
{
  return cmp_signed_dist_to_directionC2(la,lb,px,py,qx,qy) == LARGER;
}

template < class FT >
inline
typename Equal_to<FT>::result_type
has_smaller_signed_dist_to_directionC2(const FT &la, const FT &lb,
                                       const FT &px, const FT &py,
                                       const FT &qx, const FT &qy)
{
  return cmp_signed_dist_to_directionC2(la,lb,px,py,qx,qy) == SMALLER;
}

template <class FT>
inline
typename Compare<FT>::result_type
cmp_signed_dist_to_lineC2(const FT &px, const FT &py,
                          const FT &qx, const FT &qy,
                          const FT &rx, const FT &ry,
                          const FT &sx, const FT &sy)
{
  return CGAL_NTS compare(scaled_distance_to_lineC2(px,py,qx,qy,rx,ry),
                          scaled_distance_to_lineC2(px,py,qx,qy,sx,sy));
}

template <class FT>
inline
typename Equal_to<FT>::result_type
has_larger_signed_dist_to_lineC2(const FT &px, const FT &py,
                                 const FT &qx, const FT &qy,
                                 const FT &rx, const FT &ry,
                                 const FT &sx, const FT &sy)
{
  return cmp_signed_dist_to_lineC2(px,py,qx,qy,rx,ry,sx,sy) == LARGER;
}

template <class FT>
inline
typename Equal_to<FT>::result_type
has_smaller_signed_dist_to_lineC2(const FT &px, const FT &py,
                                  const FT &qx, const FT &qy,
                                  const FT &rx, const FT &ry,
                                  const FT &sx, const FT &sy)
{
  return cmp_signed_dist_to_lineC2(px,py,qx,qy,rx,ry,sx,sy) == SMALLER;
}

template <class FT>
inline
typename Same_uncertainty_nt<Oriented_side, FT>::type
side_of_oriented_lineC2(const FT &a, const FT &b, const FT &c,
                        const FT &x, const FT &y)
{
  return enum_cast<Oriented_side>(CGAL_NTS sign(a*x+b*y+c));
}

CGAL_END_NAMESPACE

#endif  // CGAL_PREDICATES_KERNEL_FTC2_H