hexagon_primitives.h

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

            stck.push(plgn[i]);

          Point_2 last_one=plgn[siz-1];
          plgn.clear();

          

          for(int i=0;i<siz-1;++i)
          {
            plgn.push_back(stck.top());
            stck.pop();
          }

          plgn.push_back(last_one);
        }
          
		
		
	return plgn;       
	}


template<typename CK, typename Output_iterator>
Output_iterator construct_bounding_hexagons_2(const typename CK::Circular_arc_2 &a, Output_iterator res)		
  {

    typedef std::pair< bool,bool >  Position;
    typedef std::pair<CGAL::Object,Position>           Verbose_type; 
    typedef std::vector<Verbose_type >                 Xy_mon_vector;	
    typedef CGAL::Simple_cartesian<double>             K;
    typedef std::vector< CGAL::Polygon_2<K> >          Polygon_vector;

    Xy_mon_vector xy_arcs;
    Polygon_vector polygons;

    advanced_make_xy_monotone<CK>(a,std::back_inserter(xy_arcs));


    for(unsigned int i=0;i<xy_arcs.size();i++)
      *res++=construct_bounding_hexagon_2<CK>(xy_arcs.at(i));

    return res;

  }	

 bool  _inner_intersect_hexagon_predicate(const CGAL::Polygon_2<Simple_cartesian< double > > &a,
                                          const CGAL::Polygon_2<Simple_cartesian<double> > &b)
 {

    typedef Simple_cartesian<double> CK;
    typedef CK::RT      RT;
    typedef CK::Point_2 Point_2;
    typedef CGAL::Polygon_2<CK> Polygon_2;
    typedef Simple_cartesian<Interval_nt<> > intrv_CK;
    typedef intrv_CK::Line_2  intrv_Line_2;
    typedef intrv_CK::Point_2  intrv_Point_2;

    
  bool pred=(a[0].x()!=a[1].x() && a[0].y()!=a[1].y());
      
          Interval_nt<> d1=a[0].x(),d2=a[0].y();
          Interval_nt<> e1=a[1].x(),e2=a[1].y();
          intrv_Point_2 a0( d1, d2 );
          intrv_Point_2 a1( e1, e2 );

          intrv_Line_2 tmp_ln(a0,a1);

   	
      if(pred && !tmp_ln.is_vertical())
        {
	  int i;
	
	  for(i=0;i<b.size();i++)
	    {
	      
                //if(b[i]==a[0] || b[i]==a[1])
                //  return true;	     

	      std::pair<double,double> app_y=tmp_ln.y_at_x(b[i].x()).pair();

              if(b[i].y()>=app_y.first )
	        if(i==0)
	          break;
	        else 
	          return true;
	    }
	
	  if(i!=0)
	    return false;

	 }
	

	  //Condition implied: the segment used for testing is vertical
	 if(a[2+pred].x()==a[3+pred].x())
	   return true;
	 
          Interval_nt<> d12=a[2+pred].x(),d22=a[2+pred].y();
          Interval_nt<> e12=a[3+pred].x(),e22=a[3+pred].y();
          intrv_Point_2 a2( d12, d22 );
          intrv_Point_2 a3( e12, e22 );

          intrv_Line_2 tmp_ln2(a2,a3);
	 
	 for(int i=0;i<b.size();i++) 
	 {
	   std::pair<double,double> app_y=tmp_ln2.y_at_x(b[i].x()).pair();

           if(b[i].y()<=app_y.second ) 
	     return true;	
	 }
			
	 return false;
			
}


bool _do_intersect_hexagon_2(const CGAL::Polygon_2<Simple_cartesian< double > > &p1,
			     const CGAL::Polygon_2<Simple_cartesian<double> > &p2)
  {
    typedef Simple_cartesian<double> CK;
    typedef CK::RT      RT;
    typedef CK::Point_2 Point_2;
    typedef CGAL::Polygon_2<CK> Polygon_2;
    typedef Simple_cartesian<Interval_nt<> > intrv_CK;
    typedef intrv_CK::Line_2  intrv_Line_2;
    typedef intrv_CK::Point_2  intrv_Point_2;
		
    Polygon_2 a,b;
    bool intersect,tmp=0;
    Point_2 frst,scnd;
	
    int size1=p1.size(),
    	size2=p2.size();

    if(size1==4 && size2==4)
      return true;

    if(size1==4)
      {	
	a=p2;
	b=p1;
      } else if (size2==4)
      {
	a=p1;
	b=p2;
      } else 
      {
		 
	CGAL::Bbox_2 test1(p1.left_vertex()->x(),p1.bottom_vertex()->y(), 
			           p1.right_vertex()->x() ,p1.top_vertex()->y());
	
	for(int i=0;i<size2;i++)
	  if( tmp=(p2[i].x()>=test1.xmin() && p2[i].x()<=test1.xmax() &&
              p2[i].y()>=test1.ymin() && p2[i].y()<=test1.ymax()))
			break;
		
	if(tmp)
	{
	  a=p1;
	  b=p2;
	}else
	{
	  a=p2;
	  b=p1;
	}

      }

       intersect=_inner_intersect_hexagon_predicate(a,b);

       if(intersect==false || b.size()==4)
         return intersect;
       else
         return _inner_intersect_hexagon_predicate(b,a);

   }

