1 // Copyright (c) 1997-2000 Max-Planck-Institute Saarbruecken (Germany). 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/Nef_2/include/CGAL/Bounded_kernel.h $ 7 // $Id: Bounded_kernel.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 // 11 // Author(s) : Michael Seel <seel@mpi-sb.mpg.de> 12 #ifndef CGAL_BOUNDED_KERNEL_H 13 #define CGAL_BOUNDED_KERNEL_H 14 15 #include <CGAL/license/Nef_2.h> 16 17 #include <CGAL/disable_warnings.h> 18 19 #include <CGAL/Simple_cartesian.h> 20 #include <CGAL/Point_2.h> 21 #include <CGAL/Intersections_2/Line_2_Line_2.h> 22 23 24 #undef CGAL_NEF_DEBUG 25 #define CGAL_NEF_DEBUG 51 26 #include <CGAL/Nef_2/debug.h> 27 #include <CGAL/Nef_2/Line_to_epoint.h> 28 29 namespace CGAL { 30 31 template <class T> class Bounded_kernel; 32 33 template<class Kernel> 34 struct Is_extended_kernel; 35 36 template<class T> 37 struct Is_extended_kernel<Bounded_kernel<T> > { 38 typedef Tag_false value_type; 39 }; 40 41 /*{\Xanpage {Bounded_kernel}{}{An extended geometric kernel model}{K}}*/ 42 43 template <class T> 44 class Bounded_kernel 45 : public T 46 { 47 48 public: 49 typedef T Base; 50 typedef Bounded_kernel<T> Self; 51 typedef T Standard_kernel; 52 53 54 typedef typename Standard_kernel::RT Standard_RT; 55 /*{\Xtypemember the standard ring type.}*/ 56 57 typedef typename Standard_kernel::FT Standard_FT; 58 /*{\Xtypemember the field type.}*/ 59 60 typedef typename Standard_kernel::Point_2 Standard_point_2; 61 /*{\Xtypemember standard points.}*/ 62 63 typedef typename Standard_kernel::Segment_2 Standard_segment_2; 64 /*{\Xtypemember standard segments.}*/ 65 66 typedef typename Standard_kernel::Line_2 Standard_line_2; 67 /*{\Xtypemember standard oriented lines.}*/ 68 69 typedef typename Standard_kernel::Direction_2 Standard_direction_2; 70 /*{\Xtypemember standard directions.}*/ 71 72 typedef typename Standard_kernel::Ray_2 Standard_ray_2; 73 /*{\Xtypemember standard rays.}*/ 74 75 typedef typename Standard_kernel::Aff_transformation_2 76 Standard_aff_transformation_2; 77 /*{\Xtypemember standard affine transformations.}*/ 78 79 /*{\Xtext \headerline{Extended kernel types}}*/ 80 81 typedef typename Base::RT RT; 82 /*{\Xtypemember the ring type of our extended kernel.}*/ 83 84 typedef typename Base::FT FT; 85 /*{\Xtypemember the ring type of our extended kernel.}*/ 86 87 typedef typename Base::Point_2 Point_2; 88 /*{\Xtypemember extended points.}*/ 89 90 typedef typename Base::Segment_2 Segment_2; 91 /*{\Xtypemember extended segments.}*/ 92 93 typedef typename Base::Line_2 Line_2; 94 /*{\Xtypemember extended lines.}*/ 95 96 typedef typename Base::Direction_2 Direction_2; 97 /*{\Xtypemember extended directions.}*/ 98 99 enum Point_type { SWCORNER=1, LEFTFRAME, NWCORNER, 100 BOTTOMFRAME, STANDARD, TOPFRAME, 101 SECORNER, RIGHTFRAME, NECORNER }; 102 /*{\Xenum a type descriptor for extended points.}*/ 103 104 Point_2 epoint(const Standard_FT& /*m1*/, const Standard_FT& /*n1*/, 105 const Standard_FT& /*m2*/, const Standard_FT& /*n2*/) const 106 { 107 CGAL_error_msg( "Bounded_kernel::epoint(..) should not be called"); 108 return Point_2(); 109 } 110 111 public: 112 113 Point_2 114 construct_point(const Standard_point_2& p) const 115 { 116 return p; 117 } 118 119 Point_2 120 construct_point(const Standard_line_2& , Point_type& ) const 121 { 122 CGAL_error_msg( "Bounded_kernel::construct_point(Line,Point_type) should not be called"); 123 return Point_2(); 124 } 125 126 Point_2 127 construct_point(const Standard_point_2& , 128 const Standard_point_2& , 129 Point_type& /*t*/) const 130 { 131 CGAL_error_msg( "Bounded_kernel::construct_point(Point,Point) should not be called"); 132 return Point_2(); 133 } 134 135 Point_2 136 construct_point(const Standard_line_2& ) const 137 { 138 CGAL_error_msg( "Bounded_kernel::construct_point(Line) should not be called"); 139 return Point_2(); 140 } 141 142 Point_2 143 construct_point(const Standard_point_2& , 144 const Standard_point_2& ) const 145 { 146 CGAL_error_msg( "Bounded_kernel::construct_point(Point,Point) should not be called"); 147 return Point_2(); 148 } 149 150 Point_2 construct_point(const Standard_point_2& , 151 const Standard_direction_2& ) const 152 { 153 CGAL_error_msg( "Bounded_kernel::construct_point(Point,Direction) should not be called"); 154 return Point_2(); 155 } 156 157 Point_2 158 construct_opposite_point(const Standard_line_2& /*l*/) const 159 { 160 CGAL_error_msg( "Bounded_kernel::construct_opposite_point(..) should not be called"); 161 return Point_2(); 162 } 163 164 Point_type 165 type(const Point_2& /*p*/) const 166 { 167 return STANDARD; 168 } 169 170 171 bool 172 is_standard(const Point_2& /*p*/) const 173 { 174 return true; 175 } 176 177 Standard_point_2 178 standard_point(const Point_2& p) const 179 { 180 return p; 181 } 182 183 Standard_line_2 184 standard_line(const Point_2& /*p*/) const 185 { 186 CGAL_error_msg( "Bounded_kernel::standard_line(..) should not be called"); 187 return Standard_line_2(); 188 } 189 190 Standard_ray_2 191 standard_ray(const Point_2& /*p*/) const 192 { 193 CGAL_error_msg( "Bounded_kernel::standard_ray(..) should not be called"); 194 return Standard_ray_2(); 195 } 196 197 Point_2 198 NE() const 199 { 200 CGAL_error_msg( "Bounded_kernel::NE(..) should not be called"); 201 return Point_2(); 202 } 203 204 205 Point_2 206 SE() const 207 { 208 CGAL_error_msg( "Bounded_kernel::SE(..) should not be called"); 209 return Point_2(); 210 } 211 212 213 Point_2 214 NW() const 215 { 216 CGAL_error_msg( "Bounded_kernel::NW(..) should not be called"); 217 return Point_2(); 218 } 219 220 221 Point_2 222 SW() const 223 { 224 CGAL_error_msg( "Bounded_kernel::SW(..) should not be called"); 225 return Point_2(); 226 } 227 228 229 Line_2 230 upper() const 231 { 232 CGAL_error_msg( "Bounded_kernel::upper(..) should not be called"); 233 return Line_2(); 234 } 235 236 237 Line_2 238 lower() const 239 { 240 CGAL_error_msg( "Bounded_kernel::lower(..) should not be called"); 241 return Line_2(); 242 } 243 244 245 Line_2 246 left() const 247 { 248 CGAL_error_msg( "Bounded_kernel::left(..) should not be called"); 249 return Line_2(); 250 } 251 252 253 254 Line_2 255 right() const 256 { 257 CGAL_error_msg( "Bounded_kernel::right(..) should not be called"); 258 return Line_2(); 259 } 260 261 262 263 Point_2 264 source(const Segment_2& s) const 265 { 266 typename Base::Construct_vertex_2 _source = 267 this->construct_vertex_2_object(); 268 return _source(s,0); } 269 270 Point_2 271 target(const Segment_2& s) const 272 { 273 typename Base::Construct_vertex_2 _target = 274 this->construct_vertex_2_object(); 275 return _target(s,1); } 276 277 Segment_2 278 construct_segment(const Point_2& p, const Point_2& q) const 279 { 280 typename Base::Construct_segment_2 _segment = 281 this->construct_segment_2_object(); 282 return _segment(p,q); 283 } 284 285 Line_2 286 construct_line(const Standard_line_2& l) const 287 { 288 return Line_2(l.a(),l.b(),l.c()); 289 } 290 291 Line_2 292 construct_line(const Point_2& p1, const Point_2& p2) const 293 { 294 return Line_2(p1,p2); 295 } 296 297 298 int 299 orientation(const Segment_2& s, const Point_2& p) const 300 { 301 typename Base::Orientation_2 _orientation = 302 this->orientation_2_object(); 303 return static_cast<int> ( _orientation(source(s),target(s),p) ); 304 } 305 306 int 307 orientation(const Point_2& p1, const Point_2& p2, const Point_2& p3) const 308 { 309 typename Base::Orientation_2 _orientation = 310 this->orientation_2_object(); 311 return static_cast<int> ( _orientation(p1,p2,p3) ); 312 } 313 314 bool 315 left_turn(const Point_2& p1, const Point_2& p2, const Point_2& p3) const 316 { 317 return orientation(p1,p2,p3) > 0; 318 } 319 320 bool 321 is_degenerate(const Segment_2& s) const 322 { 323 typename Base::Is_degenerate_2 _is_degenerate = 324 this->is_degenerate_2_object(); 325 return _is_degenerate(s); 326 } 327 328 int 329 compare_xy(const Point_2& p1, const Point_2& p2) const 330 { 331 typename Base::Compare_xy_2 _compare_xy = 332 this->compare_xy_2_object(); 333 return static_cast<int>( _compare_xy(p1,p2) ); 334 } 335 336 int 337 compare_x(const Point_2& p1, const Point_2& p2) const 338 { 339 typename Base::Compare_x_2 _compare_x = 340 this->compare_x_2_object(); 341 return static_cast<int>( _compare_x(p1,p2) ); 342 } 343 344 int 345 compare_y(const Point_2& p1, const Point_2& p2) const 346 { 347 typename Base::Compare_y_2 _compare_y = 348 this->compare_y_2_object(); 349 return static_cast<int>( _compare_y(p1,p2) ); 350 } 351 352 353 Point_2 354 intersection(const Segment_2& s1, const Segment_2& s2) const 355 { 356 typename Base::Intersect_2 _intersect = 357 this->intersect_2_object(); 358 typename Base::Construct_line_2 _line = 359 this->construct_line_2_object(); 360 Point_2 p; 361 Line_2 l1 = _line(s1); 362 Line_2 l2 = _line(s2); 363 364 CGAL::Object result = 365 _intersect(l1, l2); 366 if ( !CGAL::assign(p, result) ) 367 CGAL_error_msg("intersection: no intersection."); 368 return p; 369 } 370 371 Direction_2 372 construct_direction(const Point_2& p1, const Point_2& p2) const 373 { 374 typename Base::Construct_direction_2 _direction = 375 this->construct_direction_2_object(); 376 return _direction(construct_line(p1,p2)); 377 } 378 379 bool 380 strictly_ordered_ccw(const Direction_2& d1, 381 const Direction_2& d2, const Direction_2& d3) const 382 { 383 if ( d1 < d2 ) return ( d2 < d3 )||( d3 <= d1 ); 384 if ( d1 > d2 ) return ( d2 < d3 )&&( d3 <= d1 ); 385 return false; 386 } 387 388 bool 389 contains(const Segment_2& s, const Point_2& p) const 390 { 391 typename Base::Has_on_2 _contains = this->has_on_2_object(); 392 return _contains(s,p); 393 } 394 395 bool 396 strictly_ordered_along_line(const Point_2& p1, const Point_2& p2, const Point_2& p3) const 397 { 398 typename Base::Are_strictly_ordered_along_line_2 _ordered = 399 this->are_strictly_ordered_along_line_2_object(); 400 return _ordered(p1,p2,p3); 401 } 402 403 bool 404 first_pair_closer_than_second(const Point_2& p1, const Point_2& p2, 405 const Point_2& p3, const Point_2& p4) const 406 { 407 return ( squared_distance(p1,p2) < squared_distance(p3,p4) ); 408 } 409 410 template <class Forward_iterator> 411 void 412 determine_frame_radius(Forward_iterator start, Forward_iterator end, 413 Standard_RT& R0) const 414 { 415 Standard_RT R; 416 while ( start != end ) { 417 Point_2 p = *start++; 418 if ( is_standard(p) ) { 419 R = (CGAL::max)(CGAL_NTS abs(p.x()[0]), CGAL_NTS abs(p.y()[0])); 420 } else { 421 RT rx = CGAL_NTS abs(p.x()), ry = CGAL_NTS abs(p.y()); 422 if ( rx[1] > ry[1] ) R = CGAL_NTS abs(ry[0]-rx[0])/(rx[1]-ry[1]); 423 else if ( rx[1] < ry[1] ) R = CGAL_NTS abs(rx[0]-ry[0])/(ry[1]-rx[1]); 424 else /* rx[1] == ry[1] */ R = CGAL_NTS abs(rx[0]-ry[0])/2; 425 } 426 R0 = (CGAL::max)(R+1,R0); 427 } 428 } 429 430 431 432 const char* 433 output_identifier() const 434 { 435 return "Bounded_kernel"; 436 } 437 438 }; 439 440 } //namespace CGAL 441 442 #include <CGAL/enable_warnings.h> 443 444 #endif // CGAL_BOUNDED_KERNEL_H 445