bbox_filtered_predicates.h

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

// Copyright (c) 2003-2006  INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL 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/Circular_kernel_2/include/CGAL/Filtered_bbox_circular_kernel_2/bbox_filtered_predicates.h $
// $Id: bbox_filtered_predicates.h 34798 2006-10-16 12:32:09Z afabri $
//
// Author(s)     : Monique Teillaud, Sylvain Pion, Constantinos Tsirogiannis

// Partially supported by the IST Programme of the EU as a Shared-cost
// RTD (FET Open) Project under Contract No  IST-2000-26473 
// (ECG - Effective Computational Geometry for Curves and Surfaces) 
// and a STREP (FET Open) Project under Contract No  IST-006413 
// (ACS -- Algorithms for Complex Shapes)

#ifndef CGAL_BBOX_FILTERED_PREDICATES_H  
#define CGAL_BBOX_FILTERED_PREDICATES_H  

#include <cassert>
#include <CGAL/enum.h>
#include <CGAL/Object.h>
#include <CGAL/Bbox_2.h>

CGAL_BEGIN_NAMESPACE

namespace Bbox_functors {

template <class BK>
class Compare_x_2
  {
    typedef typename BK::Circular_kernel                           CK;
    typedef typename BK::Circular_arc_point_2                    Circular_arc_point_2;

   public:

    typedef Comparison_result result_type;

   public:

    result_type
    operator()( const Circular_arc_point_2 &a, const Circular_arc_point_2 &b) const
    {
       Bbox_2 bb1=a.bbox(),bb2=b.bbox();

       if( bb1.xmin()>bb2.xmax() )
         return LARGER;

       if( bb1.xmax()<bb2.xmin() )
         return SMALLER;

       return CK().compare_x_2_object()(a.point(),b.point());
    }

  };


template <class BK>
class Compare_y_2
  {
    typedef typename BK::Circular_kernel                           CK;
    typedef typename BK::Circular_arc_point_2                    Circular_arc_point_2;

   public:

    typedef Comparison_result result_type;

   public:

    result_type
    operator()( const Circular_arc_point_2 &a, const Circular_arc_point_2 &b) const
    {
       Bbox_2 bb1=a.bbox(),bb2=b.bbox();


       if( bb1.ymin()>bb2.ymax() )
         return LARGER;

       if( bb1.ymax()<bb2.ymin() )
         return SMALLER;

       return CK().compare_y_2_object()(a.point(),b.point());
    }

  };

template <class BK>
class Compare_xy_2
  {
    typedef typename BK::Circular_kernel                           CK;
    typedef typename BK::Circular_arc_point_2                    Circular_arc_point_2;

   public:

    typedef Comparison_result result_type;

   public:

    result_type
    operator()( const Circular_arc_point_2 &a, const Circular_arc_point_2 &b) const
    {
      typename BK::Compare_x_2 compx;
      typename BK::Compare_y_2 compy;
      Comparison_result tmp;

      if( (tmp=compx(a,b))!=EQUAL)
      return tmp;

      return compy(a,b);
    }

  };


template <class BK>
class In_x_range_2
  {
    typedef typename BK::Circular_kernel                           CK;
    typedef typename BK::Circular_arc_point_2                    Circular_arc_point_2;
    typedef typename BK::Circular_arc_2                          Circular_arc_2;
    typedef typename BK::Line_arc_2                              Line_arc_2;

   public:

    typedef bool result_type;

   private:

    template <class Arc_2>
    result_type
    _in_x_range_2(const Arc_2 &a, const Circular_arc_point_2 &p) const 
    {

      Bbox_2 bb11 = a.source().bbox(),
             bb12 = a.target().bbox(),
             bb2=p.bbox();      
      if(bb11.xmin() > bb12.xmax()) {
        if(bb2.xmax() < bb12.xmin()) return false;
        else if(bb2.xmin() > bb11.xmax()) return false;
        else if(bb12.xmax() < bb2.xmin() &&
       	        bb2.xmax() < bb11.xmin()) return true;
      } else if(bb11.xmax() < bb12.xmin()) {
        if(bb2.xmax() < bb11.xmin()) return false;
        else if(bb2.xmin() > bb12.xmax()) return false;
        else if(bb11.xmax() < bb2.xmin() &&
                bb2.xmax() < bb12.xmin()) return true;
      } else {
        if(bb2.xmin() > (std::max)(bb11.xmax(),bb12.xmax())) return false;
        if(bb2.xmax() < (std::min)(bb11.xmin(),bb12.xmin())) return false;
      }
    
      typename CK::In_x_range_2 Range;

      return Range(a.arc(),p.point());

    }

