kernel_ftc3.h

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

// Copyright (c) 2000  Utrecht University (The Netherlands),
// ETH Zurich (Switzerland), Freie Universitaet Berlin (Germany),
// INRIA Sophia-Antipolis (France), Martin-Luther-University Halle-Wittenberg
// (Germany), Max-Planck-Institute Saarbruecken (Germany), RISC Linz (Austria),
// and Tel-Aviv University (Israel).  All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Cartesian_kernel/include/CGAL/predicates/kernel_ftC3.h $
// $Id: kernel_ftC3.h 32776 2006-07-30 13:02:57Z spion $
// 
//
// Author(s)     : Herve Bronnimann, Sylvain Pion

#ifndef CGAL_PREDICATES_KERNEL_FTC3_H
#define CGAL_PREDICATES_KERNEL_FTC3_H

#include <CGAL/predicates/sign_of_determinant.h>
#include <CGAL/predicates/kernel_ftC2.h>
#include <CGAL/constructions/kernel_ftC3.h>

CGAL_BEGIN_NAMESPACE

template < class FT >
inline
typename Equal_to<FT>::result_type
parallelC3(const FT &v1x, const FT &v1y, const FT &v1z,
           const FT &v2x, const FT &v2y, const FT &v2z)
{
  return sign_of_determinant2x2(v1x, v2x, v1y, v2y) == ZERO
      && sign_of_determinant2x2(v1x, v2x, v1z, v2z) == ZERO
      && sign_of_determinant2x2(v1y, v2y, v1z, v2z) == ZERO;
}

