function_objects.h

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

// Copyright (c) 1999-2005  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/Cartesian/function_objects.h $
// $Id: function_objects.h 35640 2006-12-27 23:25:47Z spion $
//
//
// Author(s)     : Stefan Schirra, Sylvain Pion, Michael Hoffmann

#ifndef CGAL_CARTESIAN_FUNCTION_OBJECTS_H
#define CGAL_CARTESIAN_FUNCTION_OBJECTS_H

#include <CGAL/Kernel/function_objects.h>
#include <CGAL/predicates/kernel_ftC2.h>
#include <CGAL/predicates/kernel_ftC3.h>
#include <CGAL/constructions/kernel_ftC2.h>
#include <CGAL/constructions/kernel_ftC3.h>
#include <CGAL/Cartesian/solve_3.h>

CGAL_BEGIN_NAMESPACE

namespace CartesianKernelFunctors {

  using namespace CommonKernelFunctors;

  template <typename K>
  class Angle_2
  {
    typedef typename K::Point_2 Point_2;
  public:
    typedef typename K::Angle   result_type;
    typedef Arity_tag< 3 >      Arity;

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    { return angleC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y()); }
  };

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

    result_type
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      return angleC3(p.x(), p.y(), p.z(),
		     q.x(), q.y(), q.z(),
		     r.x(), r.y(), r.z());
    }
  };

  template <typename K>
  class Are_parallel_2
  {
    typedef typename K::Line_2          Line_2;
    typedef typename K::Segment_2       Segment_2;
    typedef typename K::Ray_2           Ray_2;

  public:
    typedef typename K::Bool_type       result_type;
    typedef Arity_tag< 2 >              Arity;

    result_type
    operator()(const Line_2& l1, const Line_2& l2) const
    { return parallelC2(l1.a(), l1.b(), l2.a(), l2.b()); }

    result_type
    operator()(const Segment_2& s1, const Segment_2& s2) const
    { return parallelC2(s1.source().x(), s1.source().y(),
                        s1.target().x(), s1.target().y(),
                        s2.source().x(), s2.source().y(),
                        s2.target().x(), s2.target().y());
    }

    result_type
    operator()(const Ray_2& r1, const Ray_2& r2) const
    { return parallelC2(r1.source().x(), r1.source().y(),
                        r1.second_point().x(), r1.second_point().y(),
                        r2.source().x(), r2.source().y(),
                        r2.second_point().x(), r2.second_point().y());
    }
  };

  template <typename K>
  class Are_parallel_3
  {
    typedef typename K::Line_3          Line_3;
    typedef typename K::Segment_3       Segment_3;
    typedef typename K::Ray_3           Ray_3;
    typedef typename K::Plane_3         Plane_3;

  public:
    typedef typename K::Bool_type       result_type;
    typedef Arity_tag< 2 >              Arity;

    result_type
    operator()(const Line_3& l1, const Line_3& l2) const
    { return parallelC3(
                l1.to_vector().x(), l1.to_vector().y(), l1.to_vector().z(),
                l2.to_vector().x(), l2.to_vector().y(), l2.to_vector().z());
    }

    result_type
    operator()(const Plane_3& h1, const Plane_3& h2) const
    { return parallelC3(h1.a(), h1.b(), h1.c(),
                        h2.a(), h2.b(), h2.c());
    }

    result_type
    operator()(const Segment_3& s1, const Segment_3& s2) const
    { return parallelC3(s1.source().x(), s1.source().y(), s1.source().z(),
                        s1.target().x(), s1.target().y(), s1.target().z(),
                        s2.source().x(), s2.source().y(), s2.source().z(),
                        s2.target().x(), s2.target().y(), s2.target().z());
    }

    result_type
    operator()(const Ray_3& r1, const Ray_3& r2) const
    { return parallelC3(r1.source().x(), r1.source().y(), r1.source().z(),
	r1.second_point().x(), r1.second_point().y(), r1.second_point().z(),
                        r2.source().x(), r2.source().y(), r2.source().z(),
	r2.second_point().x(), r2.second_point().y(), r2.second_point().z());
    }
  };

  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
    {
      bool x_incr = (r.xmin() < p.x()) && (p.x() < r.xmax()),
	   y_incr = (r.ymin() < p.y()) && (p.y() < r.ymax());
      if (x_incr)
	{
	  if (y_incr)
	    return ON_BOUNDED_SIDE;
	  if ( (p.y() == r.ymin()) || (r.ymax() == p.y()) )
	    return ON_BOUNDARY;
	}
      if ( (p.x() == r.xmin()) || (r.xmax() == p.x()) )
	if ( y_incr || (p.y() == r.ymin()) || (r.ymax() == p.y()) )
          return ON_BOUNDARY;

      return ON_UNBOUNDED_SIDE;
    }
  };

  template <typename K>
  class Bounded_side_3
  {
    typedef typename K::FT              FT;
    typedef typename K::Point_3         Point_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
    {
      FT alpha, beta, gamma;

      solve(t.vertex(1)-t.vertex(0),
            t.vertex(2)-t.vertex(0),
            t.vertex(3)-t.vertex(0),
            p - t.vertex(0), alpha, beta, gamma);
      if (   (alpha < 0) || (beta < 0) || (gamma < 0)
          || (alpha + beta + gamma > 1) )
          return ON_UNBOUNDED_SIDE;

      if (   (alpha == 0) || (beta == 0) || (gamma == 0)
          || (alpha+beta+gamma == 1) )
        return ON_BOUNDARY;

      return ON_BOUNDED_SIDE;
    }

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

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      CGAL_kernel_exactness_precondition( collinear(p, q, r) );
      return collinear_are_ordered_along_lineC2
	(p.x(), p.y(), q.x(), q.y(), r.x(), r.y());
    }
  };

  template <typename K>
  class Collinear_are_ordered_along_line_3
  {
    typedef typename K::Point_3         Point_3;
  public:
    typedef typename K::Bool_type       result_type;
    typedef Arity_tag< 3 >              Arity;

    result_type
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      CGAL_kernel_exactness_precondition( collinear(p, q, r) );
      return collinear_are_ordered_along_lineC3(p.x(), p.y(), p.z(),
						q.x(), q.y(), q.z(),
						r.x(), r.y(), r.z());
    }
  };

  template <typename K>
  class Collinear_are_strictly_ordered_along_line_2
  {
    typedef typename K::Point_2         Point_2;
  public:
    typedef typename K::Bool_type       result_type;
    typedef Arity_tag< 3 >              Arity;

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      CGAL_kernel_exactness_precondition( collinear(p, q, r) );
      return collinear_are_strictly_ordered_along_lineC2
	(p.x(), p.y(), q.x(), q.y(), r.x(), r.y());
    }
  };

  template <typename K>
  class Collinear_are_strictly_ordered_along_line_3
  {
    typedef typename K::Point_3         Point_3;
  public:
    typedef typename K::Bool_type       result_type;
    typedef Arity_tag< 3 >              Arity;

    result_type
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      CGAL_kernel_exactness_precondition( collinear(p, q, r) );
      return collinear_are_strictly_ordered_along_lineC3(p.x(), p.y(), p.z(),
							 q.x(), q.y(), q.z(),
							 r.x(), r.y(), r.z());
    }
  };

  template <typename K>
  class Collinear_has_on_2
  {
    typedef typename K::Point_2               Point_2;
    typedef typename K::Ray_2                 Ray_2;
    typedef typename K::Segment_2             Segment_2;
  public:
    typedef typename K::Bool_type             result_type;
    typedef Arity_tag< 2 >                    Arity;

    result_type
    operator()( const Ray_2& r, const Point_2& p) const
    {
      const Point_2 & source = r.source();
      const Point_2 & second = r.second_point();
      switch(compare_x(source, second)) {
      case SMALLER:
        return compare_x(source, p) != LARGER;
      case LARGER:
        return compare_x(p, source) != LARGER;
      default:
        switch(compare_y(source, second)){
        case SMALLER:
	  return compare_y(source, p) != LARGER;
        case LARGER:
	  return compare_y(p, source) != LARGER;
        default:
	  return true; // p == source
        }
      } // switch
    }

    result_type
    operator()( const Segment_2& s, const Point_2& p) const
    {
      return collinear_are_ordered_along_line(s.source(), p, s.target());
    }
  };

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

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

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    { return o(p, q, r) == COLLINEAR; }
  };

  template <typename K>
  class Collinear_3
  {
    typedef typename K::Point_3    Point_3;
  public:
    typedef typename K::Bool_type  result_type;
    typedef Arity_tag< 3 >         Arity;

    result_type
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      return collinearC3(p.x(), p.y(), p.z(),
			 q.x(), q.y(), q.z(),
			 r.x(), r.y(), r.z());
    }
  };

  template <typename K>
  class Compare_angle_with_x_axis_2
  {
    typedef typename K::Direction_2        Direction_2;
  public:
    typedef typename K::Comparison_result  result_type;
    typedef Arity_tag< 2 >                 Arity;

    result_type
    operator()(const Direction_2& d1, const Direction_2& d2) const
    {
      return compare_angle_with_x_axisC2(d1.dx(), d1.dy(), d2.dx(), d2.dy());
    }
  };

  template <typename K>
  class Compare_distance_2
  {
    typedef typename K::Point_2            Point_2;
  public:
    typedef typename K::Comparison_result  result_type;
    typedef Arity_tag< 3 >                 Arity;

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      return cmp_dist_to_pointC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y());
    }
  };

  template <typename K>
  class Compare_squared_distance_2
  {
    typedef typename K::Point_2            Point_2;
    typedef typename K::FT                 FT;
  public:
    typedef typename K::Comparison_result  result_type;
    typedef Arity_tag< 3 >                 Arity;

    result_type
    operator()(const Point_2& p, const Point_2& q, const FT& d2) const
    {
      return CGAL_NTS compare(squared_distance(p, q), d2);
    }
  };

  template <typename K>
  class Compare_distance_3
  {
    typedef typename K::Point_3            Point_3;
  public:
    typedef typename K::Comparison_result  result_type;
    typedef Arity_tag< 3 >                 Arity;

    result_type
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      return cmp_dist_to_pointC3(p.x(), p.y(), p.z(),
				 q.x(), q.y(), q.z(),
				 r.x(), r.y(), r.z());
    }
  };

  template <typename K>
  class Compare_squared_distance_3
  {
    typedef typename K::Point_3            Point_3;
    typedef typename K::FT                 FT;
  public: