|
BWAPI
|
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_circular_arc_3.h $ 00015 // $Id: internal_functions_on_circular_arc_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_CIRCULAR_ARC_3_H 00025 #define CGAL_SPHERICAL_KERNEL_PREDICATES_ON_CIRCULAR_ARC_3_H 00026 00027 #include <CGAL/Circular_kernel_3/internal_function_has_on_spherical_kernel.h> 00028 #include <CGAL/Circular_kernel_3/internal_functions_on_circle_3.h> 00029 00030 namespace CGAL { 00031 namespace SphericalFunctors { 00032 00033 template< class SK> 00034 bool 00035 equal( const typename SK::Circular_arc_3 &c1, 00036 const typename SK::Circular_arc_3 &c2) 00037 { 00038 return c1.rep() == c2.rep(); 00039 } 00040 00041 template <class SK> 00042 inline 00043 bool 00044 do_overlap(const typename SK::Circular_arc_3 &c1, 00045 const typename SK::Circular_arc_3 &c2, 00046 const bool known_equal_supporting_circle = false) 00047 { 00048 if(!known_equal_supporting_circle) { 00049 if(!non_oriented_equal<SK>(c1.supporting_circle(), 00050 c2.supporting_circle())) 00051 return false; 00052 } 00053 if(c1.rep().is_full()) return true; 00054 if(c2.rep().is_full()) return true; 00055 if((SK().has_on_3_object()(c1,c2.target(),true)) || 00056 (SK().has_on_3_object()(c1,c2.source(),true))) return true; 00057 return SK().has_on_3_object()(c2,c1.source(),true); 00058 } 00059 00060 template < class SK > 00061 void 00062 split(const typename SK::Circular_arc_3 &c, 00063 const typename SK::Circular_arc_point_3 &p, 00064 typename SK::Circular_arc_3 &c1, 00065 typename SK::Circular_arc_3 &c2) 00066 { 00067 // The point must be on the circular arc 00068 CGAL_kernel_precondition(SK().has_on_3_object()(c, p)); 00069 typedef typename SK::Circular_arc_3 Circular_arc_3; 00070 // It doesn't make sense to split an arc on an extremity 00071 CGAL_kernel_precondition(c.source() != p); 00072 CGAL_kernel_precondition(c.target() != p); 00073 const Circular_arc_3 &rc1 = 00074 Circular_arc_3(c.supporting_circle(), c.source(), p); 00075 const Circular_arc_3 &rc2 = 00076 Circular_arc_3(c.supporting_circle(), p, c.target()); 00077 if ( SK().compare_xyz_3_object()(rc1.source(), rc2.source()) != 00078 SMALLER) { 00079 c1 = rc2; c2 = rc1; 00080 } else { c1 = rc1; c2 = rc2; } 00081 } 00082 00083 template < class SK, class OutputIterator > 00084 OutputIterator 00085 intersect_3(const typename SK::Line_3 & l, 00086 const typename SK::Circular_arc_3 & ca, 00087 OutputIterator res) 00088 { 00089 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00090 typedef std::vector<CGAL::Object> solutions_container; 00091 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00092 00093 solutions_container solutions; 00094 00095 SK().intersect_3_object()(l, ca.supporting_circle(), 00096 std::back_inserter(solutions) ); 00097 if(solutions.size() == 0) return res; 00098 if(solutions.size() == 1) { 00099 const Solution& sol=*object_cast<Solution>(&solutions[0]); 00100 if(SK().has_on_3_object()(ca,sol.first,true)) 00101 *res++ = solutions[0]; 00102 } else { 00103 const Solution& sol1=*object_cast<Solution>(&solutions[0]); 00104 const Solution& sol2=*object_cast<Solution>(&solutions[1]); 00105 if(SK().has_on_3_object()(ca,sol1.first,true)) 00106 *res++ = solutions[0]; 00107 if(SK().has_on_3_object()(ca,sol2.first,true)) 00108 *res++ = solutions[1]; 00109 } 00110 return res; 00111 } 00112 00113 template < class SK, class OutputIterator > 00114 OutputIterator 00115 intersect_3(const typename SK::Circle_3 & c, 00116 const typename SK::Circular_arc_3 & ca, 00117 OutputIterator res) 00118 { 00119 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00120 typedef std::vector<CGAL::Object> solutions_container; 00121 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00122 00123 if(non_oriented_equal<SK>(c, ca.supporting_circle())) { 00124 *res++ = make_object(ca); 00125 } 00126 00127 solutions_container solutions; 00128 00129 SK().intersect_3_object()(ca.supporting_circle(), c, 00130 std::back_inserter(solutions) ); 00131 if(solutions.size() == 0) return res; 00132 if(solutions.size() == 1) { 00133 const Solution& sol=*object_cast<Solution>(&solutions[0]); 00134 if(SK().has_on_3_object()(ca,sol.first,true)) 00135 *res++ = solutions[0]; 00136 } else { 00137 const Solution& sol1=*object_cast<Solution>(&solutions[0]); 00138 const Solution& sol2=*object_cast<Solution>(&solutions[1]); 00139 if(SK().has_on_3_object()(ca,sol1.first,true)) 00140 *res++ = solutions[0]; 00141 if(SK().has_on_3_object()(ca,sol2.first,true)) 00142 *res++ = solutions[1]; 00143 } 00144 return res; 00145 } 00146 00147 template < class SK, class OutputIterator > 00148 OutputIterator 00149 intersect_3(const typename SK::Sphere_3 & s, 00150 const typename SK::Circular_arc_3 & c, 00151 OutputIterator res) 00152 { 00153 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00154 typedef std::vector<CGAL::Object> solutions_container; 00155 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00156 00157 if(SK().has_on_3_object()(s, c.supporting_circle())) { 00158 *res++ = make_object(c); 00159 } 00160 00161 solutions_container solutions; 00162 00163 SK().intersect_3_object()(c.supporting_circle(), s, 00164 std::back_inserter(solutions) ); 00165 if(solutions.size() == 0) return res; 00166 if(solutions.size() == 1) { 00167 const Solution& sol=*object_cast<Solution>(&solutions[0]); 00168 if(SK().has_on_3_object()(c,sol.first,true)) 00169 *res++ = solutions[0]; 00170 } else { 00171 const Solution& sol1=*object_cast<Solution>(&solutions[0]); 00172 const Solution& sol2=*object_cast<Solution>(&solutions[1]); 00173 if(SK().has_on_3_object()(c,sol1.first,true)) 00174 *res++ = solutions[0]; 00175 if(SK().has_on_3_object()(c,sol2.first,true)) 00176 *res++ = solutions[1]; 00177 } 00178 return res; 00179 } 00180 00181 template < class SK, class OutputIterator > 00182 OutputIterator 00183 intersect_3(const typename SK::Plane_3 & p, 00184 const typename SK::Circular_arc_3 & ca, 00185 OutputIterator res) 00186 { 00187 typedef typename SK::Point_3 Point_3; 00188 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00189 typedef std::vector<CGAL::Object> solutions_container; 00190 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00191 if(SK().has_on_3_object()(p,ca.supporting_circle())) { 00192 *res++ = make_object(ca); 00193 } 00194 solutions_container solutions; 00195 00196 SK().intersect_3_object()(ca.supporting_circle(), p, 00197 std::back_inserter(solutions) ); 00198 if(solutions.size() == 0) return res; 00199 if(solutions.size() == 1) { 00200 const Solution& sol=*object_cast<Solution>(&solutions[0]); 00201 if(SK().has_on_3_object()(ca,sol.first,true)) 00202 *res++ = solutions[0]; 00203 } else { 00204 const Solution& sol1=*object_cast<Solution>(&solutions[0]); 00205 const Solution& sol2=*object_cast<Solution>(&solutions[1]); 00206 if(SK().has_on_3_object()(ca,sol1.first,true)) 00207 *res++ = solutions[0]; 00208 if(SK().has_on_3_object()(ca,sol2.first,true)) 00209 *res++ = solutions[1]; 00210 } 00211 return res; 00212 } 00213 00214 template < class SK, class OutputIterator > 00215 OutputIterator 00216 intersect_3(const typename SK::Line_arc_3 & la, 00217 const typename SK::Circular_arc_3 & ca, 00218 OutputIterator res) 00219 { 00220 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00221 typedef std::vector<CGAL::Object> solutions_container; 00222 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00223 00224 solutions_container solutions; 00225 00226 SK().intersect_3_object()(la.supporting_line(), ca.supporting_circle(), 00227 std::back_inserter(solutions) ); 00228 if(solutions.size() == 0) return res; 00229 if(solutions.size() == 1) { 00230 const Solution& sol=*object_cast<Solution>(&solutions[0]); 00231 if(SK().has_on_3_object()(ca,sol.first,true) && 00232 SK().has_on_3_object()(la,sol.first,true)) 00233 *res++ = solutions[0]; 00234 } else { 00235 const Solution& sol1=*object_cast<Solution>(&solutions[0]); 00236 const Solution& sol2=*object_cast<Solution>(&solutions[1]); 00237 if(SK().has_on_3_object()(ca,sol1.first,true) && 00238 SK().has_on_3_object()(la,sol1.first,true)) 00239 *res++ = solutions[0]; 00240 if(SK().has_on_3_object()(ca,sol2.first,true) && 00241 SK().has_on_3_object()(la,sol2.first,true)) 00242 *res++ = solutions[1]; 00243 } 00244 return res; 00245 } 00246 00247 template < class SK, class OutputIterator > 00248 OutputIterator 00249 intersect_3(const typename SK::Circular_arc_3 & a1, 00250 const typename SK::Circular_arc_3 & a2, 00251 OutputIterator res) 00252 { 00253 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00254 typedef typename SK::Circular_arc_3 Circular_arc_3; 00255 typedef std::vector<CGAL::Object> solutions_container; 00256 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00257 00258 if(non_oriented_equal<SK>(a1.supporting_circle(), a2.supporting_circle())) { 00259 if(a1.rep().is_full()) { 00260 *res++ = make_object(a2); 00261 //return res; 00262 } 00263 else if(a2.rep().is_full()) { 00264 *res++ = make_object(a1); 00265 //return res; 00266 } else { 00267 bool t2_in_a1 = SK().has_on_3_object()(a1,a2.target(),true); 00268 bool s2_in_a1 = SK().has_on_3_object()(a1,a2.source(),true); 00269 if(t2_in_a1 && s2_in_a1) { 00270 bool t1_in_a2 = SK().has_on_3_object()(a2,a1.target(),true); 00271 bool s1_in_a2 = SK().has_on_3_object()(a2,a1.source(),true); 00272 if(t1_in_a2 && s1_in_a2) { 00273 const Comparison_result comp = 00274 SK().compare_xyz_3_object()(a1.source(), a2.source()); 00275 if(comp < 0) { 00276 if(a1.source() == a2.target()) { 00277 *res++ = make_object(std::make_pair(a1.source(),1u)); 00278 } else { 00279 const Circular_arc_3 & arc = 00280 Circular_arc_3(a1.supporting_circle(),a1.source(),a2.target()); 00281 *res++ = make_object(arc); 00282 } 00283 if(a2.source() == a1.target()) { 00284 *res++ = make_object(std::make_pair(a2.source(),1u)); 00285 } else { 00286 const Circular_arc_3 & arc = 00287 Circular_arc_3(a1.supporting_circle(),a2.source(),a1.target()); 00288 *res++ = make_object(arc); 00289 } 00290 } else if(comp > 0) { 00291 if(a2.source() == a1.target()) { 00292 *res++ = make_object(std::make_pair(a2.source(),1u)); 00293 } else { 00294 const Circular_arc_3 & arc = 00295 Circular_arc_3(a1.supporting_circle(),a2.source(),a1.target()); 00296 *res++ = make_object(arc); 00297 } 00298 if(a1.source() == a2.target()) { 00299 *res++ = make_object(std::make_pair(a1.source(),1u)); 00300 } else { 00301 const Circular_arc_3 & arc = 00302 Circular_arc_3(a1.supporting_circle(),a1.source(),a2.target()); 00303 *res++ = make_object(arc); 00304 } 00305 } else { 00306 *res++ = make_object(a1); 00307 } 00308 } else { 00309 *res++ = make_object(a2); 00310 } 00311 } else if(t2_in_a1) { 00312 if(a1.source() == a2.target()) 00313 *res++ = make_object(std::make_pair(a1.source(),1u)); 00314 else { 00315 const Circular_arc_3 & arc = 00316 Circular_arc_3(a1.supporting_circle(),a1.source(),a2.target()); 00317 *res++ = make_object(arc); 00318 } //return res; 00319 } else if(s2_in_a1) { 00320 if(a2.source() == a1.target()) { 00321 *res++ = make_object(std::make_pair(a2.source(),1u)); 00322 } else { 00323 const Circular_arc_3 & arc = 00324 Circular_arc_3(a1.supporting_circle(),a2.source(),a1.target()); 00325 *res++ = make_object(arc); 00326 } 00327 } else if(SK().has_on_3_object()(a2,a1.source(),true)) { 00328 *res++ = make_object(a1); 00329 } 00330 } 00331 } else { 00332 solutions_container solutions; 00333 00334 SK().intersect_3_object()(a1.supporting_circle(), a2.supporting_circle(), 00335 std::back_inserter(solutions) ); 00336 if(solutions.size() == 0) return res; 00337 if(solutions.size() == 1) { 00338 const Solution& sol=*object_cast<Solution>(&solutions[0]); 00339 if(SK().has_on_3_object()(a1,sol.first,true) && 00340 SK().has_on_3_object()(a2,sol.first,true)) 00341 *res++ = solutions[0]; 00342 } else { 00343 const Solution& sol1=*object_cast<Solution>(&solutions[0]); 00344 const Solution& sol2=*object_cast<Solution>(&solutions[1]); 00345 if(SK().has_on_3_object()(a1,sol1.first,true) && 00346 SK().has_on_3_object()(a2,sol1.first,true)) 00347 *res++ = solutions[0]; 00348 if(SK().has_on_3_object()(a1,sol2.first,true) && 00349 SK().has_on_3_object()(a2,sol2.first,true)) 00350 *res++ = solutions[1]; 00351 } 00352 } 00353 return res; 00354 } 00355 00356 template < class SK> 00357 bool 00358 is_theta_monotone_3(const typename SK::Circular_arc_3 & arc,const typename SK::Sphere_3& sphere) 00359 { 00360 CGAL_kernel_precondition(SK().has_on_3_object()(sphere,arc)); 00361 CGAL::Circle_type type=classify_circle_3<SK>(arc.supporting_circle(),sphere); 00362 CGAL_kernel_precondition(type!=CGAL::BIPOLAR); 00363 if (type==THREADED) 00364 return true; 00365 if (type==POLAR){ 00366 bool circle_contains_north = arc.supporting_circle().center().z() > sphere.center().z(); 00367 typename SK::Root_of_2 radius=make_root_of_2(typename SK::FT(0),typename SK::FT(1),sphere.squared_radius()); 00368 typename SK::Circular_arc_point_3 pole ( 00369 typename SK::Algebraic_kernel::Root_for_spheres_2_3( sphere.center().x(), 00370 sphere.center().y(), 00371 sphere.center().z()+(circle_contains_north?1:-1)*radius 00372 ) 00373 ); 00374 00375 if (arc.source().z()==pole.z() || arc.target().z()==pole.z()) 00376 return true; 00377 00378 return !has_on<SK>(arc,pole); 00379 } 00380 00381 00382 typename SK::FT z_coord=extremal_points_z_coordinate<SK>(arc.supporting_circle(),sphere); 00383 typename SK::Plane_3 plane(0,0,1,-z_coord); 00384 std::vector<CGAL::Object> inters; 00385 00386 intersect_3<SK>(plane,arc,std::back_inserter(inters)); 00387 00388 if (inters.empty()) 00389 return true; 00390 00391 //checks whether circular arc endpoints are theta extremal 00392 unsigned nb_extrem = (arc.source().z()-z_coord == 0)? 1:0; 00393 if (arc.target().z()-z_coord == 0) ++nb_extrem; 00394 00395 if (inters.size()==nb_extrem) 00396 return true; 00397 00398 return false; 00399 } 00400 00401 template < class SK,class Output_iterator> 00402 Output_iterator 00403 make_circular_arc_theta_monotone( const typename SK::Circular_arc_3& arc, 00404 const typename SK::Sphere_3& sphere, 00405 Output_iterator out_it) 00406 { 00407 CGAL::Circle_type type=classify_circle_3<SK>(arc.supporting_circle(),sphere); 00408 CGAL_kernel_precondition(type!=BIPOLAR); 00409 switch (type){ 00410 case THREADED: 00411 case POLAR:{ 00412 bool circle_contains_north = arc.supporting_circle().center().z() > sphere.center().z(); 00413 typename SK::Root_of_2 radius=make_root_of_2(typename SK::FT(0),typename SK::FT(1),sphere.squared_radius()); 00414 typename SK::Circular_arc_point_3 pole ( 00415 typename SK::Algebraic_kernel::Root_for_spheres_2_3( sphere.center().x(), 00416 sphere.center().y(), 00417 sphere.center().z()+(circle_contains_north?1:-1)*radius 00418 ) 00419 ); 00420 00421 if (arc.source().z()==pole.z() || arc.target().z()==pole.z()) 00422 *out_it++=arc; 00423 else{ 00424 if ( has_on<SK>(arc,pole) ){ 00425 *out_it++=typename SK::Circular_arc_3(arc.supporting_circle(),arc.source(),pole); 00426 *out_it++=typename SK::Circular_arc_3(arc.supporting_circle(),pole,arc.target()); 00427 } 00428 else 00429 *out_it++=arc; 00430 } 00431 } 00432 break; 00433 case NORMAL:{ 00434 typename SK::FT z_coord=extremal_points_z_coordinate<SK>(arc.supporting_circle(),sphere); 00435 typename SK::Plane_3 plane(0,0,1,-z_coord); 00436 std::vector<CGAL::Object> inters; 00437 00438 intersect_3<SK>(plane,arc,std::back_inserter(inters)); 00439 00440 //No intersection with horizontal plane: theta-monotone 00441 if (inters.empty()){ 00442 *out_it++=arc; 00443 break; 00444 } 00445 00446 //check if endpoints of circular arc are theta extremal points 00447 unsigned nb_extrem = (arc.source().z()-z_coord == 0)? 1:0; 00448 if (arc.target().z()-z_coord == 0) ++nb_extrem; 00449 00450 if (inters.size()==nb_extrem){ 00451 *out_it++=arc; 00452 break; 00453 } 00454 00455 //one endpoint is extremal: just split the arc 00456 if (nb_extrem==1){ 00457 const std::pair<typename SK::Circular_arc_point_3,unsigned>* pt[2]={NULL,NULL}; 00458 pt[0]=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[0]); 00459 pt[1]=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[1]); 00460 CGAL_kernel_precondition(pt[0]!=NULL); 00461 CGAL_kernel_precondition(pt[1]!=NULL); 00462 const typename SK::Circular_arc_point_3& midpt=(arc.source()==pt[0]->first || arc.target()==pt[0]->first)?pt[1]->first:pt[0]->first; 00463 *out_it++=typename SK::Circular_arc_3(arc.supporting_circle(),arc.source(),midpt); 00464 *out_it++=typename SK::Circular_arc_3(arc.supporting_circle(),midpt,arc.target()); 00465 break; 00466 } 00467 00468 CGAL_kernel_precondition(nb_extrem==0); 00469 00470 //only one intersection points 00471 if (inters.size()==1){ 00472 const std::pair<typename SK::Circular_arc_point_3,unsigned>* midpt=NULL; 00473 midpt=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[0]); 00474 CGAL_kernel_precondition(midpt!=NULL); 00475 *out_it++=typename SK::Circular_arc_3(arc.supporting_circle(),arc.source(),midpt->first); 00476 *out_it++=typename SK::Circular_arc_3(arc.supporting_circle(),midpt->first,arc.target()); 00477 break; 00478 } 00479 00480 //three arcs are defined by two intersection points 00481 const std::pair<typename SK::Circular_arc_point_3,unsigned>* pt[2]={NULL,NULL}; 00482 pt[0]=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[0]); 00483 pt[1]=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[1]); 00484 CGAL_kernel_precondition(pt[0]!=NULL); 00485 CGAL_kernel_precondition(pt[1]!=NULL); 00486 00487 typename SK::Circular_arc_3 arc1=typename SK::Circular_arc_3(arc.supporting_circle(),arc.source(),pt[0]->first); 00488 typename SK::Circular_arc_3 arc2=typename SK::Circular_arc_3(arc.supporting_circle(),pt[0]->first,arc.target()); 00489 if ( has_on<SK>(arc1,pt[1]->first) ){ 00490 *out_it++=typename SK::Circular_arc_3(arc1.supporting_circle(),arc1.source(),pt[1]->first); 00491 *out_it++=typename SK::Circular_arc_3(arc1.supporting_circle(),pt[1]->first,arc1.target()); 00492 *out_it++=arc2; 00493 } 00494 else{ 00495 *out_it++=arc1; 00496 *out_it++=typename SK::Circular_arc_3(arc2.supporting_circle(),arc2.source(),pt[1]->first); 00497 *out_it++=typename SK::Circular_arc_3(arc2.supporting_circle(),pt[1]->first,arc2.target()); 00498 } 00499 break; 00500 } 00501 case BIPOLAR: 00502 CGAL_kernel_precondition(!"This function does not accept bipolar circle as input."); 00503 } 00504 00505 return out_it; 00506 } 00507 00508 //this function indicates whether a theta monotone circular arc is 00509 //included in the upper part of its supporting circle (wrt theta extremal pts) 00510 template <class SK> 00511 bool 00512 is_upper_arc(const typename SK::Circular_arc_3& arc, 00513 const typename SK::Sphere_3& sphere) 00514 { 00515 CGAL_kernel_precondition(is_theta_monotone_3<SK>(arc,sphere)); 00516 CGAL::Circle_type type=classify_circle_3<SK>(arc.supporting_circle(),sphere); 00517 CGAL_kernel_precondition(type!=THREADED && type !=BIPOLAR); 00518 00519 //case of POLAR circle 00520 if (type==POLAR) 00521 return ( ( arc.supporting_circle().center().z()-sphere.center().z() ) < 0 ); 00522 00523 //case of NORMAL circle 00524 typename SK::FT z_coord=extremal_points_z_coordinate<SK>(arc.supporting_circle(),sphere); 00525 if ( z_coord < arc.source().z() ) return true; 00526 if ( z_coord > arc.source().z() ) return false; 00527 if ( z_coord < arc.target().z() ) return true; 00528 if ( z_coord > arc.target().z() ) return false; 00529 00530 //source and target are theta extremal points 00531 00532 typename SK::Point_3 out_sphere_normal=CGAL::ORIGIN + ( arc.supporting_circle().center()-sphere.center() ); 00533 typename SK::Point_3 ori(0,0,0); 00534 int wise=(out_sphere_normal > ori)? 1:-1; //check if seen ccw from the side going from the sphere center to the circle center 00535 00536 typename SK::Vector_3 cir_center(arc.supporting_circle().center().x()-sphere.center().x(),arc.supporting_circle().center().y()-sphere.center().y(),0); 00537 CGAL::Comparison_result source_vs_center=compare_theta_pt_vector<SK>(arc.source(),cir_center,sphere); 00538 CGAL::Comparison_result target_vs_center=compare_theta_pt_vector<SK>(arc.target(),cir_center,sphere); 00539 00540 00541 if (source_vs_center==target_vs_center){//circle is cut by meridian at theta=0 00542 CGAL::Comparison_result source_vs_target=compare_theta_of_pts<SK>(arc.source(),arc.target(),sphere); 00543 wise*=(source_vs_target==SMALLER)?-1:1; 00544 } 00545 else 00546 wise*=(source_vs_center==SMALLER)?1:-1; 00547 00548 return wise==1?false:true; 00549 } 00550 00551 //compute the intersection points of a theta monotone arc with a meridian. 00552 //precondition: the intersection point always exists. 00553 template <class SK> 00554 typename SK::Circular_arc_point_3 00555 intersect_3( const typename SK::Circular_arc_3& arc, 00556 const typename SK::Vector_3&m, 00557 const typename SK::Sphere_3& sphere) 00558 { 00559 typename SK::Plane_3 plane(sphere.center(),sphere.center()+m,sphere.center()+typename SK::Vector_3(0,0,1)); 00560 std::vector<CGAL::Object> inters; 00561 intersect_3<SK>(plane,arc,std::back_inserter(inters)); 00562 CGAL_kernel_precondition(!inters.empty()); 00563 if (inters.size()==1){ 00564 const typename SK::Circular_arc_point_3& pt= 00565 object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[0])->first; 00566 return pt; 00567 } 00568 00569 CGAL_kernel_precondition(classify_circle_3<SK>(arc.supporting_circle(),sphere)!=NORMAL); 00570 00571 const typename SK::Circular_arc_point_3& pts1=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[0])->first; 00572 const typename SK::Circular_arc_point_3& pts2=object_cast<std::pair<typename SK::Circular_arc_point_3,unsigned> >(&inters[1])->first; 00573 00574 00575 //either a polar (1 pole + 1 pt) or a threaded circle (2 pts with theta-coord = +/- pi) 00576 if ( (pts1.x()!=0 && pts1.y()!=0) && compare_theta_pt_vector<SK>(pts1,m,sphere)==CGAL::EQUAL) 00577 return pts1; 00578 else 00579 return pts2; 00580 } 00581 00582 00583 template <class SK> 00584 //Compare the z coordinates of the intersection points with the meridian defined by m of two theta monotone arcs. 00585 CGAL::Comparison_result 00586 compare_z_at_theta_arcs( const typename SK::Circular_arc_3& arc1, 00587 const typename SK::Circular_arc_3& arc2, 00588 const typename SK::Vector_3& m, 00589 const typename SK::Sphere_3& sphere) 00590 { 00591 CGAL_kernel_precondition(is_theta_monotone_3<SK>(arc1,sphere)); 00592 CGAL_kernel_precondition(is_theta_monotone_3<SK>(arc2,sphere)); 00593 00594 typename SK::Circular_arc_point_3 pt1=intersect_3<SK>(arc1,m,sphere); 00595 typename SK::Circular_arc_point_3 pt2=intersect_3<SK>(arc2,m,sphere); 00596 return CGAL::compare(pt1.z(),pt2.z()); 00597 } 00598 00599 template <class SK> 00600 CGAL::Comparison_result 00601 compare_z_at_theta_pt_arc(const typename SK::Circular_arc_point_3& pt, 00602 const typename SK::Circular_arc_3& arc, 00603 const typename SK::Sphere_3& sphere) 00604 { 00605 CGAL_kernel_precondition(is_theta_monotone_3<SK>(arc,sphere)); 00606 CGAL::Circle_type type=classify_circle_3<SK>(arc.supporting_circle(),sphere); 00607 CGAL_kernel_precondition(type!=BIPOLAR); 00608 00609 switch(type){ 00610 case THREADED: 00611 case POLAR: 00612 { 00613 const typename SK::Plane_3& plane=arc.supporting_circle().supporting_plane(); 00614 typename SK::Vector_3 ortho=plane.orthogonal_vector(); 00615 int res=typename SK::Algebraic_kernel().sign_at_object()( 00616 typename SK::Algebraic_kernel::Polynomial_1_3(ortho.x(),ortho.y(),ortho.z(),plane.d()), 00617 pt.coordinates() 00618 ); 00619 res*=(plane.orthogonal_vector().z()>0)?1:-1; 00620 return CGAL::Comparison_result(res); 00621 } 00622 default: 00623 { 00624 typename SK::Vector_3 ortho=arc.supporting_circle().center()-sphere.center(); 00625 typename SK::FT d=-ortho * typename SK::Vector_3(CGAL::ORIGIN,arc.supporting_circle().center()); 00626 int res=typename SK::Algebraic_kernel().sign_at_object()( 00627 typename SK::Algebraic_kernel::Polynomial_1_3(ortho.x(),ortho.y(),ortho.z(),d), 00628 pt.coordinates() 00629 ); 00630 if (res==0) return CGAL::EQUAL; 00631 if (res==-1) return CGAL::compare(pt.z(),extremal_points_z_coordinate<SK>(arc.supporting_circle(),sphere)); 00632 return is_upper_arc<SK>(arc,sphere)?CGAL::SMALLER:CGAL::LARGER; 00633 } 00634 } 00635 } 00636 00637 }//SphericalFunctors 00638 }//CGAL 00639 00640 #endif //CGAL_SPHERICAL_KERNEL_PREDICATES_ON_CIRCULAR_ARC_3_H
1.7.6.1