   public:

    result_type
    operator()( const Circular_arc_2 &a, const Circular_arc_point_2 &p) const
    { 
      CGAL_precondition( a.arc().is_x_monotone());
      return _in_x_range_2(a,p);
   }

    result_type
    operator()( const Line_arc_2 &a, const Circular_arc_point_2 &p) const
    { return _in_x_range_2(a,p);}
    

  };



template < class BK >
  class Construct_line_arc_2
  {

    typedef typename BK::Point_2                   Point_2;
    typedef typename BK::Line_2                    Line_2;
    typedef typename BK::Circle_2                  Circle_2;
    typedef typename BK::Circular_arc_point_2      Circular_arc_point_2;
    typedef typename BK::Segment_2                 Segment_2;
    typedef typename BK::Line_arc_2                Line_arc_2;

  public:
    typedef Line_arc_2   result_type;
    typedef Arity_tag<3> Arity;
    
    result_type
    operator()(void) 
    { return Line_arc_2(); }

    result_type
    operator()(const Line_2 &support,
	       const Circle_2 &c1,const bool b1,
	       const Circle_2 &c2,const bool b2) const
    { return Line_arc_2(support,c1,b1,c2,b2); }

    result_type
    operator()(const Line_2 &support,
	       const Line_2 &l1,
	       const Line_2 &l2) const
    { return Line_arc_2(support,l1,l2); }

    result_type
    operator()(const Line_2 &support,
	       const Circular_arc_point_2 &p1,
	       const Circular_arc_point_2 &p2) const
    { return Line_arc_2(support,p1,p2); }

//     result_type
//     operator()(const Line_2 &support,
// 	       const Point_2 &p1,
// 	       const Point_2 &p2) const
//     { return Line_arc_2(support,p1,p2); }

    result_type
    operator()(const Segment_2 &s) const
    { return Line_arc_2(s); }

    result_type
    operator()(const Point_2 &p1,
	       const Point_2 &p2) const
    { return Line_arc_2(p1,p2); }

  };



  template < class BK >
  class Construct_circular_arc_2
  {

    typedef typename BK::FT                           FT;
    typedef typename BK::RT                           RT;
    typedef typename BK::Point_2                      Point_2;
    typedef typename BK::Line_2                       Line_2;
    typedef typename BK::Circle_2                     Circle_2;
    typedef typename BK::Circular_arc_2               Circular_arc_2;
    typedef typename BK::Circular_arc_point_2         Circular_arc_point_2;

  public:
    typedef  Circular_arc_2 result_type;
    typedef  Arity_tag<3>   Arity;
    
    result_type
    operator()(void) 
    { return Circular_arc_2(); }

    result_type
    operator()(const Circle_2 &c) const
    { return Circular_arc_2(c); }

    result_type
    operator()(const Circle_2 &support,
               const Circular_arc_point_2 &source, 
               const Circular_arc_point_2 &target) const
    { return Circular_arc_2(support,source,target); }

    result_type
    operator()(const Circle_2 &support,
               const Line_2 &l1, bool b1,
               const Line_2 &l2, bool b2) const
    { return Circular_arc_2(support,l1,b1,l2,b2); }

    result_type
    operator()(const Circle_2 &c,
               const Circle_2 &c1, bool b_1,
               const Circle_2 &c2, bool b_2) const
    { return Circular_arc_2(c,c1,b_1,c2,b_2); }

    result_type
    operator()(const Circular_arc_2 &A,
               bool b,
               const Circle_2 &ccut, bool b_cut) const
    { return Circular_arc_2(A,b,ccut,b_cut); }

