|
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_line_arc_3.h $ 00015 // $Id: internal_functions_on_line_arc_3.h 44381 2008-07-24 09:26:28Z pmachado $ 00016 // 00017 // Author(s) : Monique Teillaud, Sylvain Pion, Pedro Machado 00018 00019 // Partially supported by the IST Programme of the EU as a 00020 // STREP (FET Open) Project under Contract No IST-006413 00021 // (ACS -- Algorithms for Complex Shapes) 00022 00023 #ifndef CGAL_SPHERICAL_KERNEL_PREDICATES_ON_LINE_ARC_3_H 00024 #define CGAL_SPHERICAL_KERNEL_PREDICATES_ON_LINE_ARC_3_H 00025 00026 namespace CGAL { 00027 namespace SphericalFunctors { 00028 00029 template< class SK> 00030 bool 00031 equal( const typename SK::Line_arc_3 &l1, 00032 const typename SK::Line_arc_3 &l2) 00033 { 00034 return l1.rep() == l2.rep(); 00035 } 00036 00037 template <class SK> 00038 inline 00039 bool 00040 do_overlap(const typename SK::Line_arc_3 &l1, 00041 const typename SK::Line_arc_3 &l2, 00042 const bool known_equal_supporting_line = false) 00043 { 00044 if(!known_equal_supporting_line) { 00045 if (!non_oriented_equal<SK>(l1.supporting_line(), 00046 l2.supporting_line())) 00047 return false; 00048 } 00049 00050 return SK().compare_xyz_3_object()(l1.higher_xyz_extremity(), 00051 l2.lower_xyz_extremity()) >= 0 00052 && SK().compare_xyz_3_object()(l1.lower_xyz_extremity(), 00053 l2.higher_xyz_extremity()) <= 0; 00054 } 00055 00056 template < class SK > 00057 void 00058 split(const typename SK::Line_arc_3 &l, 00059 const typename SK::Circular_arc_point_3 &p, 00060 typename SK::Line_arc_3 &l1, 00061 typename SK::Line_arc_3 &l2) 00062 { 00063 typedef typename SK::Line_arc_3 Line_arc_3; 00064 // The point must be on the line arc 00065 CGAL_kernel_precondition(SK().has_on_3_object()(l, p)); 00066 // It doesn't make sense to split an arc on an extremity 00067 CGAL_kernel_precondition(l.source() != p); 00068 CGAL_kernel_precondition(l.target() != p); 00069 if(SK().compare_xyz_3_object()(l.source(),p) == SMALLER) { 00070 l1 = Line_arc_3(l.supporting_line(),l.source(),p); 00071 l2 = Line_arc_3(l.supporting_line(),p,l.target()); 00072 } else { 00073 l1 = Line_arc_3(l.supporting_line(),p,l.target()); 00074 l2 = Line_arc_3(l.supporting_line(),l.source(),p); 00075 } 00076 } 00077 00078 template < class SK, class OutputIterator > 00079 OutputIterator 00080 intersect_3(const typename SK::Line_arc_3 & l1, 00081 const typename SK::Line_arc_3 & l2, 00082 OutputIterator res) 00083 { 00084 typedef typename SK::Point_3 Point_3; 00085 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00086 typedef typename SK::Line_3 Line_3; 00087 typedef typename SK::Line_arc_3 Line_arc_3; 00088 00089 Point_3 inters_p; 00090 Line_3 inters_l; 00091 00092 Object o = SK().intersect_3_object()(l1.supporting_line(), 00093 l2.supporting_line()); 00094 00095 if(assign(inters_p, o)) { 00096 Circular_arc_point_3 p = inters_p; 00097 if(!SK().has_on_3_object()(l1,p,true)) return res; 00098 if(!SK().has_on_3_object()(l2,p,true)) return res; 00099 *res++ = make_object(std::make_pair(p,1u)); 00100 } else if(assign(inters_l, o)) { 00101 00102 if(SK().compare_xyz_3_object()(l1.lower_xyz_extremity(), 00103 l2.lower_xyz_extremity()) < 0) { 00104 int comparison = 00105 SK().compare_xyz_3_object()(l2.lower_xyz_extremity(), 00106 l1.higher_xyz_extremity()); 00107 if(comparison < 0) { 00108 if(SK().compare_xyz_3_object()(l1.higher_xyz_extremity(), 00109 l2.higher_xyz_extremity()) <= 0) { 00110 *res++ = make_object 00111 (Line_arc_3(l1.supporting_line(), 00112 l2.lower_xyz_extremity(), 00113 l1.higher_xyz_extremity())); 00114 } else { 00115 *res++ = make_object(l2); 00116 } 00117 } else if (comparison == 0) { 00118 *res++ = make_object(std::make_pair(l2.lower_xyz_extremity(),1u)); 00119 } 00120 } 00121 else { 00122 int comparison = 00123 SK().compare_xyz_3_object()(l1.lower_xyz_extremity(), 00124 l2.higher_xyz_extremity()); 00125 if(comparison < 0){ 00126 if(SK().compare_xyz_3_object()(l1.higher_xyz_extremity(), 00127 l2.higher_xyz_extremity()) <= 0) { 00128 *res++ = make_object(l1); 00129 } else { 00130 *res++ = make_object 00131 (Line_arc_3(l1.supporting_line(), 00132 l1.lower_xyz_extremity(), 00133 l2.higher_xyz_extremity() )); 00134 } 00135 } 00136 else if (comparison == 0){ 00137 *res++ = make_object(std::make_pair(l1.lower_xyz_extremity(),1u)); 00138 } 00139 } 00140 } 00141 return res; 00142 } 00143 00144 template < class SK, class OutputIterator > 00145 OutputIterator 00146 intersect_3(const typename SK::Line_3 & l, 00147 const typename SK::Line_arc_3 & la, 00148 OutputIterator res) 00149 { 00150 typedef typename SK::Point_3 Point_3; 00151 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00152 typedef typename SK::Line_3 Line_3; 00153 typedef typename SK::Line_arc_3 Line_arc_3; 00154 00155 Point_3 inters_p; 00156 Line_3 inters_l; 00157 00158 Object o = SK().intersect_3_object()(l, la.supporting_line()); 00159 00160 if(assign(inters_l, o)) { 00161 *res++ = make_object(la); 00162 } else if(assign(inters_p, o)) { 00163 Circular_arc_point_3 p = inters_p; 00164 if(!SK().has_on_3_object()(la,p,true)) return res; 00165 *res++ = make_object(std::make_pair(p,1u)); 00166 } 00167 return res; 00168 } 00169 00170 template < class SK, class OutputIterator > 00171 OutputIterator 00172 intersect_3(const typename SK::Circle_3 & c, 00173 const typename SK::Line_arc_3 & l, 00174 OutputIterator res) 00175 { 00176 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00177 typedef std::vector<CGAL::Object> solutions_container; 00178 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00179 solutions_container solutions; 00180 SK().intersect_3_object()(l.supporting_line(), c, 00181 std::back_inserter(solutions) ); 00182 if(solutions.size() == 0) return res; 00183 if(solutions.size() == 1) { 00184 Solution sol; 00185 assign(sol, solutions[0]); 00186 if(SK().has_on_3_object()(l,sol.first,true)) 00187 *res++ = solutions[0]; 00188 } else { 00189 Solution sol1, sol2; 00190 assign(sol1, solutions[0]); 00191 assign(sol2, solutions[1]); 00192 if(SK().has_on_3_object()(l,sol1.first,true)) 00193 *res++ = solutions[0]; 00194 if(SK().has_on_3_object()(l,sol2.first,true)) 00195 *res++ = solutions[1]; 00196 } 00197 return res; 00198 } 00199 00200 template < class SK, class OutputIterator > 00201 OutputIterator 00202 intersect_3(const typename SK::Sphere_3 & s, 00203 const typename SK::Line_arc_3 & l, 00204 OutputIterator res) 00205 { 00206 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00207 typedef std::vector<CGAL::Object> solutions_container; 00208 typedef std::pair<Circular_arc_point_3, unsigned> Solution; 00209 solutions_container solutions; 00210 SK().intersect_3_object()(l.supporting_line(), s, 00211 std::back_inserter(solutions) ); 00212 if(solutions.size() == 0) return res; 00213 if(solutions.size() == 1) { 00214 Solution sol; 00215 assign(sol, solutions[0]); 00216 if(SK().has_on_3_object()(l,sol.first,true)) 00217 *res++ = solutions[0]; 00218 } else { 00219 Solution sol1, sol2; 00220 assign(sol1, solutions[0]); 00221 assign(sol2, solutions[1]); 00222 if(SK().has_on_3_object()(l,sol1.first,true)) 00223 *res++ = solutions[0]; 00224 if(SK().has_on_3_object()(l,sol2.first,true)) 00225 *res++ = solutions[1]; 00226 } 00227 return res; 00228 } 00229 00230 template < class SK, class OutputIterator > 00231 OutputIterator 00232 intersect_3(const typename SK::Plane_3 & p, 00233 const typename SK::Line_arc_3 & l, 00234 OutputIterator res) 00235 { 00236 typedef typename SK::Point_3 Point_3; 00237 typedef typename SK::Circular_arc_point_3 Circular_arc_point_3; 00238 if(SK().has_on_3_object()(p,l.supporting_line())) { 00239 *res++ = make_object(l); 00240 } 00241 Point_3 sol; 00242 if(!assign(sol,SK().intersect_3_object()(p,l.supporting_line()))) 00243 return res; 00244 if(!SK().has_on_3_object()(l,sol)) return res; 00245 Circular_arc_point_3 point = sol; 00246 *res++ = make_object(std::make_pair(point,1u)); 00247 return res; 00248 } 00249 00250 }//SphericalFunctors 00251 }//CGAL 00252 00253 #endif //CGAL_SPHERICAL_KERNEL_PREDICATES_ON_LINE_ARC_3_H
1.7.6.1
