1 // Copyright (c) 2000,2001
2 // Utrecht University (The Netherlands),
3 // ETH Zurich (Switzerland),
4 // INRIA Sophia-Antipolis (France),
5 // Max-Planck-Institute Saarbruecken (Germany),
6 // and Tel-Aviv University (Israel).  All rights reserved.
7 //
8 // This file is part of CGAL (www.cgal.org)
9 //
10 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Kernel_d/include/CGAL/Cartesian_d.h $
11 // $Id: Cartesian_d.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
12 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
13 //
14 //
15 // Author(s)     : Michael Seel
16 
17 #ifndef CGAL_CARTESIAN_D_H
18 #define CGAL_CARTESIAN_D_H
19 
20 #include <CGAL/basic.h>
21 #include <CGAL/representation_tags.h>
22 #include <CGAL/Kernel_d/function_objects.h>
23 #include <CGAL/Linear_algebraCd.h>
24 #include <vector>
25 
26 #include <CGAL/Kernel_d/Kernel_classesCd.h>
27 #include <CGAL/Kernel_d/PointCd.h>
28 #include <CGAL/Kernel_d/VectorCd.h>
29 #include <CGAL/Kernel_d/DirectionCd.h>
30 #include <CGAL/Kernel_d/HyperplaneCd.h>
31 #include <CGAL/Kernel_d/Aff_transformationCd.h>
32 #include <CGAL/Kernel_d/PointCd_impl.h>
33 #include <CGAL/Kernel_d/VectorCd_impl.h>
34 #include <CGAL/Kernel_d/DirectionCd_impl.h>
35 #include <CGAL/Kernel_d/HyperplaneCd_impl.h>
36 #include <CGAL/Kernel_d/function_objectsCd.h>
37 #include <CGAL/Kernel_d/intersection_objectsCd.h>
38 #include <CGAL/Kernel_d/Interface_classes.h>
39 #include <CGAL/Kernel_d/simple_objects.h>
40 #include <CGAL/Dimension.h>
41 
42 namespace CGAL {
43 
44 template <class pFT, class pLA = Linear_algebraCd<pFT> >
45 class Cartesian_d
46 {
47 public:
48   typedef Cartesian_d<pFT,pLA> Self;
49   typedef pFT                    RT;
50   typedef pFT                    FT;
51   typedef pLA                    LA;
52 
53   typedef Cartesian_tag        Rep_tag;
54   typedef Cartesian_tag        Kernel_tag;
55 
56   enum { Has_filtered_predicates = false };
57   typedef Boolean_tag<Has_filtered_predicates> Has_filtered_predicates_tag;
58 
59   typedef PointCd2<RT,LA>             Point_d_base;
60   // renamed because of clash with Cartesian...
61   typedef VectorCd<RT,LA>             Vector_d_base;
62   typedef DirectionCd<RT,LA>          Direction_d_base;
63   typedef HyperplaneCd<RT,LA>         Hyperplane_d_base;
64   typedef Aff_transformationCd<RT,LA> Aff_transformation_d_base;
65 
66   typedef CGAL::Point_d<Self>              Point_d;
67   typedef CGAL::Vector_d<Self>             Vector_d;
68   typedef CGAL::Direction_d<Self>          Direction_d;
69   typedef CGAL::Hyperplane_d<Self>         Hyperplane_d;
70   typedef CGAL::Aff_transformation_d<Self> Aff_transformation_d;
71 
72   typedef typename Point_d_base::Cartesian_const_iterator Cartesian_const_iterator_d;
73 
74     // Boolean   had originally been Bool. It was renamed to avoid a conflict
75     // between a macro defined in Xlib.h poorly chosen to have the same name,
76     // that is 'Bool'.
77     typedef typename Same_uncertainty_nt<bool, FT>::type
78                                                         Boolean;
79     typedef typename Same_uncertainty_nt<CGAL::Sign, FT>::type
80                                                         Sign;
81     typedef typename Same_uncertainty_nt<CGAL::Comparison_result, FT>::type
82                                                         Comparison_result;
83     typedef typename Same_uncertainty_nt<CGAL::Orientation, FT>::type
84                                                         Orientation;
85     typedef typename Same_uncertainty_nt<CGAL::Oriented_side, FT>::type
86                                                         Oriented_side;
87     typedef typename Same_uncertainty_nt<CGAL::Bounded_side, FT>::type
88                                                         Bounded_side;
89     typedef typename Same_uncertainty_nt<CGAL::Angle, FT>::type
90                                                         Angle;
91 
92   typedef Dynamic_dimension_tag            Dimension;
93 
94   template <typename T>
95   struct Ambient_dimension {
96     typedef typename T::Ambient_dimension type;
97   };
98 
99   template <typename T>
100   struct Feature_dimension {
101     typedef typename T::Feature_dimension type;
102   };
103 
104   template <typename K>
105   class Construct_cartesian_const_iterator
106   {
107     typedef typename K::Point_d Point_d;
108     typedef typename K::Cartesian_const_iterator_d  Cartesian_const_iterator_d;
109 
110   public:
111     typedef Cartesian_const_iterator_d result_type;
112 
113     Cartesian_const_iterator_d
operator()114     operator()(const Point_d& p) const
115     {
116       return p.cartesian_begin();
117     }
118 
119     Cartesian_const_iterator_d
operator()120     operator()( const Point_d& p, int) const
121     {
122       return p.cartesian_end();
123     }
124   };
125 
126   // TODO: Make it work for the other values
127  template <typename K>
128   class Construct_vertex
129   {
130     typedef typename K::Point_d Point_d;
131     typedef typename K::Iso_box_d Iso_box_d;
132     typedef typename K::Cartesian_const_iterator_d  Cartesian_const_iterator_d;
133   public:
134     typedef Point_d result_type;
135 
operator()136     Point_d operator()(const Iso_box_d&  b, int i)
137     {
138       if(i == 0){
139         return (b.min)();
140       }
141       return (b.max)();
142     }
143   };
144 
145 
146   typedef Construct_vertex<Self> Construct_vertex_d;
147 
148     typedef Construct_cartesian_const_iterator<Self>
149                            Construct_cartesian_const_iterator_d;
150 
151   Construct_cartesian_const_iterator_d
construct_cartesian_const_iterator_d_object()152   construct_cartesian_const_iterator_d_object() const
153   {
154     return Construct_cartesian_const_iterator_d();
155   }
156 
157  template <typename K>
158   class Construct_min_vertex
159   {
160     typedef typename K::Point_d Point_d;
161     typedef typename K::Iso_box_d Iso_box_d;
162   public:
163     typedef Point_d result_type;
164 
operator()165     Point_d operator()(const Iso_box_d&  b)
166     {
167       return (b.min)();
168     }
169   };
170   typedef Construct_min_vertex<Self> Construct_min_vertex_d;
171 
172   Construct_min_vertex_d
construct_min_vertex_d_object()173   construct_min_vertex_d_object() const
174   {
175     return Construct_min_vertex_d();
176   }
177 
178 
179  template <typename K>
180   class Construct_max_vertex
181   {
182     typedef typename K::Point_d Point_d;
183     typedef typename K::Iso_box_d Iso_box_d;
184   public:
185     typedef Point_d result_type;
186 
operator()187     Point_d operator()(const Iso_box_d&  b)
188     {
189       return (b.max)();
190     }
191   };
192   typedef Construct_max_vertex<Self> Construct_max_vertex_d;
193 
194   Construct_max_vertex_d
construct_max_vertex_d_object()195   construct_max_vertex_d_object() const
196   {
197     return Construct_max_vertex_d();
198   }
199 
200   // meta types (fit both kernels):
201   typedef CGAL::Sphere_d<Self>   Sphere_d;
202   typedef CGAL::Iso_box_d<Self>  Iso_box_d;
203   typedef CGAL::Segment_d<Self>  Segment_d;
204   typedef CGAL::Ray_d<Self>      Ray_d;
205   typedef CGAL::Line_d<Self>     Line_d;
206 
207   // construction objects:
208   typedef internal::Construct<Point_d> Construct_point_d;
construct_point_d_object()209   Construct_point_d construct_point_d_object() const
210   { return Construct_point_d(); }
211 
212   typedef internal::Construct<Vector_d> Construct_vector_d;
construct_vector_d_object()213   Construct_vector_d construct_vector_d_object() const
214   { return Construct_vector_d(); }
215 
216   typedef internal::Construct<Direction_d> Construct_direction_d;
construct_direction_d_object()217   Construct_direction_d construct_direction_d_object() const
218   { return Construct_direction_d(); }
219 
220   typedef internal::Construct<Segment_d> Construct_segment_d;
construct_segment_d_object()221   Construct_segment_d construct_segment_d_object() const
222   { return Construct_segment_d(); }
223 
224   typedef internal::Construct<Ray_d> Construct_ray_d;
construct_ray_d_object()225   Construct_ray_d construct_ray_d_object() const
226   { return Construct_ray_d(); }
227 
228   typedef internal::Construct<Line_d> Construct_line_d;
construct_line_d_object()229   Construct_line_d construct_line_d_object() const
230   { return Construct_line_d(); }
231 
232   typedef internal::Construct<Iso_box_d> Construct_iso_box_d;
construct_iso_box_d_object()233   Construct_iso_box_d construct_iso_box_d_object() const
234   { return Construct_iso_box_d(); }
235 
236   typedef internal::Construct<Hyperplane_d> Construct_hyperplane_d;
construct_hyperplane_d_object()237   Construct_hyperplane_d construct_hyperplane_d_object() const
238   { return Construct_hyperplane_d(); }
239 
240   typedef internal::Construct<Sphere_d> Construct_sphere_d;
construct_sphere_d_object()241   Construct_sphere_d construct_sphere_d_object() const
242   { return Construct_sphere_d(); }
243 
244   typedef internal::Construct<Aff_transformation_d>
245     Construct_aff_transformation_d;
246   Construct_aff_transformation_d
construct_aff_transformation_d_object()247     construct_aff_transformation_d_object() const
248   { return Construct_aff_transformation_d(); }
249 
250   // function objects:
251   typedef Compute_coordinateCd<Self> Compute_coordinate_d;
252   typedef Lift_to_paraboloidCd<Self> Lift_to_paraboloid_d;
253   typedef Project_along_d_axisCd<Self> Project_along_d_axis_d;
254   typedef MidpointCd<Self> Midpoint_d;
255   typedef Squared_distanceCd<Self> Squared_distance_d;
256   typedef Position_on_lineCd<Self> Position_on_line_d;
257   typedef Barycentric_coordinatesCd<Self> Barycentric_coordinates_d;
258   typedef OrientationCd<Self> Orientation_d;
259   typedef Coaffine_orientationCd<Self> Coaffine_orientation_d;
260   typedef Side_of_oriented_sphereCd<Self> Side_of_oriented_sphere_d;
261   typedef Side_of_oriented_subsphereCd<Self> Side_of_oriented_subsphere_d;
262   typedef Side_of_bounded_sphereCd<Self> Side_of_bounded_sphere_d;
263   typedef Contained_in_simplexCd<Self> Contained_in_simplex_d;
264   typedef Contained_in_affine_hullCd<Self> Contained_in_affine_hull_d;
265   typedef Affine_rankCd<Self> Affine_rank_d;
266   typedef Affinely_independentCd<Self> Affinely_independent_d;
267   typedef Compare_lexicographicallyCd<Self> Compare_lexicographically_d;
268   typedef Lt_from_compare<Self> Less_lexicographically_d;
269   typedef Le_from_compare<Self> Less_or_equal_lexicographically_d;
270   typedef Less_coordinateCd<Self> Less_coordinate_d;
271   typedef Point_dimensionCd<Self> Point_dimension_d;
272   typedef Eq_from_method<Self> Equal_d;
273   typedef Center_of_sphereCd<Self> Center_of_sphere_d;
274   typedef Contained_in_linear_hullCd<Self> Contained_in_linear_hull_d;
275   typedef Linear_rankCd<Self> Linear_rank_d;
276   typedef Linearly_independentCd<Self> Linearly_independent_d;
277   typedef Linear_baseCd<Self> Linear_base_d;
278 
compute_coordinate_d_object()279   Compute_coordinate_d compute_coordinate_d_object() const
280   { return Compute_coordinate_d(); }
point_dimension_d_object()281   Point_dimension_d point_dimension_d_object() const
282   { return Point_dimension_d(); }
less_coordinate_d_object()283   Less_coordinate_d less_coordinate_d_object() const
284   { return Less_coordinate_d(); }
lift_to_paraboloid_d_object()285   Lift_to_paraboloid_d lift_to_paraboloid_d_object() const
286   { return Lift_to_paraboloid_d(); }
project_along_d_axis_d_object()287   Project_along_d_axis_d project_along_d_axis_d_object() const
288   { return Project_along_d_axis_d(); }
midpoint_d_object()289   Midpoint_d midpoint_d_object() const
290   { return Midpoint_d(); }
squared_distance_d_object()291   Squared_distance_d squared_distance_d_object() const
292   { return Squared_distance_d(); }
position_on_line_d_object()293   Position_on_line_d position_on_line_d_object() const
294   { return Position_on_line_d(); }
barycentric_coordinates_d_object()295   Barycentric_coordinates_d barycentric_coordinates_d_object() const
296   { return Barycentric_coordinates_d(); }
orientation_d_object()297   Orientation_d orientation_d_object() const
298   { return Orientation_d(); }
coaffine_orientation_d_object()299   Coaffine_orientation_d coaffine_orientation_d_object() const
300   { return Coaffine_orientation_d(); }
side_of_oriented_sphere_d_object()301   Side_of_oriented_sphere_d side_of_oriented_sphere_d_object() const
302   { return Side_of_oriented_sphere_d(); }
side_of_oriented_subsphere_d_object()303   Side_of_oriented_subsphere_d side_of_oriented_subsphere_d_object() const
304   { return Side_of_oriented_subsphere_d(); }
side_of_bounded_sphere_d_object()305   Side_of_bounded_sphere_d side_of_bounded_sphere_d_object() const
306   { return Side_of_bounded_sphere_d(); }
contained_in_simplex_d_object()307   Contained_in_simplex_d contained_in_simplex_d_object() const
308   { return Contained_in_simplex_d(); }
contained_in_affine_hull_d_object()309   Contained_in_affine_hull_d contained_in_affine_hull_d_object() const
310   { return Contained_in_affine_hull_d(); }
affine_rank_d_object()311   Affine_rank_d affine_rank_d_object() const
312   { return Affine_rank_d(); }
affinely_independent_d_object()313   Affinely_independent_d affinely_independent_d_object() const
314   { return Affinely_independent_d(); }
equal_d_object()315   Equal_d equal_d_object() const
316   { return Equal_d(); }
compare_lexicographically_d_object()317   Compare_lexicographically_d compare_lexicographically_d_object() const
318   { return Compare_lexicographically_d(); }
less_lexicographically_d_object()319   Less_lexicographically_d less_lexicographically_d_object() const
320   { return Less_lexicographically_d(); }
321   Less_or_equal_lexicographically_d
less_or_equal_lexicographically_d_object()322     less_or_equal_lexicographically_d_object() const
323   { return Less_or_equal_lexicographically_d(); }
center_of_sphere_d_object()324   Center_of_sphere_d center_of_sphere_d_object() const
325   { return Center_of_sphere_d(); }
contained_in_linear_hull_d_object()326   Contained_in_linear_hull_d contained_in_linear_hull_d_object() const
327   { return Contained_in_linear_hull_d(); }
linear_rank_d_object()328   Linear_rank_d linear_rank_d_object() const
329   { return Linear_rank_d(); }
linearly_independent_d_object()330   Linearly_independent_d linearly_independent_d_object() const
331   { return Linearly_independent_d(); }
linear_base_d_object()332   Linear_base_d linear_base_d_object() const
333   { return Linear_base_d(); }
334 
335   // Intersection objects:
336   typedef CGAL::Line_line_intersectionCd<Self> Line_line_intersection_d;
337   typedef CGAL::Line_hyperplane_intersectionCd<Self>
338                                                Line_hyperplane_intersection_d;
339   typedef CGAL::Line_d_Line_d_pair<Self> Line_d_Line_d_pair;
340   typedef CGAL::Ray_d_Ray_d_pair<Self> Ray_d_Ray_d_pair;
341   typedef CGAL::Segment_d_Segment_d_pair<Self> Segment_d_Segment_d_pair;
342   typedef CGAL::Line_d_Ray_d_pair<Self> Line_d_Ray_d_pair;
343   typedef CGAL::Line_d_Segment_d_pair<Self> Line_d_Segment_d_pair;
344   typedef CGAL::Ray_d_Segment_d_pair<Self> Ray_d_Segment_d_pair;
345   typedef CGAL::Line_d_Hyperplane_d_pair<Self> Line_d_Hyperplane_d_pair;
346   typedef CGAL::Ray_d_Hyperplane_d_pair<Self> Ray_d_Hyperplane_d_pair;
347   typedef CGAL::Segment_d_Hyperplane_d_pair<Self> Segment_d_Hyperplane_d_pair;
348 
349   typedef internal::Intersect<Self> Intersect_d;
intersect_d_object()350   Intersect_d intersect_d_object() const
351   { return Intersect_d(); }
352 
353   typedef internal::Do_intersect<Self> Do_intersect_d;
do_intersect_d_object()354   Do_intersect_d do_intersect_d_object() const
355   { return Do_intersect_d(); }
356 
357   // FT - RT conversion and access :
358 
make_FT(const RT & num,const RT & denom)359   static  FT make_FT(const RT & num, const RT& denom)
360   { return num/denom; }
361 
make_FT(const RT & num)362   static  FT make_FT(const RT & num)
363   { return FT(num); }
364 
FT_numerator(const FT & r)365   static  RT FT_numerator(const FT &r)
366   { return r; }
367 
FT_denominator(const FT &)368   static  RT FT_denominator(const FT & /*r*/)
369   { return RT(1); }
370 
371   // special stuff for traits class character :
372 
373   struct Component_accessor_d {
374     template <typename C>
dimensionComponent_accessor_d375     int dimension(const C& c) const { return c.dimension(); }
376     template <typename C>
homogeneousComponent_accessor_d377     RT homogeneous(const C& c, int i) { return c.homogeneous(i); }
378     template <typename C>
cartesianComponent_accessor_d379     FT cartesian(const C& c, int i) { return c.cartesian(i); }
380   };
component_accessor_d_object()381   Component_accessor_d component_accessor_d_object() const
382   { return Component_accessor_d(); }
383 
384   typedef internal::Call_has_on_positive_side Has_on_positive_side_d;
has_on_positive_side_d_object()385   Has_on_positive_side_d has_on_positive_side_d_object() const
386   { return Has_on_positive_side_d(); }
387 
388   typedef internal::Call_oriented_side Oriented_side_d;
oriented_side_d_object()389   Oriented_side_d oriented_side_d_object() const
390   { return Oriented_side_d(); }
391 
392   struct Value_at_d {
operatorValue_at_d393     RT operator()(const Hyperplane_d& h, const Point_d& p) const
394     { return h.value_at(p); }
395   };
value_at_d_object()396   Value_at_d value_at_d_object() const
397   { return Value_at_d(); }
398 
399   struct Point_to_vector_d {
operatorPoint_to_vector_d400     Vector_d operator()(const Point_d& p) const
401     { return p-CGAL::ORIGIN; }
402   };
point_to_vector_d_object()403   Point_to_vector_d point_to_vector_d_object() const
404   { return Point_to_vector_d(); }
405 
406   struct Vector_to_point_d {
operatorVector_to_point_d407     Point_d operator()(const Vector_d& v) const
408     { return CGAL::ORIGIN+v; }
409   };
vector_to_point_d_object()410   Vector_to_point_d vector_to_point_d_object() const
411   { return Vector_to_point_d(); }
412 
413   struct Orthogonal_vector_d {
operatorOrthogonal_vector_d414     Vector_d operator()(const Hyperplane_d& h) const
415     { return h.orthogonal_vector(); }
416   };
orthogonal_vector_d_object()417   Orthogonal_vector_d orthogonal_vector_d_object() const
418   { return Orthogonal_vector_d(); }
419 
420   struct Point_of_sphere_d {
operatorPoint_of_sphere_d421     Point_d operator()(const Sphere_d& S, int i)
422     { return S.point(i); }
423   };
point_of_sphere_d_object()424   Point_of_sphere_d point_of_sphere_d_object() const
425   { return Point_of_sphere_d(); }
426 
427 }; // Cartesian_d<R>
428 
429 
430 } //namespace CGAL
431 
432 #include <CGAL/Kernel_d/Point_d.h>
433 #include <CGAL/Kernel_d/Vector_d.h>
434 #include <CGAL/Kernel_d/Direction_d.h>
435 #include <CGAL/Kernel_d/Hyperplane_d.h>
436 #include <CGAL/Kernel_d/Aff_transformation_d.h>
437 #include <CGAL/Kernel_d/Sphere_d.h>
438 #include <CGAL/Kernel_d/Iso_box_d.h>
439 #include <CGAL/Kernel_d/Segment_d.h>
440 #include <CGAL/Kernel_d/Ray_d.h>
441 #include <CGAL/Kernel_d/Line_d.h>
442 #include <CGAL/Kernel_d/Line_d_impl.h>
443 #include <CGAL/intersections_d.h>
444 
445 #endif // CGAL_CARTESIAN_D_H
446