function_objects.h

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

// Copyright (c) 1999-2004  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.
//
// $Source: /CVSROOT/CGAL/Packages/H2/include/CGAL/Homogeneous/function_objects.h,v $
// $Revision: 1.40 $ $Date: 2004/08/11 14:37:09 $
// $Name:  $
//
// Author(s)     : Stefan Schirra, Sylvain Pion, Michael Hoffmann

#ifndef CGAL_HOMOGENEOUS_FUNCTION_OBJECTS_H
#define CGAL_HOMOGENEOUS_FUNCTION_OBJECTS_H

#include <CGAL/Kernel/function_objects.h>
#include <CGAL/Cartesian/function_objects.h>

CGAL_BEGIN_NAMESPACE

namespace HomogeneousKernelFunctors {

  using namespace CommonKernelFunctors;

  // For lazyness...
  using CartesianKernelFunctors::Are_parallel_2;
  using CartesianKernelFunctors::Are_parallel_3;
  using CartesianKernelFunctors::Compute_squared_area_3;
  using CartesianKernelFunctors::Collinear_3;
  using CartesianKernelFunctors::Construct_line_3;

  template <typename K>
  class Angle_2
  {
    typedef typename K::Point_2             Point_2;
    typedef typename K::Construct_vector_2  Construct_vector_2;
    Construct_vector_2 c;
  public:
    typedef Angle            result_type;
    typedef Arity_tag< 3 >   Arity;
  
    Angle_2() {}
    Angle_2(const Construct_vector_2& c_) : c(c_) {}

    Angle
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    { return (Angle) CGAL_NTS sign(c(q,p) * c(q,r)); } 
    // FIXME: scalar product
  };

  template <typename K>
  class Angle_3
  {
    typedef typename K::Point_3             Point_3;
    typedef typename K::Construct_vector_3  Construct_vector_3;
    Construct_vector_3 c;
  public:
    typedef Angle            result_type;
    typedef Arity_tag< 3 >   Arity;

    Angle_3() {}
    Angle_3(const Construct_vector_3& c_) : c(c_) {}

    Angle
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    { return (Angle) CGAL_NTS sign(c(q,p) * c(q,r)); } 
    // FIXME: scalar product
  };

  template <typename K>
  class Bounded_side_3
  {
    typedef typename K::RT              RT;
    typedef typename K::Point_3         Point_3;
    typedef typename K::Vector_3        Vector_3;
    typedef typename K::Sphere_3        Sphere_3;
    typedef typename K::Tetrahedron_3   Tetrahedron_3;
    typedef typename K::Iso_cuboid_3    Iso_cuboid_3;
  public:
    typedef Bounded_side     result_type;
    typedef Arity_tag< 2 >   Arity;

    Bounded_side
    operator()( const Sphere_3& s, const Point_3& p) const
    { return s.bounded_side(p); }

