function_objects.h

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

// 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.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Homogeneous_kernel/include/CGAL/Homogeneous/function_objects.h $
// $Id: function_objects.h 37194 2007-03-17 09:50:18Z afabri $
//
//
// 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>
#include <CGAL/Kernel/Return_base_tag.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;
  using CartesianKernelFunctors::Construct_equidistant_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 typename K::Angle               result_type;
    typedef Arity_tag< 3 >                  Arity;

    Angle_2() {}
    Angle_2(const Construct_vector_2& c_) : c(c_) {}

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    { return enum_cast<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 typename K::Angle               result_type;
    typedef Arity_tag< 3 >                  Arity;

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

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


  template <typename K>
  class Bounded_side_2
  {
    typedef typename K::Point_2         Point_2;
    typedef typename K::Circle_2        Circle_2;
    typedef typename K::Triangle_2      Triangle_2;
    typedef typename K::Iso_rectangle_2 Iso_rectangle_2;
  public:
    typedef typename K::Bounded_side    result_type;
    typedef Arity_tag< 2 >              Arity;

    result_type
    operator()( const Circle_2& c, const Point_2& p) const
    {
      typename K::Compute_squared_distance_2 squared_distance;
      return enum_cast<Bounded_side>(CGAL_NTS compare(c.squared_radius(),
					   squared_distance(c.center(),p)));
    }

    result_type
    operator()( const Triangle_2& t, const Point_2& p) const
    {
      typename K::Collinear_are_ordered_along_line_2
	collinear_are_ordered_along_line;
      typename K::Orientation_2 orientation;
      typename K::Orientation o1 = orientation(t.vertex(0), t.vertex(1), p),
	                      o2 = orientation(t.vertex(1), t.vertex(2), p),
	                      o3 = orientation(t.vertex(2), t.vertex(3), p);

      if (o2 == o1 && o3 == o1)
	return ON_BOUNDED_SIDE;
      return
	(o1 == COLLINEAR
	 && collinear_are_ordered_along_line(t.vertex(0), p, t.vertex(1))) ||
	(o2 == COLLINEAR
	 && collinear_are_ordered_along_line(t.vertex(1), p, t.vertex(2))) ||
	(o3 == COLLINEAR
	 && collinear_are_ordered_along_line(t.vertex(2), p, t.vertex(3)))
	? ON_BOUNDARY
	: ON_UNBOUNDED_SIDE;
    }

    result_type
    operator()( const Iso_rectangle_2& r, const Point_2& p) const
    {
      return  r.rep().bounded_side(p);
    }
  };

  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 typename K::Bounded_side    result_type;
    typedef Arity_tag< 2 >              Arity;

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

    result_type
    operator()( const Tetrahedron_3& t, const Point_3& p) const
    {
      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()

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

      RT alpha = det3x3_by_formula( vpx, v2x, v3x,
                                    vpy, v2y, v3y,
                                    vpz, v2z, v3z );
      RT beta  = det3x3_by_formula( v1x, vpx, v3x,
                                    v1y, vpy, v3y,
                                    v1z, vpz, v3z );
      RT 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;
    }

    result_type
    operator()( const Iso_cuboid_3& c, const Point_3& p) const
    { return c.rep().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 typename K::Bool_type       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

    result_type
    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 typename K::Bool_type       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

    result_type
    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 typename K::Bool_type       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

    result_type
    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 typename K::Bool_type       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

    result_type
    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 typename K::Bool_type             result_type;
    typedef Arity_tag< 2 >                    Arity;

    Collinear_has_on_2() {}
    Collinear_has_on_2(const Construct_point_on_2& cp_,