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