bbox_filtered_predicates.h

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

     {return _compare_y_at_x_2(p,a);}

};


template <class BK>
class Has_on_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 bool result_type;

  private:

    template <class Arc_2>
    result_type
    _has_on_2(const Arc_2 &a, const Circular_arc_point_2 &p) const
    {
      Bbox_2 bb1=a.bbox(),bb2=p.bbox();

      if(do_overlap(bb1,bb2))
        return CK().has_on_2_object()(a.arc(),p.point());

       return false;
    }

  public:

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

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

};


template <class BK>
class Equal_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 bool result_type;

  private:

    template <class Arc_2>
    result_type
    _equal_2(const Arc_2 &a,const Arc_2 &b) const
    {
      Bbox_2 bb11=a.source().bbox(),
             bb12=a.target().bbox(),
             bb21=b.source().bbox(),
             bb22=b.target().bbox();

      if(bb11.xmin() > bb21.xmax()) return false;
      if(bb11.xmax() < bb21.xmin()) return false;
      if(bb11.ymin() > bb21.ymax()) return false;
      if(bb11.ymax() < bb21.ymin()) return false;

      if(bb12.xmin() > bb22.xmax()) return false;
      if(bb12.xmax() < bb22.xmin()) return false;
      if(bb12.ymin() > bb22.ymax()) return false;
      if(bb12.ymax() < bb22.ymin()) return false;

      return CK().equal_2_object()( a.arc(),b.arc() );

    }

  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 false;
      if(bb1.xmax() < bb2.xmin()) return false;
      if(bb1.ymin() > bb2.ymax()) return false;
      if(bb1.ymax() < bb2.ymin()) return false;
      return CK().equal_2_object()( a.point(),b.point() );
    }

    result_type
    operator()( const Circular_arc_2 &a , const Circular_arc_2 &b ) const
    {
      CGAL_precondition( a.arc().is_x_monotone());
      CGAL_precondition( b.arc().is_x_monotone());

      return _equal_2(a,b);      
    }

    result_type
    operator()( const Line_arc_2 &a ,
                const Line_arc_2 &b ) const
    {  return _equal_2(a,b);}

    result_type
    operator()( const Circular_arc_2 &a ,
                const Line_arc_2 &b ) const
	 {  return false;}

    result_type
    operator()( const Line_arc_2 &a ,
                const Circular_arc_2 &b ) const
	 {  return false;}

};


template <class BK>
class Do_overlap_2
  {
    typedef typename BK::Circular_kernel                                  CK;
    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
    _do_overlap_2(const Arc_2 &a, const Arc_2 &b) const
    {
      Bbox_2 bb1=a.bbox(),bb2=b.bbox();  

      if(do_overlap(bb1,bb2))
        return CK().do_overlap_2_object()(a.arc(),b.arc());
        
      return false;        
    }


  public:
    
    result_type
    operator()( const Circular_arc_2 &a , const Circular_arc_2 &b ) const
    {
      CGAL_precondition( a.arc().is_x_monotone());
      CGAL_precondition( b.arc().is_x_monotone());
      return _do_overlap_2(a,b); 
    }

    result_type
    operator()( const Line_arc_2 &a ,
                const Line_arc_2 &b ) const
    {  return _do_overlap_2(a,b);}

    result_type
    operator()( const Circular_arc_2 &a ,
                const Line_arc_2 &b ) const
	 {  return false;}

    result_type
    operator()( const Line_arc_2 &a ,
                const Circular_arc_2 &b ) const
	 {  return false;}

};


