1 // Copyright (c) 2003-2008 INRIA Sophia-Antipolis (France). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Circular_kernel_2/include/CGAL/Circular_kernel_2/Line_arc_2.h $ 7 // $Id: Line_arc_2.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s) : Monique Teillaud, Sylvain Pion, Pedro Machado 11 12 // Partially supported by the IST Programme of the EU as a Shared-cost 13 // RTD (FET Open) Project under Contract No IST-2000-26473 14 // (ECG - Effective Computational Geometry for Curves and Surfaces) 15 // and a STREP (FET Open) Project under Contract No IST-006413 16 // (ACS -- Algorithms for Complex Shapes) 17 18 #ifndef CGAL_CIRCULAR_KERNEL_LINE_ARC_2_H 19 #define CGAL_CIRCULAR_KERNEL_LINE_ARC_2_H 20 21 #include <CGAL/license/Circular_kernel_2.h> 22 23 24 #include <CGAL/global_functions_circular_kernel_2.h> 25 #include <CGAL/Algebraic_kernel_for_circles/internal_functions_on_roots_and_polynomial_1_2_and_2_2.h> 26 #include <CGAL/Circular_kernel_2/internal_functions_on_line_2.h> 27 #include <CGAL/Circular_kernel_2/internal_functions_on_line_arc_2.h> 28 #include <CGAL/Bbox_2.h> 29 #include <CGAL/Circular_kernel_2/Circular_arc_2.h> 30 #include <CGAL/Circular_kernel_2/Intersection_traits.h> 31 32 33 namespace CGAL { 34 namespace internal { 35 36 template <class CK > 37 class Line_arc_2_base 38 { 39 public: 40 typedef typename CK::FT FT; 41 typedef typename CK::RT RT; 42 typedef typename CK::Point_2 Point_2; 43 typedef typename CK::Line_2 Line_2; 44 typedef typename CK::Circle_2 Circle_2; 45 typedef typename CK::Circular_arc_2 Circular_arc_2; 46 typedef typename CK::Circular_arc_point_2 Circular_arc_point_2; 47 typedef typename CK::Root_of_2 Root_of_2; 48 typedef typename CK::Segment_2 Segment_2; 49 50 private: 51 typedef struct bit_field { 52 unsigned char begin_less_xy_than_end:2; 53 } bit_field; 54 55 // set flags to 0 56 // when 1 bit -> 0 = false, 1 = true 57 // when 2 bits -> 0 = don_know, 1 = false 58 // 2 = true reset_flags()59 void reset_flags() const { 60 flags.begin_less_xy_than_end = 0; 61 } 62 63 public: 64 //typedef typename CGAL::Simple_cartesian<Root_of_2>::Point_2 65 // Numeric_point_2; 66 typedef typename CK::Root_for_circles_2_2 67 Root_for_circles_2_2; 68 69 static 70 Circular_arc_point_2 intersect(const Line_2 & l,const Circle_2 & c,const bool b)71 intersect(const Line_2 & l, const Circle_2 & c, const bool b) 72 { 73 74 typedef std::vector<typename CK2_Intersection_traits<CK, Line_2, Circle_2>::type> 75 solutions_container; 76 77 solutions_container solutions; 78 CGAL::CircularFunctors::intersect_2<CK> 79 ( l, c, std::back_inserter(solutions) ); 80 typename solutions_container::iterator it = solutions.begin(); 81 82 CGAL_kernel_precondition( it != solutions.end() ); 83 // the circles intersect 84 85 const std::pair<typename CK::Circular_arc_point_2, unsigned>* 86 result = CGAL::Intersections::internal::intersect_get<std::pair<typename CK::Circular_arc_point_2, unsigned> >(*it); 87 // get must have succeeded 88 if ( result->second == 2 ) // double solution 89 return result->first; 90 if (b) return result->first; 91 ++it; 92 result = CGAL::Intersections::internal::intersect_get<std::pair<typename CK::Circular_arc_point_2, unsigned> >(*it); 93 return result->first; 94 } 95 96 97 public: Line_arc_2_base()98 Line_arc_2_base() 99 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 100 : id_of_my_supporting_line(Circular_arc_2::circle_table.get_new_id()) 101 #endif 102 {} 103 Line_arc_2_base(const Line_2 & support,const Circle_2 & c1,const bool b1,const Circle_2 & c2,const bool b2)104 Line_arc_2_base(const Line_2 &support, 105 const Circle_2 &c1,const bool b1, 106 const Circle_2 &c2,const bool b2) 107 :_support(support) 108 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 109 ,id_of_my_supporting_line(Circular_arc_2::circle_table.get_new_id()) 110 #endif 111 { 112 _begin = intersect(support, c1, b1); 113 _end = intersect(support, c2, b2); 114 reset_flags(); 115 } 116 117 Line_arc_2_base(const Line_2 & support,const Line_2 & l1,const Line_2 & l2)118 Line_arc_2_base(const Line_2 &support, 119 const Line_2 &l1, 120 const Line_2 &l2) 121 :_support(support) 122 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 123 ,id_of_my_supporting_line(Circular_arc_2::circle_table.get_new_id()) 124 #endif 125 { 126 CGAL_kernel_precondition(do_intersect(support, l1)); 127 CGAL_kernel_precondition(do_intersect(support, l2)); 128 //typedef typename Root_of_2::RT RT_2; 129 typename Intersection_traits<CK, Line_2, Line_2>::result_type 130 v = CGAL::Intersections::internal::intersection(support, l1, CK()); 131 CGAL_assertion(bool(v)); 132 133 const Point_2 *pt = CGAL::Intersections::internal::intersect_get<Point_2>(v); 134 CGAL_assertion(pt != nullptr); 135 _begin = Circular_arc_point_2(*pt); 136 v = CGAL::Intersections::internal::intersection(support, l2, CK()); 137 const Point_2 *pt2 = CGAL::Intersections::internal::intersect_get<Point_2>(v); 138 CGAL_assertion(pt2 != nullptr); 139 _end = Circular_arc_point_2(*pt2); 140 reset_flags(); 141 } 142 Line_arc_2_base(const Line_2 & support,const Circular_arc_point_2 & p1,const Circular_arc_point_2 & p2)143 Line_arc_2_base(const Line_2 &support, 144 const Circular_arc_point_2 &p1, 145 const Circular_arc_point_2 &p2) 146 :_support(support) 147 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 148 ,id_of_my_supporting_line(Circular_arc_2::circle_table.get_new_id()) 149 #endif 150 { 151 //Verifier si p1 et p2 sont sur la line 152 _begin = p1; 153 _end = p2; 154 reset_flags(); 155 } 156 Line_arc_2_base(const Segment_2 & s)157 Line_arc_2_base(const Segment_2 &s) 158 :_support(s.supporting_line()) 159 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 160 ,id_of_my_supporting_line(Circular_arc_2::circle_table.get_new_id()) 161 #endif 162 { 163 _begin = Circular_arc_point_2(s.source()); 164 _end = Circular_arc_point_2(s.target()); 165 reset_flags(); 166 } 167 168 Line_arc_2_base(const Point_2 & p1,const Point_2 & p2)169 Line_arc_2_base(const Point_2 &p1, 170 const Point_2 &p2) 171 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 172 : id_of_my_supporting_line(Circular_arc_2::circle_table.get_new_id()) 173 #endif 174 { 175 _support = Line_2(p1, p2); 176 _begin = Circular_arc_point_2(p1); 177 _end = Circular_arc_point_2(p2); 178 reset_flags(); 179 } 180 181 private: 182 183 Line_2 _support; 184 Circular_arc_point_2 _begin, _end; 185 mutable bit_field flags; 186 187 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 188 mutable unsigned int id_of_my_supporting_line; 189 line_number()190 unsigned int line_number() const { 191 return id_of_my_supporting_line; 192 } 193 set_line_number(unsigned int i)194 void set_line_number(unsigned int i) const { 195 id_of_my_supporting_line = i; 196 } 197 #endif 198 199 private: //(some useful functions) 200 begin_less_xy_than_end()201 bool begin_less_xy_than_end() const { 202 if(flags.begin_less_xy_than_end == 0) { 203 if(compare_xy(_begin, _end) < 0) 204 flags.begin_less_xy_than_end = 2; 205 else flags.begin_less_xy_than_end = 1; 206 } return flags.begin_less_xy_than_end == 2; 207 } 208 209 public : 210 211 #ifdef CGAL_INTERSECTION_MAP_FOR_SUPPORTING_CIRCLES 212 template < class T > find_intersection_circle_line(const Circular_arc_2 & c,const Line_arc_2_base & l,T & res)213 static bool find_intersection_circle_line( 214 const Circular_arc_2& c, 215 const Line_arc_2_base& l, 216 T& res) { 217 if(c.id_of_my_supporting_circle == 0) return false; 218 return Circular_arc_2::circle_table.template find<T>(c.id_of_my_supporting_circle, 219 l.id_of_my_supporting_line, 220 res); 221 } 222 223 template < class T > put_intersection_circle_line(const Circular_arc_2 & c,const Line_arc_2_base & l,const T & res)224 static void put_intersection_circle_line(const Circular_arc_2& c, 225 const Line_arc_2_base& l, 226 const T& res) { 227 Circular_arc_2::circle_table.template put<T>(c.circle_number(), 228 l.line_number(), 229 res); 230 } 231 #endif 232 supporting_line()233 const Line_2 & supporting_line() const 234 { 235 return _support; 236 } 237 left()238 const Circular_arc_point_2 & left() const 239 { 240 return begin_less_xy_than_end() ? _begin : _end; 241 } 242 right()243 const Circular_arc_point_2 & right() const 244 { 245 return begin_less_xy_than_end() ? _end : _begin; 246 } 247 source()248 const Circular_arc_point_2 & source() const 249 { 250 return _begin; 251 } 252 target()253 const Circular_arc_point_2 & target() const 254 { 255 return _end; 256 } 257 is_vertical()258 bool is_vertical() const 259 { 260 return supporting_line().is_vertical(); 261 } 262 bbox()263 CGAL::Bbox_2 bbox() const 264 { 265 return _begin.bbox() + _end.bbox(); 266 } 267 268 }; // end class Line_arc_2_base 269 270 template <class CB, typename Base_CK> 271 class Filtered_bbox_line_arc_2_base : public Base_CK::Line_arc_2 { 272 typedef Filtered_bbox_line_arc_2_base<CB,Base_CK> Self; 273 typedef typename Base_CK::Line_arc_2 P_arc; 274 275 public: 276 277 typedef typename CB::Point_2 Point_2; 278 typedef typename CB::Line_2 Line_2; 279 typedef typename CB::Segment_2 Segment_2; 280 typedef typename CB::Circle_2 Circle_2; 281 typedef typename CB::Circular_arc_point_2 Circular_arc_point_2; 282 Filtered_bbox_line_arc_2_base()283 Filtered_bbox_line_arc_2_base() : P_arc(), bb(nullptr) {} 284 Filtered_bbox_line_arc_2_base(const P_arc & arc)285 Filtered_bbox_line_arc_2_base(const P_arc& arc) : P_arc(arc), bb(nullptr) {} 286 Filtered_bbox_line_arc_2_base(const Line_2 & support,const Circle_2 & l1,const bool b_l1,const Circle_2 & l2,const bool b_l2)287 Filtered_bbox_line_arc_2_base(const Line_2 &support, 288 const Circle_2 &l1, const bool b_l1, 289 const Circle_2 &l2, const bool b_l2) 290 : P_arc(support,l1,b_l1,l2,b_l2), bb(nullptr) 291 {} 292 293 Filtered_bbox_line_arc_2_base(const Line_2 & support,const Line_2 & l1,const Line_2 & l2)294 Filtered_bbox_line_arc_2_base(const Line_2 &support, 295 const Line_2 &l1, 296 const Line_2 &l2) 297 : P_arc(support,l1,l2), bb(nullptr) 298 {} 299 Filtered_bbox_line_arc_2_base(const Line_2 & support,const Circular_arc_point_2 & begin,const Circular_arc_point_2 & end)300 Filtered_bbox_line_arc_2_base(const Line_2 &support, 301 const Circular_arc_point_2 &begin, 302 const Circular_arc_point_2 &end) 303 : P_arc(support, begin, end) , bb(nullptr) 304 {} 305 306 Filtered_bbox_line_arc_2_base(const Segment_2 & s)307 Filtered_bbox_line_arc_2_base(const Segment_2 &s) 308 : P_arc(s) , bb(nullptr) 309 {} 310 311 Filtered_bbox_line_arc_2_base(const Point_2 & p1,const Point_2 & p2)312 Filtered_bbox_line_arc_2_base(const Point_2 &p1, 313 const Point_2 &p2) 314 : P_arc(p1,p2) , bb(nullptr) 315 {} 316 317 Filtered_bbox_line_arc_2_base(const Filtered_bbox_line_arc_2_base & c)318 Filtered_bbox_line_arc_2_base(const Filtered_bbox_line_arc_2_base &c) 319 : P_arc(c), bb(c.bb ? new Bbox_2(*(c.bb)) : nullptr) 320 {} 321 322 Filtered_bbox_line_arc_2_base& operator=(const Self& c) 323 { 324 if(this != &c) 325 { 326 this->P_arc::operator=(c); 327 328 if (bb != nullptr){ 329 delete bb; 330 } 331 bb = c.bb ? new Bbox_2(*(c.bb)) : nullptr; 332 } 333 return *this; 334 } 335 ~Filtered_bbox_line_arc_2_base()336 ~Filtered_bbox_line_arc_2_base() { if(bb) delete bb; } 337 bbox()338 Bbox_2 bbox() const 339 { 340 if(bb==nullptr) 341 bb=new Bbox_2(P_arc::bbox()); 342 return *bb; 343 } 344 has_no_bbox()345 bool has_no_bbox() const 346 { return (bb==nullptr);} 347 348 private: 349 350 mutable Bbox_2 *bb; 351 352 }; // end class Filtered_bbox_line_arc_2_base 353 354 /* template < typename CK > */ 355 /* std::ostream & */ 356 /* operator<<(std::ostream & os, const Line_arc_2_base<CK> &a) */ 357 /* { */ 358 359 /* return os << a.supporting_line() << " " */ 360 /* << a.source() << " " */ 361 /* << a.target() << " "; */ 362 /* } */ 363 364 /* template < typename CK > */ 365 /* std::istream & */ 366 /* operator>>(std::istream & is, Line_arc_2_base<CK> &a) */ 367 /* { */ 368 /* typename CK::Line_2 l; */ 369 /* typename CK::Circular_arc_point_2 p1; */ 370 /* typename CK::Circular_arc_point_2 p2; */ 371 /* is >> l >> p1 >> p2 ; */ 372 /* if (is) */ 373 /* a = Line_arc_2_base<CK>(l, p1, p2); */ 374 /* return is; */ 375 /* } */ 376 377 378 } // namespace internal 379 } // namespace CGAL 380 381 #endif // CGAL_CIRCULAR_KERNEL_LINE_ARC_2_H 382