1 // Copyright (c) 1997-2002 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_S2/include/CGAL/Nef_S2/Sphere_geometry.h $
7 // $Id: Sphere_geometry.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-inf.mpg.de>
12 // Peter Hachenberger <hachenberger@mpi-inf.mpg.de>
13
14 #ifndef CGAL_SPHERE_GEOMETRY_H
15 #define CGAL_SPHERE_GEOMETRY_H
16
17 #include <CGAL/license/Nef_S2.h>
18
19
20 #include <CGAL/basic.h>
21 #include <CGAL/intersection_3.h>
22 #include <list>
23
24 #undef CGAL_NEF_DEBUG
25 #define CGAL_NEF_DEBUG 113
26 #include <CGAL/Nef_2/debug.h>
27
28 namespace CGAL {
29
30 template <class R> class Sphere_point;
31 template <class R> class Sphere_segment;
32 template <class R> class Sphere_triangle;
33 template <class R> class Sphere_circle;
34 template <class R> class Sphere_direction;
35
36 } //namespace CGAL
37
38 #include <CGAL/Nef_S2/Sphere_point.h>
39 #include <CGAL/Nef_S2/Sphere_circle.h>
40 #include <CGAL/Nef_S2/Sphere_direction.h>
41 #include <CGAL/Nef_S2/Sphere_segment.h>
42 #include <CGAL/Nef_S2/Sphere_triangle.h>
43 #include <CGAL/Nef_S2/sphere_predicates.h>
44
45 namespace CGAL {
46
47 template <typename R_>
48 struct Positive_halfsphere_geometry {
49
50 typedef R_ R;
51 typedef CGAL::Sphere_point<R> Point_2;
52 typedef CGAL::Sphere_segment<R> Segment_2;
53
54 int axis;
55
Positive_halfsphere_geometryPositive_halfsphere_geometry56 Positive_halfsphere_geometry() : axis(2) {}
Positive_halfsphere_geometryPositive_halfsphere_geometry57 Positive_halfsphere_geometry(int check_sphere) : axis(check_sphere) {}
58
sourcePositive_halfsphere_geometry59 Point_2 source(const Segment_2& s) const
60 { return s.source(); }
targetPositive_halfsphere_geometry61 Point_2 target(const Segment_2& s) const
62 { return s.target(); }
construct_segmentPositive_halfsphere_geometry63 Segment_2 construct_segment(const Point_2& p, const Point_2& q) const
64 { return Segment_2(p,q); }
65
xz_pi_half_rotatePositive_halfsphere_geometry66 void xz_pi_half_rotate(Point_2& p) const
67 { p = Point_2(-p.hz(),p.hy(),p.hx()); }
68
zx_pi_half_rotatePositive_halfsphere_geometry69 void zx_pi_half_rotate(Point_2& p) const
70 { p = Point_2(-p.hz(),p.hy(),p.hx()); }
71
xy_pi_half_rotatePositive_halfsphere_geometry72 void xy_pi_half_rotate(Point_2& p) const
73 { p = Point_2(-p.hy(),p.hx(),p.hz()); }
74
orientationPositive_halfsphere_geometry75 int orientation(const Point_2& p1, const Point_2& p2,
76 const Point_2& p3) const {
77
78 int sor = CGAL::spherical_orientation(p1,p2,p3);
79 if (sor) return sor;
80 Point_2 pp1(p1), pp2(p2), pp3(p3);
81 switch(axis) {
82 case 0:
83 if ( !( p1.hx() == 0 && p2.hx() == 0 && p3.hx() == 0) ) return sor;
84 if ( p1.hz()<0 ) zx_pi_half_rotate(pp1);
85 if ( p2.hz()<0 ) zx_pi_half_rotate(pp2);
86 if ( p3.hz()<0 ) zx_pi_half_rotate(pp3);
87 return CGAL::spherical_orientation(pp1,pp2,pp3);
88 break;
89 case 1:
90 if ( !( p1.hy() == 0 && p2.hy() == 0 && p3.hy() == 0) ) return sor;
91 if ( p1.hx()>0 ) xy_pi_half_rotate(pp1);
92 if ( p2.hx()>0 ) xy_pi_half_rotate(pp2);
93 if ( p3.hx()>0 ) xy_pi_half_rotate(pp3);
94 return CGAL::spherical_orientation(pp1,pp2,pp3);
95 break;
96 case 2:
97 if ( !( p1.hz() == 0 && p2.hz() == 0 && p3.hz() == 0) ) return sor;
98 // sor==0 we perturb any point in the xy-plane with x>0
99 // by a negative rotation around the y-axis
100 // our perturbation is big :-) we take PI/2 :
101 if ( p1.hx()>0 ) xz_pi_half_rotate(pp1);
102 if ( p2.hx()>0 ) xz_pi_half_rotate(pp2);
103 if ( p3.hx()>0 ) xz_pi_half_rotate(pp3);
104 return CGAL::spherical_orientation(pp1,pp2,pp3);
105 break;
106 }
107 return 0;
108 }
109
orientationPositive_halfsphere_geometry110 int orientation(const Segment_2& s, const Point_2& p) const
111 { return orientation(s.source(),s.target(),p); }
112
is_degeneratePositive_halfsphere_geometry113 bool is_degenerate(const Segment_2& s) const
114 { return s.is_degenerate(); }
115
compare_xyPositive_halfsphere_geometry116 int compare_xy(const Point_2& p1, const Point_2& p2) const {
117 CGAL_NEF_TRACEN("compare_xy " << axis << ":" << p1 << " / " << p2);
118 return CGAL::spherical_compare(p1,p2,axis,+1);
119 }
120
intersectionPositive_halfsphere_geometry121 Point_2 intersection(const Segment_2& s1, const Segment_2& s2) const
122 { if (s1.sphere_circle() != s2.sphere_circle().opposite())
123 return s1.intersection(s2);
124 CGAL_assertion(s1.target()==s2.target());
125 return s1.target();
126 }
127
128 }; // Positive_halfsphere_geometry<R>
129
130 template <typename R>
131 struct Negative_halfsphere_geometry :
132 public Positive_halfsphere_geometry<R> {
133
134 typedef Positive_halfsphere_geometry<R> Base;
135 typedef typename Base::Point_2 Point_2;
136 typedef typename Base::Segment_2 Segment_2;
137
138 using Base::xz_pi_half_rotate;
139 using Base::zx_pi_half_rotate;
140 using Base::xy_pi_half_rotate;
141
Negative_halfsphere_geometryNegative_halfsphere_geometry142 Negative_halfsphere_geometry() : Base() {}
Negative_halfsphere_geometryNegative_halfsphere_geometry143 Negative_halfsphere_geometry(int check_sphere) : Base(check_sphere) {}
144
orientationNegative_halfsphere_geometry145 int orientation(const Point_2& p1, const Point_2& p2,
146 const Point_2& p3) const {
147
148 int sor = CGAL::spherical_orientation(p1,p2,p3);
149 if (sor) return sor;
150 Point_2 pp1(p1), pp2(p2), pp3(p3);
151 switch(((Base*) this)->axis) {
152 case 0:
153 if ( !( p1.hx() == 0 && p2.hx() == 0 && p3.hx() == 0) ) return sor;
154 if ( p1.hz()>0 ) zx_pi_half_rotate(pp1);
155 if ( p2.hz()>0 ) zx_pi_half_rotate(pp2);
156 if ( p3.hz()>0 ) zx_pi_half_rotate(pp3);
157 return CGAL::spherical_orientation(pp1,pp2,pp3);
158 break;
159 case 1:
160 if ( !( p1.hy() == 0 && p2.hy() == 0 && p3.hy() == 0) ) return sor;
161 if ( p1.hx()<0 ) xy_pi_half_rotate(pp1);
162 if ( p2.hx()<0 ) xy_pi_half_rotate(pp2);
163 if ( p3.hx()<0 ) xy_pi_half_rotate(pp3);
164 return CGAL::spherical_orientation(pp1,pp2,pp3);
165 break;
166 case 2:
167 if ( !( p1.hz() == 0 && p2.hz() == 0 && p3.hz() == 0) ) return sor;
168 // sor==0 we perturb any point in the xy-plane with x>0
169 // by a negative rotation around the y-axis
170 // our perturbation is big :-) we take PI/2 :
171 if ( p1.hx()<0 ) xz_pi_half_rotate(pp1);
172 if ( p2.hx()<0 ) xz_pi_half_rotate(pp2);
173 if ( p3.hx()<0 ) xz_pi_half_rotate(pp3);
174 return CGAL::spherical_orientation(pp1,pp2,pp3);
175 break;
176 }
177 return 0;
178 }
179
orientationNegative_halfsphere_geometry180 int orientation(const Segment_2& s, const Point_2& p) const
181 { return orientation(s.source(),s.target(),p); }
182
compare_xyNegative_halfsphere_geometry183 int compare_xy(const Point_2& p1, const Point_2& p2) const
184 { return CGAL::spherical_compare(p1,p2,this->axis,-1); }
185
186 }; // Negative_halfsphere_geometry<R>
187
188 template <typename R_>
189 struct Sphere_geometry {
190
191 typedef R_ R;
192 typedef typename R_::RT RT;
193 typedef typename R_::FT FT;
194 typedef CGAL::Sphere_point<R> Sphere_point;
195 typedef CGAL::Sphere_segment<R> Sphere_segment;
196 typedef CGAL::Sphere_circle<R> Sphere_circle;
197 typedef CGAL::Sphere_direction<R> Sphere_direction;
198 typedef CGAL::Sphere_triangle<R> Sphere_triangle;
199 typedef typename R::Point_3 Point_3;
200 typedef typename R::Plane_3 Plane_3;
201 typedef typename R::Aff_transformation_3 Aff_transformation_3;
202 typedef CGAL::Positive_halfsphere_geometry<R> Positive_halfsphere_geometry;
203 typedef CGAL::Negative_halfsphere_geometry<R> Negative_halfsphere_geometry;
204
sourceSphere_geometry205 Sphere_point source(const Sphere_segment& s) const
206 { return s.source(); }
207
targetSphere_geometry208 Sphere_point target(const Sphere_segment& s) const
209 { return s.target(); }
210
construct_segmentSphere_geometry211 Sphere_segment construct_segment(const Sphere_point& p,
212 const Sphere_point& q) const
213 { return Sphere_segment(p,q); }
214
construct_segmentSphere_geometry215 Sphere_segment construct_segment(const Sphere_point& p,
216 const Sphere_point& q,
217 const Plane_3& h) const
218 { return Sphere_segment(p,q,Sphere_circle(h)); }
219
affine_representationSphere_geometry220 Plane_3 affine_representation(const Plane_3& h, const Point_3& p) const
221 { RT wp = p.hw();
222 return Plane_3(wp*h.a(),wp*h.b(),wp*h.c(),
223 -(p.hx()*h.a() + p.hy()*h.b() + p.hz()*h.c())); }
224
linear_representationSphere_geometry225 Plane_3 linear_representation(const Plane_3& h) const
226 { return Plane_3(h.a(),h.b(),h.c(),0); }
227
228 /*
229 Positive_halfsphere_geometry PHG;
230 const Positive_halfsphere_geometry&
231 get_positive_halfsphere_geometry() const
232 { return PHG; }
233
234 Negative_halfsphere_geometry NHG;
235 const Negative_halfsphere_geometry&
236 get_negative_halfsphere_geometry() const
237 { return NHG; }
238 */
239
240 const Positive_halfsphere_geometry&
get_positive_halfsphere_geometrySphere_geometry241 get_positive_halfsphere_geometry(int a) const {
242 return Positive_halfsphere_geometry(a);
243 }
244
245 const Negative_halfsphere_geometry&
get_negative_halfsphere_geometrySphere_geometry246 get_negative_halfsphere_geometry(int a) const {
247 return Negative_halfsphere_geometry(a);
248 }
249
250 };
251
252
253
254 } //namespace CGAL
255 #endif //CGAL_SPHERE_GEOMETRY_H
256