template < class FT >
typename Equal_to<FT>::result_type
parallelC3(const FT &s1sx, const FT &s1sy, const FT &s1sz,
           const FT &s1tx, const FT &s1ty, const FT &s1tz,
           const FT &s2sx, const FT &s2sy, const FT &s2sz,
           const FT &s2tx, const FT &s2ty, const FT &s2tz)
{
  // NB : Could be made slightly more efficient by computing the z differences
  // only when they are needed.
  FT v1x = s1tx - s1sx;
  FT v1y = s1ty - s1sy;
  FT v1z = s1tz - s1sz;
  FT v2x = s2tx - s2sx;
  FT v2y = s2ty - s2sy;
  FT v2z = s2tz - s2sz;
  return parallelC3(v1x, v1y, v1z, v2x, v2y, v2z);
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Compare<FT>::result_type
compare_lexicographically_xyzC3(const FT &px, const FT &py, const FT &pz,
                                const FT &qx, const FT &qy, const FT &qz)
{
  typedef typename Compare<FT>::result_type Cmp;
  Cmp c = CGAL_NTS compare(px, qx);
  if (c != EQUAL) return c;
  c = CGAL_NTS compare(py, qy);
  if (c != EQUAL) return c;
  return CGAL_NTS compare(pz, qz);
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Equal_to<FT>::result_type
strict_dominanceC3(const FT &px, const FT &py, const FT &pz,
		   const FT &qx, const FT &qy, const FT &qz)
{
  return CGAL_NTS compare(px, qx) == LARGER &&
	 CGAL_NTS compare(py, qy) == LARGER &&
	 CGAL_NTS compare(pz, qz) == LARGER;
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Equal_to<FT>::result_type
dominanceC3(const FT &px, const FT &py, const FT &pz,
	    const FT &qx, const FT &qy, const FT &qz)
{
  return CGAL_NTS compare(px, qx) != SMALLER && 
	 CGAL_NTS compare(py, qy) != SMALLER &&
	 CGAL_NTS compare(pz, qz) != SMALLER;
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Equal_to<FT>::result_type
collinearC3(const FT &px, const FT &py, const FT &pz,
            const FT &qx, const FT &qy, const FT &qz,
            const FT &rx, const FT &ry, const FT &rz)
{
  FT dpx = px-rx;
  FT dqx = qx-rx;
  FT dpy = py-ry;
  FT dqy = qy-ry;
  if (sign_of_determinant2x2(dpx, dqx, dpy, dqy) != ZERO)
      return false;
  FT dpz = pz-rz;
  FT dqz = qz-rz;
  return sign_of_determinant2x2(dpx, dqx, dpz, dqz) == ZERO
      && sign_of_determinant2x2(dpy, dqy, dpz, dqz) == ZERO;
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Same_uncertainty_nt<Orientation, FT>::type
orientationC3(const FT &px, const FT &py, const FT &pz,
              const FT &qx, const FT &qy, const FT &qz,
              const FT &rx, const FT &ry, const FT &rz,
              const FT &sx, const FT &sy, const FT &sz)
{
  return enum_cast<Orientation>(sign_of_determinant3x3<FT>(qx-px,rx-px,sx-px,
                                                           qy-py,ry-py,sy-py,
                                                           qz-pz,rz-pz,sz-pz));
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Same_uncertainty_nt<Orientation, FT>::type
orientationC3(const FT &ux, const FT &uy, const FT &uz,
              const FT &vx, const FT &vy, const FT &vz,
              const FT &wx, const FT &wy, const FT &wz)
{
  return enum_cast<Orientation>(sign_of_determinant3x3(ux, vx, wx,
                                                       uy, vy, wy,
                                                       uz, vz, wz));
}

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

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Same_uncertainty_nt<Orientation, FT>::type
coplanar_orientationC3(const FT &px, const FT &py, const FT &pz,
                       const FT &qx, const FT &qy, const FT &qz,
                       const FT &rx, const FT &ry, const FT &rz,
                       const FT &sx, const FT &sy, const FT &sz)
{
  typedef typename Same_uncertainty_nt<Orientation, FT>::type  Ori;
  Ori oxy_pqr = orientationC2(px,py,qx,qy,rx,ry);
  if (oxy_pqr != COLLINEAR)
      return enum_cast<Orientation>( oxy_pqr * orientationC2(px,py,qx,qy,sx,sy));

  Ori oyz_pqr = orientationC2(py,pz,qy,qz,ry,rz);
  if (oyz_pqr != COLLINEAR)
      return enum_cast<Orientation>( oyz_pqr * orientationC2(py,pz,qy,qz,sy,sz));

  Ori oxz_pqr = orientationC2(px,pz,qx,qz,rx,rz);
  CGAL_kernel_assertion(oxz_pqr != COLLINEAR);
  return enum_cast<Orientation>( oxz_pqr * orientationC2(px,pz,qx,qz,sx,sz));
}

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Same_uncertainty_nt<Orientation, FT>::type
coplanar_orientationC3(const FT &px, const FT &py, const FT &pz,
                       const FT &qx, const FT &qy, const FT &qz,
                       const FT &rx, const FT &ry, const FT &rz)
{
  typedef typename Same_uncertainty_nt<Orientation, FT>::type  Ori;
  Ori oxy_pqr = orientationC2(px,py,qx,qy,rx,ry);
  if (oxy_pqr != COLLINEAR)
      return oxy_pqr;

  Ori oyz_pqr = orientationC2(py,pz,qy,qz,ry,rz);
  if (oyz_pqr != COLLINEAR)
      return oyz_pqr;

  return orientationC2(px,pz,qx,qz,rx,rz);
}

template < class FT >
CGAL_KERNEL_LARGE_INLINE
typename Same_uncertainty_nt<Bounded_side, FT>::type
coplanar_side_of_bounded_circleC3(const FT &px, const FT &py, const FT &pz,
                                  const FT &qx, const FT &qy, const FT &qz,
                                  const FT &rx, const FT &ry, const FT &rz,
                                  const FT &tx, const FT &ty, const FT &tz)
{
  // The approach is to compute side_of_bounded_sphere(p,q,r,t+v,t),
  // with v = pq ^ pr.
  // Note : since the circle defines the orientation of the plane, it can not
  // be considered oriented.
  FT ptx = px - tx;
  FT pty = py - ty;
  FT ptz = pz - tz;
  FT pt2 = CGAL_NTS square(ptx) + CGAL_NTS square(pty) + CGAL_NTS square(ptz);
  FT qtx = qx - tx;
  FT qty = qy - ty;
  FT qtz = qz - tz;
  FT qt2 = CGAL_NTS square(qtx) + CGAL_NTS square(qty) + CGAL_NTS square(qtz);
  FT rtx = rx - tx;
  FT rty = ry - ty;
  FT rtz = rz - tz;
  FT rt2 = CGAL_NTS square(rtx) + CGAL_NTS square(rty) + CGAL_NTS square(rtz);
  FT pqx = qx - px;
  FT pqy = qy - py;
  FT pqz = qz - pz;
  FT prx = rx - px;
  FT pry = ry - py;
  FT prz = rz - pz;
  FT vx = pqy*prz - pqz*pry;
  FT vy = pqz*prx - pqx*prz;
  FT vz = pqx*pry - pqy*prx;
  FT v2 = CGAL_NTS square(vx) + CGAL_NTS square(vy) + CGAL_NTS square(vz);
  return enum_cast<Bounded_side>(sign_of_determinant4x4(ptx,pty,ptz,pt2,
                                                        rtx,rty,rtz,rt2,
                                                        qtx,qty,qtz,qt2,
                                                        vx,vy,vz,v2));
}

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

template < class FT >
CGAL_KERNEL_MEDIUM_INLINE
typename Equal_to<FT>::result_type
collinear_are_strictly_ordered_along_lineC3(
     const FT &px, const FT &py, const FT &pz,
     const FT &qx, const FT &qy, const FT &qz,
     const FT &rx, const FT &ry, const FT &rz)
{
  if (px < qx) return (qx < rx);
  if (qx < px) return (rx < qx);
  if (py < qy) return (qy < ry);
  if (qy < py) return (ry < qy);
  if (pz < qz) return (qz < rz);
  if (qz < pz) return (rz < qz);
  return false; // p==q
}

template < class FT >