function_objects.h

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

    typedef typename K::Iso_rectangle_2 Iso_rectangle_2;

  public:
    typedef FT               result_type;
    typedef Arity_tag< 1 >   Arity;

    const result_type &
    operator()(const Iso_rectangle_2& r) const
    {
      return (r.min)().x();
    }
  };

  template <typename K>
  class Compute_xmax_2 : public Has_qrt
  {
    typedef typename K::FT              FT;
    typedef typename K::Iso_rectangle_2 Iso_rectangle_2;

  public:
    typedef FT               result_type;
    typedef Arity_tag< 1 >   Arity;

    const result_type &
    operator()(const Iso_rectangle_2& r) const
    {
      return (r.max)().x();
    }
  };

  template <typename K>
  class Compute_ymin_2 : public Has_qrt
  {
    typedef typename K::FT              FT;
    typedef typename K::Iso_rectangle_2 Iso_rectangle_2;

  public:
    typedef FT               result_type;
    typedef Arity_tag< 1 >   Arity;

    const result_type &
    operator()(const Iso_rectangle_2& r) const
    {
      return (r.min)().y();
    }
  };

  template <typename K>
  class Compute_ymax_2 : public Has_qrt
  {
    typedef typename K::FT              FT;
    typedef typename K::Iso_rectangle_2 Iso_rectangle_2;

  public:
    typedef FT               result_type;
    typedef Arity_tag< 1 >   Arity;

    const result_type &
    operator()(const Iso_rectangle_2& r) const
    {
      return (r.max)().y();
    }
  };


  template <typename K>
  class Construct_base_vector_3
  {
    typedef typename K::Vector_3   Vector_3;
    typedef typename K::Plane_3    Plane_3;
    typedef typename K::FT         FT;
    typedef typename K::Construct_cross_product_vector_3
    Construct_cross_product_vector_3;
    typedef typename K::Construct_orthogonal_vector_3
    Construct_orthogonal_vector_3;
    Construct_cross_product_vector_3 cp;
    Construct_orthogonal_vector_3 co;
  public:
    typedef Vector_3         result_type;
    typedef Arity_tag< 2 >   Arity;

    Construct_base_vector_3() {}
    Construct_base_vector_3(const Construct_cross_product_vector_3& cp_,
			    const Construct_orthogonal_vector_3& co_)
      : cp(cp_), co(co_)
    {}

    result_type
    operator()( const Plane_3& h, int index ) const
    {
      if (index == 1) {
	if ( CGAL_NTS is_zero(h.a()) )  // parallel to x-axis
	  return Vector_3(FT(1), FT(0), FT(0));
	
	if ( CGAL_NTS is_zero(h.b()) )  // parallel to y-axis
	  return Vector_3(FT(0), FT(1), FT(0));
	
	if ( CGAL_NTS is_zero(h.c()) )  // parallel to z-axis
	  return Vector_3(FT(0), FT(0), FT(1));
	
	return Vector_3(-h.b(), h.a(), FT(0));
      } else {
	return cp(co(h), this->operator()(h,1));
      }
    }
  };


  template <typename K>
  class Construct_bbox_2
  {
    typedef typename K::Point_2          Point_2;
    typedef typename K::Segment_2        Segment_2;
    typedef typename K::Iso_rectangle_2  Iso_rectangle_2;
    typedef typename K::Triangle_2       Triangle_2;
    typedef typename K::Circle_2         Circle_2;
  public:
    typedef Bbox_2                       result_type;
    typedef Arity_tag< 1 >               Arity;

    result_type
    operator()(const Point_2& p) const
    {
      std::pair<double,double> xp = CGAL_NTS to_interval(p.x());
      std::pair<double,double> yp = CGAL_NTS to_interval(p.y());
      return Bbox_2(xp.first, yp.first, xp.second, yp.second);
    }

    result_type
    operator()(const Segment_2& s) const
    { return s.source().bbox() + s.target().bbox(); }

    result_type
    operator()(const Triangle_2& t) const
    {
      typename K::Construct_bbox_2 construct_bbox_2;
      return construct_bbox_2(t.vertex(0))
	   + construct_bbox_2(t.vertex(1))
	   + construct_bbox_2(t.vertex(2));
    }

    result_type
    operator()(const Iso_rectangle_2& r) const
    {
      typename K::Construct_bbox_2 construct_bbox_2;
      return construct_bbox_2((r.min)()) + construct_bbox_2((r.max)());
    }

    result_type
    operator()(const Circle_2& c) const
    {
      typename K::Construct_bbox_2 construct_bbox_2;
      Bbox_2 b = construct_bbox_2(c.center());

      Interval_nt<> x (b.xmin(), b.xmax());
      Interval_nt<> y (b.ymin(), b.ymax());

      Interval_nt<> sqr = CGAL_NTS to_interval(c.squared_radius());
      Interval_nt<> r = CGAL::sqrt(sqr);
      Interval_nt<> minx = x-r;
      Interval_nt<> maxx = x+r;
      Interval_nt<> miny = y-r;
      Interval_nt<> maxy = y+r;

      return Bbox_2(minx.inf(), miny.inf(), maxx.sup(), maxy.sup());
    }
  };


  template <typename K>
  class Construct_bbox_3
  {
    typedef typename K::Point_3          Point_3;
    typedef typename K::Segment_3        Segment_3;
    typedef typename K::Iso_cuboid_3     Iso_cuboid_3;
    typedef typename K::Triangle_3       Triangle_3;
    typedef typename K::Tetrahedron_3    Tetrahedron_3;
    typedef typename K::Sphere_3         Sphere_3;
  public:
    typedef Bbox_3          result_type;
    typedef Arity_tag< 1 >  Arity;

    Bbox_3
    operator()(const Point_3& p) const
    {
      std::pair<double,double> xp = CGAL_NTS to_interval(p.x());
      std::pair<double,double> yp = CGAL_NTS to_interval(p.y());
      std::pair<double,double> zp = CGAL_NTS to_interval(p.z());
      return Bbox_3(xp.first, yp.first, zp.first,
                    xp.second, yp.second, zp.second);
    }

    Bbox_3
    operator()(const Segment_3& s) const
    { return s.source().bbox() + s.target().bbox(); }

    Bbox_3
    operator()(const Triangle_3& t) const
    {
      typename K::Construct_bbox_3 construct_bbox_3;
      return construct_bbox_3(t.vertex(0))
	   + construct_bbox_3(t.vertex(1))
	   + construct_bbox_3(t.vertex(2));
    }

    Bbox_3
    operator()(const Iso_cuboid_3& r) const
    {
      typename K::Construct_bbox_3 construct_bbox_3;
      return construct_bbox_3((r.min)()) + construct_bbox_3((r.max)());
    }

    Bbox_3
    operator()(const Tetrahedron_3& t) const
    {
      typename K::Construct_bbox_3 construct_bbox_3;
      return construct_bbox_3(t.vertex(0)) + construct_bbox_3(t.vertex(1))
           + construct_bbox_3(t.vertex(2)) + construct_bbox_3(t.vertex(3));
    }

    Bbox_3
    operator()(const Sphere_3& s) const
    {
      typename K::Construct_bbox_3 construct_bbox_3;
      Bbox_3 b = construct_bbox_3(s.center());

      Interval_nt<> x (b.xmin(), b.xmax());
      Interval_nt<> y (b.ymin(), b.ymax());
      Interval_nt<> z (b.zmin(), b.zmax());

      Interval_nt<> sqr = CGAL_NTS to_interval(s.squared_radius());
      Interval_nt<> r = CGAL::sqrt(sqr);
      Interval_nt<> minx = x-r;
      Interval_nt<> maxx = x+r;
      Interval_nt<> miny = y-r;
      Interval_nt<> maxy = y+r;
      Interval_nt<> minz = z-r;
      Interval_nt<> maxz = z+r;

      return Bbox_3(minx.inf(), miny.inf(), minz.inf(), 
		    maxx.sup(), maxy.sup(), maxz.sup());
    }
  };


  template <typename K>
  class Construct_bisector_2
  {
    typedef typename K::FT      FT;
    typedef typename K::Point_2 Point_2;
    typedef typename K::Line_2  Line_2;
  public:
    typedef Line_2              result_type;
    typedef Arity_tag< 2 >      Arity;

    result_type
    operator()(const Point_2& p, const Point_2& q) const
    {
      FT a, b, c;
      bisector_of_pointsC2(p.x(), p.y(), q.x(), q.y(), a, b, c);
      return Line_2(a, b, c);
    }

    result_type
    operator()(const Line_2& p, const Line_2& q) const
    {
      FT a, b, c;
      bisector_of_linesC2(p.a(), p.b(), p.c(),
                          q.a(), q.b(), q.c(),
                          a, b, c);
      return Line_2(a, b, c);
    }
  };

  template <typename K>
  class Construct_bisector_3
  {
    typedef typename K::FT        FT;
    typedef typename K::Point_3   Point_3;
    typedef typename K::Plane_3   Plane_3;
  public:
    typedef Plane_3               result_type;
    typedef Arity_tag< 2 >        Arity;

    result_type
    operator()(const Point_3& p, const Point_3& q) const
    {
      FT a, b, c, d;
      bisector_of_pointsC3(p.x(), p.y(), p.z(),
	                   q.x(), q.y(), q.z(),
			   a, b, c, d);
      return Plane_3(a, b, c, d);
    }

    result_type
    operator()(const Plane_3& p, const Plane_3& q) const
    {
      FT a, b, c, d;
      bisector_of_planesC3(p.a(), p.b(), p.c(), p.d(),
                           q.a(), q.b(), q.c(), q.d(),
                           a, b, c, d);
      return Plane_3(a, b, c, d);
    }
  };

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

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      typename K::Construct_point_2 construct_point_2;
      FT x, y;
      centroidC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y(), x, y);
      return construct_point_2(x, y);
    }

    result_type
    operator()(const Triangle_2& t) const
    {
      return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2));
    }

    result_type
    operator()(const Point_2& p, const Point_2& q,
               const Point_2& r, const Point_2& s) const
    {
      typename K::Construct_point_2 construct_point_2;
      FT x, y;
      centroidC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y(), s.x(), s.y(), x, y);
      return construct_point_2(x, y);
    }
  };

  template <typename K>
  class Construct_centroid_3
  {
    typedef typename K::FT             FT;
    typedef typename K::Point_3        Point_3;
    typedef typename K::Triangle_3     Triangle_3;
    typedef typename K::Tetrahedron_3  Tetrahedron_3;
  public:
    typedef Point_3                    result_type;
    typedef Arity_tag< 3 >             Arity;

    result_type
    operator()(const Point_3& p, const Point_3& q, const Point_3& r) const
    {
      typename K::Construct_point_3 construct_point_3;
      FT x, y, z;
      centroidC3(p.x(), p.y(), p.z(),
		 q.x(), q.y(), q.z(),
		 r.x(), r.y(), r.z(),
		 x, y, z);
      return construct_point_3(x, y, z);
    }

    result_type
    operator()(const Point_3& p, const Point_3& q,
               const Point_3& r, const Point_3& s) const
    {
      typename K::Construct_point_3 construct_point_3;
      FT x, y, z;
      centroidC3(p.x(), p.y(), p.z(),
		 q.x(), q.y(), q.z(),
		 r.x(), r.y(), r.z(),
		 s.x(), s.y(), s.z(),
		 x, y, z);
      return construct_point_3(x, y, z);
    }

    result_type
    operator()(const Triangle_3& t) const
    {
      return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2));
    }

    result_type
    operator()(const Tetrahedron_3& t) const
    {
      return this->operator()(t.vertex(0), t.vertex(1),
                              t.vertex(2), t.vertex(3));
    }
  };

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

    Point_2
    operator()(const Point_2& p, const Point_2& q) const
    {
      typename K::Construct_midpoint_2 construct_midpoint_2;
      return construct_midpoint_2(p, q);
    }

    result_type
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      typename K::Construct_point_2 construct_point_2;
      typedef typename K::FT        FT;
      FT x, y;
      circumcenterC2(p.x(), p.y(), q.x(), q.y(), r.x(), r.y(), x, y);
      return construct_point_2(x, y);
    }

    result_type
    operator()(const Triangle_2& t) const
    {
      return this->operator()(t.vertex(0), t.vertex(1), t.vertex(2));
    }
  };

  template <typename K>
  class Construct_circumcenter_3
  {
    typedef typename K::FT             FT;
    typedef typename K::Tetrahedron_3  Tetrahedron_3;
    typedef typename K::Triangle_3     Triangle_3;
    typedef typename K::Point_3        Point_3;
  public:
    typedef Point_3                    result_type;
    typedef Arity_tag< 4 >             Arity;

    Point_3
    operator()(const Point_3& p, const Point_3& q) const
    {
      typename K::Construct_midpoint_3 construct_midpoint_3;
      return construct_midpoint_3(p, q);
    }

    Point_3
    operator()(const Point_3& p, const Point_3& q, const Point_3& s) const
    {
      typename K::Construct_point_3 construct_point_3;
      // Translate s to origin to simplify the expression.
      FT psx = p.x()-s.x();
      FT psy = p.y()-s.y();
      FT psz = p.z()-s.z();
      FT ps2 = CGAL_NTS square(psx) + CGAL_NTS square(psy) + CGAL_NTS square(psz);
      FT qsx = q.x()-s.x();
      FT qsy = q.y()-s.y();
      FT qsz = q.z()-s.z();
      FT qs2 = CGAL_NTS square(qsx) + CGAL_NTS square(qsy) + CGAL_NTS square(qsz);
      FT rsx = psy*qsz-psz*qsy;
      FT rsy = psz*qsx-psx*qsz;
      FT rsz = psx*qsy-psy*qsx;

      // The following determinants can be developped and simplified.
      //