// This predicate cannot be filtered

 template < class BK >
  class Compare_y_to_right_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;

  public:
    typedef Comparison_result result_type;
    
    template <typename T1, typename T2>
    result_type
    operator()(const T1 &a1,
               const T2 &a2,
               const Circular_arc_point_2 &p) const
    { return CK().compare_y_to_right_2_object()(a1.arc(), a2.arc(), p.point()); }
    
  };


  template < class BK >
  class Make_x_monotone_2
  {
    typedef typename BK::Circular_kernel            CK;
    typedef typename BK::Rcirc_arc_2              Rcirc_arc_2;
    typedef typename BK::Circular_arc_2       	  Circular_arc_2;
    typedef typename BK::Line_arc_2               Line_arc_2;

  public:
    // typedef OutputIterator result_type;

    template < class OutputIterator >
    OutputIterator
    operator()(const Circular_arc_2 &A, OutputIterator res)
      { 
	std::vector<Object> vec;
	
	CK().make_x_monotone_2_object()(A.arc(), std::back_inserter(vec) );

	for(unsigned i=0; i<vec.size() ; i++)
	{
	  const Rcirc_arc_2 *tmp_arc;
	  tmp_arc=object_cast<Rcirc_arc_2>(&vec.at(i));
	  assert(tmp_arc!=NULL);
	  *res++ = make_object( Circular_arc_2(*tmp_arc) );
	}

	return res;
      }
    
    template < class OutputIterator >
    OutputIterator
    operator()(const Line_arc_2 &A, OutputIterator res)
      { 
	*res++ = make_object(A);
	return res;
      }
  };


  template < class BK >
  class Intersect_2
  {
    public:

    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;
    typedef typename BK::Rcirc_arc_2              Rcirc_arc_2;
    typedef typename BK::Rline_arc_2              Rline_arc_2;
    typedef typename BK::Rcirc_arc_point_2        Rcirc_arc_point_2;
    typedef typename BK::Circle_2                 Circle;

    template < class OutputIterator >
    OutputIterator
    operator()(const Circle & c1, const Circle & c2, OutputIterator res)
      { 
        if(!do_overlap(c1.bbox(),c2.bbox()))
          return res;

	std::vector<Object> vec;
         
        CK().intersect_2_object()(c1,c2,std::back_inserter(vec));
        //return CK().intersect_2_object()(c1,c2,res);

        for(unsigned i=0; i<vec.size() ; i++)
        {
          const std::pair<Rcirc_arc_point_2, unsigned> *tmp_point;

          if ( (tmp_point=object_cast<std::pair<Rcirc_arc_point_2, unsigned> >(&vec.at(i)))!=NULL )
            *res++ = make_object( std::make_pair(Circular_arc_point_2(tmp_point->first),tmp_point->second));
          else
            *res++=vec.at(i);
        }

        return res;
      }

     template < class OutputIterator >
    OutputIterator
    operator()(const Circular_arc_2 & c1, const Circular_arc_2 & c2, 
	       OutputIterator res)
      { 
         Bbox_2 bb1=c1.bbox(),bb2=c2.bbox();

        if(!do_overlap(bb1,bb2 ))
         return res;

	std::vector<Object> vec;
	
	CK().intersect_2_object()(c1.arc(),c2.arc(),std::back_inserter(vec)); 

 	for(unsigned i=0; i<vec.size() ; i++)
	{
	  const Rcirc_arc_2 *tmp_arc;

	  if ( (tmp_arc=object_cast<Rcirc_arc_2>(&vec.at(i)) )!=NULL )
	    *res++ = make_object( Circular_arc_2(*tmp_arc) );
	  else
	    {
              const std::pair<Rcirc_arc_point_2, unsigned> *tmp_point;
              tmp_point=object_cast<std::pair<Rcirc_arc_point_2, unsigned> >(&vec.at(i));
              assert(tmp_point!=NULL);
              *res++ = make_object( std::make_pair(Circular_arc_point_2(tmp_point->first),tmp_point->second));   
	    }

        }

	return res;
	

      }

     template < class OutputIterator >
    OutputIterator
    operator()(const Line_arc_2 & c1, const Line_arc_2 & c2, 
	       OutputIterator res)
      { 
         Bbox_2 bb1=c1.bbox(),bb2=c2.bbox();

        if(!do_overlap(bb1,bb2 ))
         return res;

	std::vector<Object> vec;
	
	CK().intersect_2_object()(c1.arc(),c2.arc(),std::back_inserter(vec)); 

 	for(unsigned i=0; i<vec.size() ; i++)
	{
	  const Rline_arc_2 *tmp_arc;

	  if ( (tmp_arc=object_cast<Rline_arc_2>(&vec.at(i)) )!=NULL )
	    *res++ = make_object( Line_arc_2(*tmp_arc) );
	  else
            {
              const std::pair<Rcirc_arc_point_2, unsigned> *tmp_point;
              tmp_point=object_cast<std::pair<Rcirc_arc_point_2, unsigned> >(&vec.at(i));
              assert(tmp_point!=NULL);
	      *res++ = make_object( std::make_pair(Circular_arc_point_2(tmp_point->first),tmp_point->second));
            }
	}
	return res;	
      }

     template < class OutputIterator >
    OutputIterator
    operator()(const Circular_arc_2 & c1, const Line_arc_2 & c2, 
	       OutputIterator res)
      { 
         Bbox_2 bb1=c1.bbox(),bb2=c2.bbox();

        if(!do_overlap(bb1,bb2 ))
         return res;

	std::vector<Object> vec;
	
	CK().intersect_2_object()(c1.arc(),c2.arc(),std::back_inserter(vec)); 

 	for(unsigned i=0; i<vec.size() ; i++)
	{
	  const Rcirc_arc_2 *tmp_arc;
	  const Rline_arc_2 *tmp_line;

	  if ( (tmp_arc=object_cast<Rcirc_arc_2>(&vec.at(i)) )!=NULL )  // Can this happen?
	    *res++ = make_object( Circular_arc_2(*tmp_arc) );
	  else if ( (tmp_line=object_cast<Rline_arc_2>(&vec.at(i)) )!=NULL ) //Can this happen?
	    *res++ = make_object( Line_arc_2(*tmp_line) );
	  else
	    {
              const std::pair<Rcirc_arc_point_2, unsigned> *tmp_point;
              tmp_point=object_cast<std::pair<Rcirc_arc_point_2, unsigned> >(&vec.at(i));
              assert(tmp_point!=NULL);
              *res++ = make_object( std::make_pair(Circular_arc_point_2(tmp_point->first),tmp_point->second));
            }

	}

	return res;	

      }

      template < class OutputIterator >
    OutputIterator
    operator()(const Line_arc_2 & c1, const Circular_arc_2 & c2, 
	       OutputIterator res)
      {	return operator()(c2,c1,res);}
     
    
  };


  template < class BK >
  class Split_2
  {

    typedef typename BK::Circular_kernel            CK;
    typedef typename BK::Rcirc_arc_2              Rcirc_arc_2;
    typedef typename BK::Rline_arc_2              Rline_arc_2;
    typedef typename BK::Circular_arc_2           Circular_arc_2;
    typedef typename BK::Line_arc_2               Line_arc_2;
    typedef typename BK::Circular_arc_point_2  Circular_arc_point_2;

  public:
    typedef void result_type;

    result_type
    operator()(const Circular_arc_2 &A, 
	       const Circular_arc_point_2 &p,
	       Circular_arc_2 &ha1, Circular_arc_2 &ha2) const
    {  
      Rcirc_arc_2 ca1 , ca2;

      CK().split_2_object()(A.arc(), p.point(), ca1, ca2);

      ha1=Circular_arc_2(ca1); 
      ha2=Circular_arc_2(ca2);
    }
    
    result_type
    operator()(const Line_arc_2 &A, 
	       const Circular_arc_point_2 &p,
	       Line_arc_2 &ha1, Line_arc_2 &ha2) const
    {  
      Rline_arc_2 ca1 , ca2;

      CK().split_2_object()(A.arc(), p.point(), ca1, ca2);

      ha1=Line_arc_2(ca1); 
      ha2=Line_arc_2(ca2);
    }
    
  };


  
} //Bbox_functors

CGAL_END_NAMESPACE  

#endif // CGAL_BBOX_FILTERED_PREDICATES_H