1 // Copyright (c) 1997-2001
2 // ETH Zurich (Switzerland). 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/Bounding_volumes/include/CGAL/Min_ellipse_2/Min_ellipse_2_adapterC2.h $
7 // $Id: Min_ellipse_2_adapterC2.h 4e519a3 2021-05-05T13:15:37+02:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Sven Schoenherr <sven@inf.ethz.ch>, Bernd Gaertner
12
13 #ifndef CGAL_MIN_ELLIPSE_2_ADAPTERC2_H
14 #define CGAL_MIN_ELLIPSE_2_ADAPTERC2_H
15
16 #include <CGAL/license/Bounding_volumes.h>
17
18
19 // includes
20 # include <CGAL/Cartesian/ConicCPA2.h>
21 # include <CGAL/Optimisation/assertions.h>
22
23 namespace CGAL {
24
25 // Class declarations
26 // ==================
27 template < class Traits_ >
28 class Min_ellipse_2;
29
30 template < class PT_, class DA_ >
31 class Min_ellipse_2_adapterC2;
32
33 template < class PT_, class DA_ >
34 class _Min_ellipse_2_adapterC2__Ellipse;
35
36 // Class interface and implementation
37 // ==================================
38 template < class PT, class DA >
39 bool
are_ordered_along_lineC2(const PT & p,const PT & q,const PT & r,const DA & da)40 are_ordered_along_lineC2( const PT& p, const PT& q, const PT& r,
41 const DA& da)
42 {
43 typedef typename DA::FT FT;
44
45 FT px;
46 FT py;
47 FT qx;
48 FT qy;
49 FT rx;
50 FT ry;
51
52 da.get( p, px, py);
53 da.get( q, qx, qy);
54 da.get( r, rx, ry);
55
56 // p,q,r collinear?
57 if ( ! CGAL_NTS is_zero( ( px-rx) * ( qy-ry) - ( py-ry) * ( qx-rx)))
58 return( false);
59
60 // p,q,r vertical?
61 if ( px != rx)
62 return( ( ( px < qx) && ( qx < rx))
63 || ( ( rx < qx) && ( qx < px)));
64 else
65 return( ( ( py < qy) && ( qy < ry))
66 || ( ( ry < qy) && ( qy < py)));
67 }
68
69 template < class PT_, class DA_ >
70 class Min_ellipse_2_adapterC2 {
71 public:
72 // types
73 typedef PT_ PT;
74 typedef DA_ DA;
75
76 // nested types
77 typedef PT Point;
78 typedef _Min_ellipse_2_adapterC2__Ellipse<PT,DA> Ellipse;
79
80 private:
81 DA dao; // data accessor object
82 Ellipse ellipse; // current ellipse
83 friend class Min_ellipse_2< Min_ellipse_2_adapterC2<PT,DA> >;
84
85 public:
86 // creation
87 Min_ellipse_2_adapterC2( const DA& da = DA())
dao(da)88 : dao( da), ellipse( da)
89 { }
90
91 // operations
92 CGAL::Orientation
orientation(const Point & p,const Point & q,const Point & r)93 orientation( const Point& p, const Point& q, const Point& r) const
94 {
95 typedef typename DA_::FT FT;
96
97 FT px;
98 FT py;
99 FT qx;
100 FT qy;
101 FT rx;
102 FT ry;
103
104 dao.get( p, px, py);
105 dao.get( q, qx, qy);
106 dao.get( r, rx, ry);
107
108 return( static_cast< CGAL::Orientation>(
109 CGAL_NTS sign( ( px-rx) * ( qy-ry) - ( py-ry) * ( qx-rx))));
110 }
111 };
112
113 // Nested type `Ellipse'
114 template < class PT_, class DA_ >
115 std::ostream& operator << ( std::ostream& os,
116 const _Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& c);
117
118 template < class PT_, class DA_ >
119 std::istream& operator >> ( std::istream& is,
120 _Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& c);
121
122 template < class PT_, class DA_ >
123 class _Min_ellipse_2_adapterC2__Ellipse {
124 public:
125 // typedefs
126 typedef PT_ PT;
127 typedef DA_ DA;
128
129 typedef ConicCPA2< PT, DA> CT;
130 typedef typename DA_::FT FT;
131
132 private:
133 // data members
134 int n_boundary_points; // number of boundary points
135 PT boundary_point1, boundary_point2; // two boundary points
136 CT conic1, conic2; // two conics
137 FT dr, ds, dt, du, dv, dw; // the gradient vector
138
139 friend
140 std::ostream& operator << <> ( std::ostream& os,
141 const _Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& c);
142
143 friend
144 std::istream& operator >> <> ( std::istream& is,
145 _Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& c);
146
147 public:
148 // types
149 typedef PT Point;
150
151 // creation
_Min_ellipse_2_adapterC2__Ellipse(const DA & da)152 _Min_ellipse_2_adapterC2__Ellipse( const DA& da)
153 : conic1( da), conic2( da)
154 { }
155
156 void
set()157 set( )
158 {
159 n_boundary_points = 0;
160 }
161
162 void
set(const Point & p)163 set( const Point& p)
164 {
165 n_boundary_points = 1;
166 boundary_point1 = p;
167 }
168
169 void
set(const Point & p,const Point & q)170 set( const Point& p, const Point& q)
171 {
172 n_boundary_points = 2;
173 boundary_point1 = p;
174 boundary_point2 = q;
175 }
176
177 void
set(const Point & p1,const Point & p2,const Point & p3)178 set( const Point& p1, const Point& p2, const Point& p3)
179 {
180 n_boundary_points = 3;
181 conic1.set_ellipse( p1, p2, p3);
182 }
183
184 void
set(const Point & p1,const Point & p2,const Point & p3,const Point & p4)185 set( const Point& p1, const Point& p2,
186 const Point& p3, const Point& p4)
187 {
188 n_boundary_points = 4;
189 CT::set_two_linepairs( p1, p2, p3, p4, conic1, conic2);
190 dr = FT( 0);
191 ds = conic1.r() * conic2.s() - conic2.r() * conic1.s(),
192 dt = conic1.r() * conic2.t() - conic2.r() * conic1.t(),
193 du = conic1.r() * conic2.u() - conic2.r() * conic1.u(),
194 dv = conic1.r() * conic2.v() - conic2.r() * conic1.v(),
195 dw = conic1.r() * conic2.w() - conic2.r() * conic1.w();
196 }
197
198 void
set(const Point &,const Point &,const Point &,const Point &,const Point & p5)199 set( const Point&, const Point&,
200 const Point&, const Point&, const Point& p5)
201 {
202 n_boundary_points = 5;
203 conic1.set( conic1, conic2, p5);
204 conic1.analyse();
205 }
206
207 // predicates
208 CGAL::Bounded_side
bounded_side(const Point & p)209 bounded_side( const Point& p) const
210 {
211 switch ( n_boundary_points) {
212 case 0:
213 return( CGAL::ON_UNBOUNDED_SIDE);
214 case 1:
215 return( ( p == boundary_point1) ?
216 CGAL::ON_BOUNDARY : CGAL::ON_UNBOUNDED_SIDE);
217 case 2:
218 return( ( p == boundary_point1)
219 || ( p == boundary_point2)
220 || ( CGAL::are_ordered_along_lineC2( boundary_point1, p,
221 boundary_point2, conic1.da())) ?
222 CGAL::ON_BOUNDARY : CGAL::ON_UNBOUNDED_SIDE);
223 case 3:
224 case 5:
225 return( conic1.convex_side( p));
226 case 4: {
227 CT c( conic1.da());
228 c.set( conic1, conic2, p);
229 c.analyse();
230 if ( ! c.is_ellipse()) {
231 c.set_ellipse( conic1, conic2);
232 c.analyse();
233 return( c.convex_side( p)); }
234 else {
235 int tau_star = c.vol_derivative( dr, ds, dt, du, dv, dw);
236 return( CGAL::Bounded_side( CGAL_NTS sign( tau_star))); } }
237 default:
238 CGAL_optimisation_assertion( ( n_boundary_points >= 0) &&
239 ( n_boundary_points <= 5) ); }
240 // keeps g++ happy
241 return( CGAL::Bounded_side( 0));
242 }
243
244 bool
has_on_bounded_side(const Point & p)245 has_on_bounded_side( const Point& p) const
246 {
247 return( bounded_side( p) == CGAL::ON_BOUNDED_SIDE);
248 }
249
250 bool
has_on_boundary(const Point & p)251 has_on_boundary( const Point& p) const
252 {
253 return( bounded_side( p) == CGAL::ON_BOUNDARY);
254 }
255
256 bool
has_on_unbounded_side(const Point & p)257 has_on_unbounded_side( const Point& p) const
258 {
259 return( bounded_side( p) == CGAL::ON_UNBOUNDED_SIDE);
260 }
261
262 bool
is_empty()263 is_empty( ) const
264 {
265 return( n_boundary_points == 0);
266 }
267
268 bool
is_degenerate()269 is_degenerate( ) const
270 {
271 return( n_boundary_points < 3);
272 }
273
274 // additional operations for checking
275 bool
276 operator == (
277 const CGAL::_Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& e) const
278 {
279 if ( n_boundary_points != e.n_boundary_points)
280 return( false);
281
282 switch ( n_boundary_points) {
283 case 0:
284 return( true);
285 case 1:
286 return( boundary_point1 == e.boundary_point1);
287 case 2:
288 return( ( ( boundary_point1 == e.boundary_point1)
289 && ( boundary_point2 == e.boundary_point2))
290 || ( ( boundary_point1 == e.boundary_point2)
291 && ( boundary_point2 == e.boundary_point1)));
292 case 3:
293 case 5:
294 return( conic1 == e.conic1);
295 case 4:
296 return( ( ( conic1 == e.conic1)
297 && ( conic2 == e.conic2))
298 || ( ( conic1 == e.conic2)
299 && ( conic2 == e.conic1)));
300 default:
301 CGAL_optimisation_assertion( ( n_boundary_points >= 0)
302 && ( n_boundary_points <= 5)); }
303 // keeps g++ happy
304 return( false);
305 }
306
307 bool
308 operator != (
309 const CGAL::_Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& e) const
310 {
311 return( ! ( *this == e));
312 }
313 };
314
315 // I/O
316 template < class PT_, class DA_ >
317 std::ostream&
318 operator << ( std::ostream& os,
319 const CGAL::_Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& e)
320 {
321 const char* const empty = "";
322 const char* const pretty_head =
323 "CGAL::Min_ellipse_2_adapterC2::Ellipse( ";
324 const char* const pretty_sep = ", ";
325 const char* const pretty_tail = ")";
326 const char* const ascii_sep = " ";
327
328 const char* head = empty;
329 const char* sep = empty;
330 const char* tail = empty;
331
332 switch ( CGAL::IO::get_mode( os)) {
333 case CGAL::IO::PRETTY:
334 head = pretty_head;
335 sep = pretty_sep;
336 tail = pretty_tail;
337 break;
338 case CGAL::IO::ASCII:
339 sep = ascii_sep;
340 break;
341 case CGAL::IO::BINARY:
342 break;
343 default:
344 CGAL_optimisation_assertion_msg( false,
345 "CGAL::IO::get_mode( os) invalid!");
346 break; }
347
348 os << head << e.n_boundary_points;
349 switch ( e.n_boundary_points) {
350 case 0:
351 break;
352 case 1:
353 os << sep << e.boundary_point1;
354 break;
355 case 2:
356 os << sep << e.boundary_point1
357 << sep << e.boundary_point2;
358 break;
359 case 3:
360 case 5:
361 os << sep << e.conic1;
362 break;
363 case 4:
364 os << sep << e.conic1
365 << sep << e.conic2;
366 break; }
367 os << tail;
368
369 return( os);
370 }
371
372 template < class PT_, class DA_ >
373 std::istream&
374 operator >> ( std::istream& is,
375 CGAL::_Min_ellipse_2_adapterC2__Ellipse<PT_,DA_>& e)
376 {
377 switch ( CGAL::IO::get_mode( is)) {
378
379 case CGAL::IO::PRETTY:
380 std::cerr << std::endl;
381 std::cerr << "Stream must be in ascii or binary mode" << std::endl;
382 break;
383
384 case CGAL::IO::ASCII:
385 case CGAL::IO::BINARY:
386 CGAL::read( is, e.n_boundary_points);
387 switch ( e.n_boundary_points) {
388 case 0:
389 break;
390 case 1:
391 is >> e.boundary_point1;
392 break;
393 case 2:
394 is >> e.boundary_point1
395 >> e.boundary_point2;
396 break;
397 case 3:
398 case 5:
399 is >> e.conic1;
400 break;
401 case 4:
402 is >> e.conic1
403 >> e.conic2;
404 break; }
405 break;
406
407 default:
408 CGAL_optimisation_assertion_msg( false,
409 "CGAL::IO::mode invalid!");
410 break; }
411
412 return( is);
413 }
414
415 } //namespace CGAL
416
417 #endif // CGAL_MIN_ELLIPSE_2_ADAPTERC2_H
418
419 // ===== EOF ==================================================================
420