    result_type
    operator()(const Point_2 &begin,
               const Point_2 &middle, 
               const Point_2 &end) const
    { return Circular_arc_2(begin,middle,end); }

    result_type
    operator()(const Point_2 &begin,
               const Point_2 &end,
	       const FT& bulge) const
    { return Circular_arc_2(begin,end,bulge); }

  };




template <class BK>
class Construct_circular_source_vertex_2
  {
    typedef typename BK::Circular_kernel                       CK;
    typedef typename BK::Circular_arc_point_2                Circular_arc_point_2;
    typedef typename BK::Circular_arc_2                      Circular_arc_2;

   public:

    typedef Circular_arc_point_2    result_type;
    typedef const result_type &     qualified_result_type;

    template <typename T>
    result_type
      operator()(const T& a) const
    {return CK().construct_circular_source_vertex_2_object()(a.arc());}

  };


template <class BK>
class Construct_circular_target_vertex_2
  {
    typedef typename BK::Circular_kernel                       CK;
    typedef typename BK::Circular_arc_point_2                Circular_arc_point_2;
    typedef typename BK::Circular_arc_2                      Circular_arc_2;

   public:

    typedef Circular_arc_point_2 result_type;
    typedef const result_type &     qualified_result_type;

    template <typename T>
    result_type
      operator()(const T& a) const
    {return CK().construct_circular_target_vertex_2_object()(a.arc());}

  };



template <class BK>
class Construct_circular_min_vertex_2
  {
    typedef typename BK::Circular_kernel                       CK;
    typedef typename BK::Circular_arc_point_2                Circular_arc_point_2;
    typedef typename BK::Circular_arc_2                      Circular_arc_2;

   public:

    typedef Circular_arc_point_2 result_type;
    
    template <typename T>
    result_type
      operator()(const T& a) const
    {return CK().construct_circular_min_vertex_2_object()(a.arc());}
    
  };

template <class BK>
class Construct_circular_max_vertex_2
  {
    typedef typename BK::Circular_kernel                           CK;
    typedef typename BK::Circular_arc_point_2                    Circular_arc_point_2;
    typedef typename BK::Circular_arc_2                          Circular_arc_2;

   public:

    typedef Circular_arc_point_2 result_type;

    template <typename T>
     result_type
      operator()(const T& a) const
    { return CK().construct_circular_max_vertex_2_object()(a.arc()); }

  };

template <class BK>
class Is_vertical_2
  {
    typedef typename BK::Circular_kernel                           CK;
    typedef typename BK::Circular_arc_point_2                    Circular_arc_point_2;
    typedef typename BK::Circular_arc_2                          Circular_arc_2;

   public:

    typedef bool result_type;
    
    template <typename T>
    result_type
      operator()(const T& a) const
    { return CK().is_vertical_2_object()(a.arc()); }
  };

 


template <class BK>
class Compare_y_at_x_2
  {
    typedef typename BK::Circular_kernel                                    CK;
    typedef typename BK::Circular_arc_2                                   Circular_arc_2;
    typedef typename BK::Circular_arc_point_2                             Circular_arc_point_2;
    typedef typename BK::Line_arc_2                                       Line_arc_2;

  public:

    typedef Comparison_result result_type;

  private:

    template <class Arc_2>
    result_type
    _compare_y_at_x_2(const Circular_arc_point_2 &p,const Arc_2 &a) const
    {
      CGAL_precondition_code(bool tmp=In_x_range_2<BK>()(a,p));
      CGAL_precondition(tmp );

      Bbox_2 bb1=a.bbox(),bb2=p.bbox();

      if(bb1.ymin()>bb2.ymax())
        return SMALLER;
      else if(bb1.ymax()<bb2.ymin())
        return LARGER;

      return CK().compare_y_at_x_2_object()(p.point(),a.arc());

    }

  public:

    result_type
    operator()( const Circular_arc_point_2 &p,const Circular_arc_2 &a ) const
    {   
      CGAL_precondition( a.arc().is_x_monotone());
      return _compare_y_at_x_2(p,a);
    }

    result_type
    operator()( const Circular_arc_point_2 &p,const Line_arc_2 &a ) const