// This is meant for x_monotone and for non-x_monotone cases
template < typename Hex_iterator1, typename Hex_iterator2 >
bool do_intersect_hexagons_2(Hex_iterator1 a_begin, Hex_iterator1 a_end, Hex_iterator2 b_begin, Hex_iterator2 b_end)
  {

    for(Hex_iterator1 it1=a_begin;it1!=a_end;it1++)
      for(Hex_iterator2 it2=b_begin;it2!=b_end;it2++) 
	if( !(it2->top_vertex()->y() < it1->bottom_vertex()->y() || 
	      it2->bottom_vertex()->y() > it1->top_vertex()->y() ||     
	      it2->right_vertex()->x() < it1->left_vertex()->x() || 
	      it2->left_vertex()->x() > it1->right_vertex()->x() ))     
	{
	  bool tmp = _do_intersect_hexagon_2(*it1,*it2);
          if (tmp)
	    return true;
            
        }

	return false;

  }// do_intersect_hexagons_2


 }//namespace CGALi


//Lazy like functors that there is no use to be included in the kernel

template < class CK, class Hexagon>
  class Hexagon_construction_with_interval_2 {

  typedef typename CK::Circular_arc_2  Circular_arc_2;
  typedef typename CK::Line_arc_2  Line_arc_2;
  typedef CGAL::Simple_cartesian<CGAL::Interval_nt<> >                   FK;
  typedef CGAL::Circular_kernel_2< FK,CGAL::Algebraic_kernel_for_circles_2_2<FK::RT> >   CK2;
  typedef CGAL::Circular_kernel_converter<CK,CK2>                          Conv;

  public:

  template < class OutputIterator>
  OutputIterator  
  operator()(const Circular_arc_2 &a, OutputIterator res) const
    {
      Conv cnv;
      static const bool Protection = true;
      try{return CGALi::construct_bounding_hexagons_2<CK2>(cnv(a),res);}
      catch (Interval_nt_advanced::unsafe_comparison)
      {
         CGAL::Protect_FPU_rounding<!Protection> P(CGAL_FE_TONEAREST);
         return CGALi::construct_bounding_hexagons_2<CK>(a,res);
      }

   }

  Hexagon operator()(const Line_arc_2 &a) const
    {
      Conv cnv;
      static const bool Protection = true;
      try{return CGALi::construct_bounding_hexagon_for_line_arc_2<CK2>(cnv(a));}
      catch (Interval_nt_advanced::unsafe_comparison)
      {
         CGAL::Protect_FPU_rounding<!Protection> P(CGAL_FE_TONEAREST);
         return CGALi::construct_bounding_hexagon_for_line_arc_2<CK>(a);
      }

   }

};


template < class CK, class Hexagon>
 class Hexagon_construction_on_lazy_kernel_2 {

  typedef typename CK::Circular_arc_2  Circular_arc_2;
  typedef typename CK::Line_arc_2  Line_arc_2;

  public:

  template < class OutputIterator>
  OutputIterator  
  operator()(const Circular_arc_2 &a, OutputIterator res) const
    { 
      static const bool Protection = true;      
      try{return CGALi::construct_bounding_hexagons_2<typename CK::AK>(a.approx(),res);}
      catch (Interval_nt_advanced::unsafe_comparison)
      {
         CGAL::Protect_FPU_rounding<!Protection> P(CGAL_FE_TONEAREST);
         return CGALi::construct_bounding_hexagons_2<typename CK::EK>(a.exact(),res);
      }

   }

  Hexagon  operator()(const Line_arc_2 &a) const
    { 
      static const bool Protection = true;
      try{return CGALi::construct_bounding_hexagon_for_line_arc_2<typename CK::AK>(a.approx());}
      catch (Interval_nt_advanced::unsafe_comparison)
      {
         CGAL::Protect_FPU_rounding<!Protection> P(CGAL_FE_TONEAREST);
         return CGALi::construct_bounding_hexagon_for_line_arc_2<typename CK::EK>(a.exact());
      }

    }
};


}// namespace CGAL

#endif // CGAL_HEXAGON_PRIMITIVES_H