    Bounded_side
    operator()( const Tetrahedron_3& t, const Point_3& p) const
    {
      RT alpha;
      RT beta ;
      RT gamma;

      Vector_3 v1 = t.vertex(1)-t.vertex(0);
      Vector_3 v2 = t.vertex(2)-t.vertex(0);
      Vector_3 v3 = t.vertex(3)-t.vertex(0);

      Vector_3 vp =   p     - t.vertex(0);

      // want to solve  alpha*v1 + beta*v2 + gamma*v3 == vp
      // let vi' == vi*vi.hw()
      // we solve alpha'*v1' + beta'*v2' + gamma'*v3' == vp' / vp.hw()
      //          muliplied by vp.hw()
      // then we have  alpha = alpha'*v1.hw() / vp.hw()
      // and           beta  = beta' *v2.hw() / vp.hw()
      // and           gamma = gamma'*v3.hw() / vp.hw()

      RT v1x = v1.hx();
      RT v1y = v1.hy();
      RT v1z = v1.hz();
      RT v2x = v2.hx();
      RT v2y = v2.hy();
      RT v2z = v2.hz();
      RT v3x = v3.hx();
      RT v3y = v3.hy();
      RT v3z = v3.hz();
      RT vpx = vp.hx();
      RT vpy = vp.hy();
      RT vpz = vp.hz();

      alpha = det3x3_by_formula( vpx, v2x, v3x,
                                 vpy, v2y, v3y,
                                 vpz, v2z, v3z );
      beta  = det3x3_by_formula( v1x, vpx, v3x,
                                 v1y, vpy, v3y,
                                 v1z, vpz, v3z );
      gamma = det3x3_by_formula( v1x, v2x, vpx,
                                 v1y, v2y, vpy,
                                 v1z, v2z, vpz );
      RT det= det3x3_by_formula( v1x, v2x, v3x,
                                 v1y, v2y, v3y,
                                 v1z, v2z, v3z );

      CGAL_kernel_assertion( det != 0 );
      if (det < 0 )
      {
          alpha = - alpha;
          beta  = - beta ;
          gamma = - gamma;
          det   = - det  ;
      }

      bool t1 = ( alpha < 0 );
      bool t2 = ( beta  < 0 );
      bool t3 = ( gamma < 0 );
            // t1 || t2 || t3 == not contained in cone

      RT lhs = alpha*v1.hw() + beta*v2.hw() + gamma*v3.hw();
      RT rhs = det * vp.hw();

      bool t4 = ( lhs > rhs );
            // alpha + beta + gamma > 1 ?
      bool t5 = ( lhs < rhs );
            // alpha + beta + gamma < 1 ?
      bool t6 = ( (alpha > 0) && (beta > 0) && (gamma > 0) );

      if ( t1 || t2 || t3 || t4 )
      {
          return ON_UNBOUNDED_SIDE;
      }
      return (t5 && t6) ? ON_BOUNDED_SIDE : ON_BOUNDARY;
    }

    Bounded_side
    operator()( const Iso_cuboid_3& c, const Point_3& p) const
    { return c.bounded_side(p); }
  };

  template <typename K>
  class Collinear_are_ordered_along_line_2
  {
    typedef typename K::RT              RT;
    typedef typename K::Point_2         Point_2;
#ifdef CGAL_kernel_exactness_preconditions 
    typedef typename K::Collinear_2 Collinear_2;
    Collinear_2 c;
#endif // CGAL_kernel_exactness_preconditions 
  public:
    typedef bool             result_type;
    typedef Arity_tag< 3 >   Arity;

#ifdef CGAL_kernel_exactness_preconditions 
    Collinear_are_ordered_along_line_2() {}
    Collinear_are_ordered_along_line_2(const Collinear_2& c_) : c(c_) {}
#endif // CGAL_kernel_exactness_preconditions 

    bool
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      CGAL_kernel_exactness_precondition( c(p, q, r) );

      const RT& phx = p.hx();
      const RT& phy = p.hy();
      const RT& phw = p.hw();
      const RT& qhx = q.hx();
      const RT& qhy = q.hy();
      const RT& qhw = q.hw();
      const RT& rhx = r.hx();
      const RT& rhy = r.hy();
      const RT& rhw = r.hw();

