BWAPI: SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Circular_kernel_3/internal_functions_on_circle

Go to the documentation of this file.
00001 // Copyright (c) 2008  INRIA Sophia-Antipolis (France).
00002 // All rights reserved.
00003 //
00004 // This file is part of CGAL (www.cgal.org); you may redistribute it under
00005 // the terms of the Q Public License version 1.0.
00006 // See the file LICENSE.QPL distributed with CGAL.
00007 //
00008 // Licensees holding a valid commercial license may use this file in
00009 // accordance with the commercial license agreement provided with the software.
00010 //
00011 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00012 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00013 //
00014 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Circular_kernel_3/include/CGAL/Circular_kernel_3/internal_functions_on_circle_3.h $
00015 // $Id: internal_functions_on_circle_3.h 50731 2009-07-21 09:08:07Z sloriot $
00016 //
00017 // Author(s) : Monique Teillaud, Sylvain Pion, Pedro Machado, 
00018 //             Sebastien Loriot, Julien Hazebrouck, Damien Leroy
00019 
00020 // Partially supported by the IST Programme of the EU as a 
00021 // STREP (FET Open) Project under Contract No  IST-006413 
00022 // (ACS -- Algorithms for Complex Shapes)
00023 
00024 #ifndef CGAL_SPHERICAL_KERNEL_PREDICATES_ON_CIRCLE_3_H
00025 #define CGAL_SPHERICAL_KERNEL_PREDICATES_ON_CIRCLE_3_H
00026 
00027 #include <CGAL/Circle_type.h>
00028 #include <CGAL/Circular_kernel_3/internal_functions_on_plane_3.h>
00029 #include <CGAL/Circular_kernel_3/internal_functions_on_circular_arc_point_3.h>
00030 
00031 namespace CGAL {
00032   namespace SphericalFunctors {
00033             
00034     template < class SK >
00035     typename SK::Circle_3
00036     construct_circle_3(const typename SK::Polynomials_for_circle_3 &eq)
00037     {
00038       typedef typename SK::Point_3 Point_3;
00039       typedef typename SK::Plane_3 Plane_3;
00040       typedef typename SK::Circle_3 Circle_3;
00041       typedef typename SK::Sphere_3 Sphere_3;
00042       typedef typename SK::FT FT;
00043       Sphere_3 s = construct_sphere_3<SK>(eq.first);
00044       Plane_3 p = construct_plane_3<SK>(eq.second);
00045       const FT d2 = CGAL::square(p.a()*s.center().x() + 
00046                                  p.b()*s.center().y() + 
00047                                  p.c()*s.center().z() + p.d()) /
00048        (CGAL::square(p.a()) + CGAL::square(p.b()) + CGAL::square(p.c()));
00049       // We do not accept circles with radius 0 (should we?)
00050       CGAL_kernel_precondition(d2 <  s.squared_radius());
00051       // d2 < s.squared_radius()
00052       Point_3 center = p.projection(s.center());
00053       return Circle_3(center,s.squared_radius() - d2,p);
00054     }
00055 
00056 
00057     template < class SK >
00058     CGAL::Circle_type
00059     classify_circle_3(const typename SK::Circle_3& circle,const typename SK::Sphere_3& sphere)
00060     {
00061       typedef typename SK::Algebraic_kernel::Root_for_spheres_2_3   Root_for_spheres_2_3;
00062       typedef typename SK::Circular_arc_point_3                     Circular_arc_point_3;
00063       
00064       CGAL_kernel_precondition(SK().has_on_3_object()(sphere,circle));
00065       
00066       //if circle is a great circle, it can only be a bipolar or a threaded.
00067       if (circle.center()==sphere.center()){
00068         if (circle.supporting_plane().orthogonal_vector().z()==0)
00069           return CGAL::BIPOLAR;
00070         return CGAL::THREADED;
00071       }
00072       
00073       typename SK::Root_of_2 radius=CGAL::make_root_of_2(typename SK::FT(1),typename SK::FT(0),-sphere.squared_radius(),false);
00074       Circular_arc_point_3 north_pole( Root_for_spheres_2_3(sphere.center().x(),sphere.center().y(),sphere.center().z()+radius) );
00075       Circular_arc_point_3 south_pole( Root_for_spheres_2_3(sphere.center().x(),sphere.center().y(),sphere.center().z()-radius) );
00076 
00077 
00078       const typename SK::Sphere_3& supp_sphere=circle.diametral_sphere();
00079       typename SK::Bounded_side_3 bounded_side=SK().bounded_side_3_object();
00080       
00081 
00082       CGAL::Bounded_side side_of_north=bounded_side(supp_sphere,north_pole);
00083       CGAL::Bounded_side side_of_south=bounded_side(supp_sphere,south_pole);
00084       
00085       if (side_of_north==ON_BOUNDARY || side_of_south==ON_BOUNDARY)
00086         return CGAL::POLAR;
00087 
00088       if (side_of_north==ON_BOUNDED_SIDE || side_of_south==ON_BOUNDED_SIDE)
00089         return CGAL::THREADED;      
00090       
00091       CGAL_kernel_precondition(side_of_north==ON_UNBOUNDED_SIDE && side_of_south==ON_UNBOUNDED_SIDE);
00092       
00093       return CGAL::NORMAL;
00094     }
00095 
00096 
00097     template < class SK >
00098     inline typename SK::FT
00099     extremal_points_z_coordinate(const typename SK::Circle_3& circle,const typename SK::Sphere_3& sphere)
00100     {
00101       CGAL_kernel_precondition(SK().has_on_3_object()(sphere,circle));
00102       CGAL_kernel_precondition(classify_circle_3<SK>(circle,sphere)==CGAL::NORMAL);
00103       
00104       const typename SK::Point_3& circle_center=circle.center();
00105       const typename SK::Point_3& sphere_center=sphere.center();
00106 
00107       return
00108       typename SK::FT(2) * (circle_center-sphere_center).z() * sphere.squared_radius() 
00109                / ( SK().compute_squared_distance_3_object()(circle_center,sphere_center) + sphere.squared_radius()-circle.squared_radius() )
00110                + sphere_center.z();
00111     }
00112     
00113     template < class SK, class Output_iterator >
00114     Output_iterator theta_extremal_points(const typename SK::Circle_3& circle,const typename SK::Sphere_3& sphere,Output_iterator out_it){
00115       CGAL_kernel_precondition(classify_circle_3<SK>(circle,sphere)==NORMAL);
00116       CGAL_kernel_precondition(SK().has_on_3_object()(sphere,circle));
00117       
00118       typename SK::FT z_coord=extremal_points_z_coordinate<SK>(circle,sphere);
00119       
00120       typename SK::Plane_3 plane(0,0,1,-z_coord);
00121       std::vector<CGAL::Object> inters;
00122       
00123       intersect_3<SK>(circle,plane,std::back_inserter(inters));      
00124       CGAL_kernel_precondition(inters.size()==2);
00125       const std::pair<typename SK::Circular_arc_point_3,unsigned>* pt[2]={NULL,NULL};
00126       pt[0]=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[0]);
00127       pt[1]=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[1]);
00128       CGAL_kernel_precondition(pt[0]!=NULL);
00129       CGAL_kernel_precondition(pt[1]!=NULL);
00130       
00131       if ( compare_theta_of_pts<SK>(pt[0]->first,pt[1]->first,sphere) == SMALLER){
00132         *out_it++=pt[0]->first;
00133         *out_it++=pt[1]->first;
00134       }
00135       else{
00136         *out_it++=pt[1]->first;
00137         *out_it++=pt[0]->first;
00138       }
00139         
00140       return out_it;
00141     }
00142     
00143     template < class SK >
00144     typename SK::Circular_arc_point_3 theta_extremal_point(const typename SK::Circle_3& circle,const typename SK::Sphere_3& sphere,bool is_smallest){
00145       typename SK::Circular_arc_point_3 pts[2];
00146       theta_extremal_points(circle,sphere,pts);
00147       if (is_smallest)
00148         return pts[0];
00149       return pts[1];
00150     }
00151     
00152     template < class SK,class Output_iterator>
00153     Output_iterator make_circle_theta_monotone(const typename SK::Circle_3& circle,const typename SK::Sphere_3& sphere,Output_iterator out_it){
00154       CGAL::Circle_type type=classify_circle_3<SK>(circle,sphere);
00155       switch (type){
00156         case THREADED:
00157         {
00158           *out_it++=typename SK::Circular_arc_3(circle);
00159           break;
00160         }  
00161         case POLAR:{
00162           typename SK::Vector_3 ortho=circle.center()-sphere.center();
00163           CGAL_kernel_precondition(ortho.z()!=0);
00164           bool is_north_pole=ortho.z()>0;
00165           typename SK::Root_of_2 radius = make_root_of_2(typename SK::FT(1),typename SK::FT(0),-sphere.squared_radius(),!is_north_pole);
00166           typename SK::Circular_arc_point_3 source_target(
00167             typename SK::Algebraic_kernel::Root_for_spheres_2_3(
00168               sphere.center().x(),
00169               sphere.center().y(),
00170               sphere.center().z()+radius
00171             )
00172           );
00173           *out_it++=typename SK::Circular_arc_3(circle,source_target);
00174           break;
00175         }
00176         case NORMAL:{
00177           typename SK::Circular_arc_point_3 ints[2];
00178           theta_extremal_points(circle,sphere,ints);
00179           *out_it++=typename SK::Circular_arc_3(circle,ints[0],ints[1]);
00180           *out_it++=typename SK::Circular_arc_3(circle,ints[1],ints[0]);
00181         }
00182         break;
00183         case BIPOLAR:
00184           CGAL_kernel_precondition(!"This function does not accept bipolar circle as input.");
00185       }
00186       return out_it;
00187     }
00188     
00189 
00190     
00191   }//SphericalFunctors
00192 }//CGAL
00193 
00194 #endif //CGAL_SPHERICAL_KERNEL_PREDICATES_ON_CIRCLE_3_H