|
BWAPI
|
00001 // Copyright (c) 2005-2009 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 // Partially supported by the IST Programme of the EU as a Shared-cost 00015 // RTD (FET Open) Project under Contract No IST-2000-26473 00016 // (ECG - Effective Computational Geometry for Curves and Surfaces) 00017 // and a STREP (FET Open) Project under Contract No IST-006413 00018 // (ACS -- Algorithms for Complex Shapes) 00019 // 00020 // $URL: $ 00021 // $Id: internal_function_compare_to_right_spherical_kernel.h 40627 2007-10-16 15:00:59Z sloriot $ 00022 // 00023 // Author(s) : Sebastien Loriot 00024 00025 00026 #ifndef CGAL_SPHERICAL_KERNEL_PREDICATES_COMPARE_TO_RIGHT_H 00027 #define CGAL_SPHERICAL_KERNEL_PREDICATES_COMPARE_TO_RIGHT_H 00028 00029 namespace CGAL { 00030 namespace SphericalFunctors { 00031 00032 //Traits providing primitives to compare two theta-monotone circular arc to the right of a common point Pt 00033 template <class SK> 00034 struct Trait_for_cmp_tgt{ 00035 typename SK::Algebraic_kernel::Root_for_spheres_2_3 Pt_; 00036 typedef typename SK::Algebraic_kernel::Root_of_2 Tk_type; 00037 00038 Trait_for_cmp_tgt(const typename SK::Algebraic_kernel::Root_for_spheres_2_3& Pt, 00039 const typename SK::Sphere_3& sphere) 00040 :Pt_(Pt.x()-sphere.center().x(),Pt.y()-sphere.center().y(),Pt.z()-sphere.center().z()){} 00041 00042 typename SK::Algebraic_kernel::Root_of_2 00043 unsigned_tkz_coeff_normal(const typename SK::Point_3& C, 00044 const typename SK::FT& rk, 00045 const typename SK::FT& R, 00046 const typename SK::FT& gamma_k 00047 ) const 00048 { 00049 return CGAL_NTS sign(gamma_k)*(C.x()*Pt_.y()-C.y()*Pt_.x()); 00050 } 00051 00052 Tk_type 00053 unsigned_tkz_coeff_threaded(const typename SK::Point_3& C) const { 00054 return C.x()*Pt_.y()-C.y()*Pt_.x(); 00055 } 00056 00057 }; 00058 00059 // Same as Trait_for_cmp_tgt but in the case where common point is at theta=0 00060 template <class SK> 00061 struct Trait_for_cmp_tgt_theta_0{ 00062 typename SK::Algebraic_kernel::Root_for_spheres_2_3 Pt_; 00063 typedef typename SK::FT Tk_type; 00064 00065 Trait_for_cmp_tgt_theta_0(const typename SK::Algebraic_kernel::Root_for_spheres_2_3& Pt, 00066 const typename SK::Sphere_3& sphere) 00067 :Pt_(Pt.x()-sphere.center().x(),Pt.y()-sphere.center().y(),Pt.z()-sphere.center().z()){} 00068 00069 typename SK::FT 00070 unsigned_tkz_coeff_normal( const typename SK::Point_3& C, 00071 const typename SK::FT& rk, 00072 const typename SK::FT& R, 00073 const typename SK::FT& gamma_k 00074 ) const 00075 { 00076 return - CGAL_NTS sign(gamma_k)*C.y(); 00077 } 00078 00079 Tk_type 00080 unsigned_tkz_coeff_threaded(const typename SK::Point_3& C) const{ 00081 return -C.y(); 00082 } 00083 }; 00084 00085 // Class to compare two theta-monotone circular arc to the right of a common point. 00086 // This class need a traits class which can be either Trait_for_cmp_tgt or Trait_for_cmp_tgt_theta_0 00087 //depending on the properties of the point. 00088 template<class SK,class Traits> 00089 struct Compare_to_right_of_arcs{ 00090 Traits traits_; 00091 const typename SK::Sphere_3& sphere_; 00092 00093 Compare_to_right_of_arcs(const Traits& traits,const typename SK::Sphere_3& sphere): 00094 traits_(traits),sphere_(sphere){} 00095 00096 typename SK::FT 00097 gamma_k ( const typename SK::Point_3& c, 00098 const typename SK::FT& rk, 00099 const typename SK::FT& R, 00100 typename SK::FT& ak2) const 00101 { 00102 ak2=c.x()*c.x()+c.y()*c.y()+c.z()*c.z(); 00103 return (ak2+R-rk)/(2.*ak2); 00104 } 00105 00106 typename SK::FT 00107 gamma_k (const typename SK::Point_3& c, 00108 const typename SK::FT& rk, 00109 const typename SK::FT& R) const 00110 { 00111 typename SK::FT ak2=c.x()*c.x()+c.y()*c.y()+c.z()*c.z(); 00112 return (ak2+R-rk)/(2.*ak2); 00113 } 00114 00115 bool is_arc_an_upper_one(const typename SK::Circular_arc_3& arc,const typename SK::Sphere_3& sphere) const { 00116 CGAL::Circle_type type=classify_circle_3<SK>(arc.supporting_circle(),sphere); 00117 if ( type==CGAL::NORMAL) 00118 return extremal_points_z_coordinate<SK>(arc.supporting_circle(),sphere)-sphere.center().z() < traits_.Pt_.z(); 00119 CGAL_kernel_precondition(type==POLAR); 00120 return arc.supporting_circle().center().z() < sphere.center().z() ; 00121 } 00122 00123 00124 typename SK::FT square_norm_tk_normal (const typename SK::Point_3& c,const typename SK::FT& rk,const typename SK::FT& R) const; 00125 typename SK::FT square_norm_tk_threaded (const typename SK::Point_3& c,const typename SK::FT& rk,const typename SK::FT& R) const; 00126 void fill_tzk_n(const typename SK::Circular_arc_3& arc,typename Traits::Tk_type& tz,typename SK::FT& n,bool is_supporting_circle_threaded) const; 00127 int sign_of_delta(const typename SK::Circular_arc_3& arc1,bool circle1_threaded,const typename SK::Circular_arc_3& arc2,bool circle2_threaded) const; 00128 typename SK::FT give_rk(const typename SK::Circular_arc_3& arc) const; 00129 int compare_for_delta_eq_0_threaded(const typename SK::Circular_arc_3& arc_threaded,const typename SK::Circular_arc_3& arc,bool circle_threaded) const; 00130 int compare_for_delta_eq_0(const typename SK::Circular_arc_3& arc1,bool circle1_threaded,const typename SK::Circular_arc_3& arc2,bool circle2_threaded) const; 00131 CGAL::Comparison_result operator()(const typename SK::Circular_arc_3& arc1,const typename SK::Circular_arc_3& arc2,bool do_it_to_left=false) const; 00132 }; 00133 00134 00135 template<class SK,class Traits> 00136 typename SK::FT 00137 Compare_to_right_of_arcs<SK,Traits>::square_norm_tk_normal( 00138 const typename SK::Point_3& c, 00139 const typename SK::FT& rk, 00140 const typename SK::FT& R) const 00141 { 00142 typename SK::FT ak2; 00143 typename SK::FT gk=gamma_k(c,rk,R,ak2); 00144 return ak2 * (R - gk * gk * ak2); 00145 }; 00146 00147 template<class SK,class Traits> 00148 typename SK::FT 00149 Compare_to_right_of_arcs<SK,Traits>::square_norm_tk_threaded( 00150 const typename SK::Point_3& c, 00151 const typename SK::FT& rk, 00152 const typename SK::FT& R) const 00153 { 00154 typename SK::FT ak2; 00155 typename SK::FT gk=gamma_k(c,rk,R,ak2); 00156 return ak2 * (R - gk * gk * ak2); 00157 }; 00158 00159 template<class SK,class Traits> 00160 void 00161 Compare_to_right_of_arcs<SK,Traits>::fill_tzk_n( 00162 const typename SK::Circular_arc_3& arc, 00163 typename Traits::Tk_type& tz, 00164 typename SK::FT& n, 00165 bool is_supporting_circle_threaded) const 00166 { 00167 if (is_supporting_circle_threaded){ 00168 //use a pseudo-sphere whose center is translated by ortho from the center 00169 // of the circle 00170 //~ tz=traits_.unsigned_tkz_coeff_threaded(arc.supporting_circle().supporting_sphere_center()); 00171 typename SK::Vector_3 ortho=arc.supporting_circle().supporting_plane().orthogonal_vector(); 00172 tz=traits_.unsigned_tkz_coeff_threaded(CGAL::ORIGIN+ortho); 00173 //~ tz*=(CGAL::pole_covered_by_supporting_sphere<SK>(arc.supporting_circle())==CGAL::NPOLE)?(1):(-1); 00174 if (ortho.z() <= 0) 00175 tz=-tz; 00176 //~ tz*= ( (ortho.z() > 0)?(1):(-1) ); 00177 //~ n=square_norm_tk_threaded(arc.supporting_circle().supporting_sphere_center(), 00178 //~ arc.supporting_circle().supporting_sphere_squared_radius(), 00179 //~ sphere_.squared_radius()); 00180 n=square_norm_tk_threaded(CGAL::ORIGIN+ortho, 00181 arc.supporting_circle().squared_radius() + ortho.squared_length(), 00182 sphere_.squared_radius()); 00183 //warning : down to here 00184 } 00185 else{ 00186 typename SK::Point_3 tmp_pt=typename SK::Point_3(0.,0.,0.) + (arc.supporting_circle().center()-sphere_.center()); 00187 typename SK::FT gk= 00188 gamma_k(tmp_pt, 00189 arc.supporting_circle().squared_radius(), 00190 sphere_.squared_radius()); 00191 00192 tz=traits_.unsigned_tkz_coeff_normal(tmp_pt, 00193 arc.supporting_circle().squared_radius(), 00194 sphere_.squared_radius(), 00195 gk); 00196 if ( is_arc_an_upper_one(arc,sphere_) ) 00197 tz=-tz; 00198 //~ tz*=is_arc_an_upper_one(arc,sphere_)?(-1):(1); 00199 n=square_norm_tk_normal(tmp_pt, 00200 arc.supporting_circle().squared_radius(), 00201 sphere_.squared_radius()); 00202 } 00203 }; 00204 00205 00206 template<class SK,class Traits> 00207 int 00208 Compare_to_right_of_arcs<SK,Traits>::sign_of_delta( 00209 const typename SK::Circular_arc_3& arc1, bool is_circle_1_threaded, 00210 const typename SK::Circular_arc_3& arc2, bool is_circle_2_threaded) const 00211 { 00212 typename Traits::Tk_type tz1,tz2; 00213 typename SK::FT n1,n2; 00214 fill_tzk_n(arc1,tz1,n1,is_circle_1_threaded); 00215 fill_tzk_n(arc2,tz2,n2,is_circle_2_threaded); 00216 if (tz1==0 && tz2==0) 00217 return 0; 00218 if (tz1==0) 00219 return CGAL_NTS sign(tz2); 00220 if (tz2==0) 00221 return -CGAL_NTS sign(tz1); 00222 00223 if (CGAL_NTS sign(tz1)!=CGAL_NTS sign(tz2)) 00224 return CGAL_NTS sign(tz2); 00225 return CGAL_NTS sign(tz2)*CGAL_NTS sign(n1*CGAL::square(tz2)-n2*CGAL::square(tz1)); 00226 }; 00227 00228 00229 template<class SK,class Traits> 00230 typename SK::FT 00231 Compare_to_right_of_arcs<SK,Traits>::give_rk( 00232 const typename SK::Circular_arc_3& arc) const 00233 { 00234 return (is_arc_an_upper_one(arc,sphere_)?(1):(-1))*arc.supporting_circle().squared_radius(); 00235 }; 00236 00237 template<class SK,class Traits> 00238 int 00239 Compare_to_right_of_arcs<SK,Traits>::compare_for_delta_eq_0_threaded( 00240 const typename SK::Circular_arc_3& arc_threaded, 00241 const typename SK::Circular_arc_3& arc, 00242 bool is_supporting_circle_threaded) const 00243 { 00244 if (!is_supporting_circle_threaded) 00245 return ( is_upper_arc<SK>(arc,sphere_) )?(-1):(1); //IN THAT CASE WE CAN OPTIMIZE AND USE THE Z-COORDINATES OF THE POINT AND CIRCLE THETA-EXTREMAL PT 00246 return (-CGAL_NTS sign(arc_threaded.supporting_circle().center().z()-arc.supporting_circle().center().z())); 00247 }; 00248 00249 template<class SK,class Traits> 00250 int 00251 Compare_to_right_of_arcs<SK,Traits>::compare_for_delta_eq_0( 00252 const typename SK::Circular_arc_3& arc1, 00253 bool is_circle_1_threaded, 00254 const typename SK::Circular_arc_3& arc2, 00255 bool is_circle_2_threaded) const 00256 { 00257 if (is_circle_1_threaded) 00258 return compare_for_delta_eq_0_threaded(arc1,arc2,is_circle_2_threaded); 00259 if (is_circle_2_threaded) 00260 return -compare_for_delta_eq_0_threaded(arc2,arc1,is_circle_1_threaded); 00261 typename SK::FT rc1=give_rk(arc1); 00262 typename SK::FT rc2=give_rk(arc2); 00263 CGAL_precondition(rc1!=0 && rc2!=0); 00264 if(CGAL_NTS sign(rc1)*CGAL_NTS sign(rc2)<0) 00265 return (CGAL_NTS sign(rc1)>0)?(1):(-1); 00266 return (rc1<rc2)?(1):(-1); 00267 }; 00268 00269 00270 template<class SK,class Traits> 00271 CGAL::Comparison_result Compare_to_right_of_arcs<SK,Traits>::operator()( 00272 const typename SK::Circular_arc_3& arc1, 00273 const typename SK::Circular_arc_3& arc2, 00274 bool do_it_to_left 00275 ) const 00276 { 00277 bool is_circle_1_threaded = (classify_circle_3<SK>(arc1.supporting_circle(),sphere_)==CGAL::THREADED); 00278 bool is_circle_2_threaded = (classify_circle_3<SK>(arc2.supporting_circle(),sphere_)==CGAL::THREADED); 00279 00280 int res=(do_it_to_left?-1:1)*sign_of_delta(arc1,is_circle_1_threaded,arc2,is_circle_2_threaded); 00281 if (res==0) 00282 res=compare_for_delta_eq_0(arc1,is_circle_1_threaded,arc2,is_circle_2_threaded); 00283 CGAL_precondition(res!=0); 00284 if (res<0) return CGAL::LARGER; 00285 return CGAL::SMALLER; 00286 }; 00287 00288 } 00289 } 00290 00291 #endif //CGAL_SPHERICAL_KERNEL_PREDICATES_COMPARE_TO_RIGHT_H
1.7.6.1