      if ( !(phx * rhw == rhx * phw ) )          // non-vertical ?
	{
	  return !( (  ( phx * qhw < qhx * phw)
		       &&( rhx * qhw < qhx * rhw))
		    ||(  ( qhx * phw < phx * qhw)
			 &&( qhx * rhw < rhx * qhw)) );
	}
      else if ( !(phy * rhw == rhy * phw ) )
	{
	  return !( (  ( phy * qhw < qhy * phw)
		       &&( rhy * qhw < qhy * rhw))
		    ||(  ( qhy * phw < phy * qhw)
			 &&( qhy * rhw < rhy * qhw)) );
	}
      else
	return (( phx*qhw == qhx*phw) && ( phy*qhw == qhy*phw));
    }
  };

  template <typename K>
  class Collinear_are_ordered_along_line_3
  {
    typedef typename K::Point_3         Point_3;
#ifdef CGAL_kernel_exactness_preconditions 
    typedef typename K::Collinear_3 Collinear_3;
    Collinear_3 c;
#endif // CGAL_kernel_exactness_preconditions 
  public:
    typedef bool             result_type;
    typedef Arity_tag< 3 >   Arity;

#ifdef CGAL_kernel_exactness_preconditions 
    Collinear_are_ordered_along_line_3() {}
    Collinear_are_ordered_along_line_3(const Collinear_3& c_) : c(c_) {}
#endif // CGAL_kernel_exactness_preconditions 

    bool
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      CGAL_kernel_exactness_precondition( c(p, q, r) );
      typedef typename K::RT RT;
      const RT phx = p.hx();
      const RT phw = p.hw();
      const RT qhx = q.hx();
      const RT qhw = q.hw();
      const RT rhx = r.hx();
      const RT rhw = r.hw();

      const RT pqx = phx*qhw;
      const RT qpx = qhx*phw;
      const RT prx = phx*rhw;
      const RT qrx = qhx*rhw;
      const RT rqx = rhx*qhw;
      const RT rpx = rhx*phw;

      if ( prx != rpx )   // px != rx
	{
	  //    (px <= qx)&&(qx <= rx) || (px >= qx)&&(qx >= rx)
	  // !(((qx <  px)||(rx <  qx))&&((px <  qx)||(qx <  rx)))
	  return ! (   ((qpx < pqx) || (rqx < qrx))
		       && ((pqx < qpx) || (qrx < rqx))  );
	}

      const RT phy = p.hy();
      const RT qhy = q.hy();
      const RT rhy = r.hy();

      const RT pqy = phy*qhw;
      const RT qpy = qhy*phw;
      const RT pry = phy*rhw;
      const RT qry = qhy*rhw;
      const RT rqy = rhy*qhw;
      const RT rpy = rhy*phw;

      if ( pry != rpy )
	{
	  return ! (   ((qpy < pqy) || (rqy < qry))
		       && ((pqy < qpy) || (qry < rqy))  );
	}

      const RT phz = p.hz();
      const RT qhz = q.hz();
      const RT rhz = r.hz();

      const RT pqz = phz*qhw;
      const RT qpz = qhz*phw;
      const RT prz = phz*rhw;
      const RT qrz = qhz*rhw;
      const RT rqz = rhz*qhw;
      const RT rpz = rhz*phw;

      if ( prz != rpz )
	{
	  return ! (   ((qpz < pqz) || (rqz < qrz))
		       && ((pqz < qpz) || (qrz < rqz))  );
	}
      // p == r
      return  ((rqx == qrx) && (rqy == qry) && (rqz == qrz));
    }  
  };

  template <typename K>
  class Collinear_are_strictly_ordered_along_line_2
  {
    typedef typename K::Point_2         Point_2;
#ifdef CGAL_kernel_exactness_preconditions 
    typedef typename K::Collinear_2 Collinear_2;
    Collinear_2 c;
#endif // CGAL_kernel_exactness_preconditions 
  public:
    typedef bool             result_type;
    typedef Arity_tag< 3 >   Arity;

#ifdef CGAL_kernel_exactness_preconditions 
    Collinear_are_strictly_ordered_along_line_2() {}
    Collinear_are_strictly_ordered_along_line_2(const Collinear_2& c_) : c(c_) 
    {}
#endif // CGAL_kernel_exactness_preconditions 

    bool
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      CGAL_kernel_exactness_precondition( c(p, q, r) );
      typedef typename K::RT RT;

      const RT& phx = p.hx();
      const RT& phy = p.hy();
      const RT& phw = p.hw();
      const RT& qhx = q.hx();
      const RT& qhy = q.hy();
      const RT& qhw = q.hw();
      const RT& rhx = r.hx();
      const RT& rhy = r.hy();
      const RT& rhw = r.hw();

      if ( !(phx * rhw == rhx * phw ) )
	{
	  return (   ( phx * qhw < qhx * phw)
		     &&( qhx * rhw < rhx * qhw))
	    ||(   ( qhx * phw < phx * qhw)    // ( phx * qhw > qhx * phw)
		  &&( rhx * qhw < qhx * rhw));  // ( qhx * rhw > rhx * qhw)
	}
      else
	{
	  return (   ( phy * qhw < qhy * phw)
		     &&( qhy * rhw < rhy * qhw))
	    ||(   ( qhy * phw < phy * qhw)    // ( phy * qhw > qhy * phw)
		  &&( rhy * qhw < qhy * rhw));  // ( qhy * rhw > rhy * qhw)
	}
    }
  };

  template <typename K>
  class Collinear_are_strictly_ordered_along_line_3
  {
    typedef typename K::Point_3         Point_3;
    typedef typename K::Direction_3     Direction_3;
#ifdef CGAL_kernel_exactness_preconditions 
    typedef typename K::Collinear_3 Collinear_3;
    Collinear_3 c;
#endif // CGAL_kernel_exactness_preconditions 
  public:
    typedef bool             result_type;
    typedef Arity_tag< 3 >   Arity;

#ifdef CGAL_kernel_exactness_preconditions 
    Collinear_are_strictly_ordered_along_line_3() {}
    Collinear_are_strictly_ordered_along_line_3(const Collinear_3& c_) : c(c_)
    {}
#endif // CGAL_kernel_exactness_preconditions 

    bool
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      CGAL_kernel_exactness_precondition( c(p, q, r) );
      if ( p == r) return false;
      Direction_3 dir_pq = (p - q).direction();
      Direction_3 dir_rq = (r - q).direction();
      return (dir_pq == -dir_rq);
    }  // FIXME
  };

  template <typename K>
  class Collinear_has_on_2
  {
    typedef typename K::Point_2               Point_2;
    typedef typename K::Direction_2           Direction_2;
    typedef typename K::Ray_2                 Ray_2;
    typedef typename K::Segment_2             Segment_2;
    typedef typename K::Construct_point_on_2  Construct_point_on_2;
    typedef typename K::Compare_xy_2          Compare_xy_2;
    typedef typename K::Collinear_are_ordered_along_line_2
                                           Collinear_are_ordered_along_line_2;
    Collinear_are_ordered_along_line_2 co;
    Construct_point_on_2 cp;
    Compare_xy_2 cxy;
  public:
    typedef bool             result_type;
    typedef Arity_tag< 2 >   Arity;

    Collinear_has_on_2() {}
    Collinear_has_on_2(const Construct_point_on_2& cp_,
		       const Compare_xy_2& cxy_)
      : cp(cp_), cxy(cxy_)
    {}

    bool
    operator()( const Ray_2& r, const Point_2& p) const
    {
      const Point_2 & source = cp(r,0);      
      return p == source || Direction_2(p - source) == r.direction();
    } // FIXME
  
    bool
    operator()( const Segment_2& s, const Point_2& p) const
    { 
      return co(cp(s,0), p, cp(s,1));
    }
  };

  template <typename K>
  class Collinear_2
  {
    typedef typename K::Point_2        Point_2;
    typedef typename K::Orientation_2  Orientation_2;
    Orientation_2 o;
  public:
    typedef bool             result_type;
    typedef Arity_tag< 3 >   Arity;

    Collinear_2() {}
    Collinear_2(const Orientation_2 o_) : o(o_) {}

    bool
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      typedef typename K::RT RT;

      const RT& phx = p.hx();
      const RT& phy = p.hy();
      const RT& phw = p.hw();
      const RT& qhx = q.hx();
      const RT& qhy = q.hy();
      const RT& qhw = q.hw();
      const RT& rhx = r.hx();
      const RT& rhy = r.hy();
      const RT& rhw = r.hw();
      const RT  RT0 = RT(0);

      // | A B |
      // | C D |