1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
|
// Copyright (c) 2001 Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Convex_hull_3/include/CGAL/Convex_hull_traits_3.h $
// $Id: Convex_hull_traits_3.h 44317 2008-07-22 12:29:01Z spion $
//
//
// Author(s) : Susan Hert <hert@mpi-sb.mpg.de>
#ifndef CGAL_CONVEX_HULL_TRAITS_3_H
#define CGAL_CONVEX_HULL_TRAITS_3_H
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Convex_hull_projective_xy_traits_2.h>
#include <CGAL/Convex_hull_projective_xz_traits_2.h>
#include <CGAL/Convex_hull_projective_yz_traits_2.h>
namespace CGAL {
template < class R_ >
class Point_triple
{
protected:
typedef typename R_::FT FT;
typedef typename R_::Point_3 Point_3;
typedef typename R_::Vector_3 Vector_3;
Point_3 p_, q_, r_;
public:
typedef R_ R;
Point_triple() {}
Point_triple(const Point_3 &p, const Point_3 &q, const Point_3 &r)
: p_(p), q_(q), r_(r)
{}
const Point_3& p() const { return p_; }
const Point_3& q() const { return q_; }
const Point_3& r() const { return r_; }
};
template <class K>
class Point_triple_has_on_positive_side_3 {
public:
typedef typename K::Point_3 Point_3;
typedef typename K::Plane_3 Plane_3;
bool
operator()( const Plane_3& pl, const Point_3& p) const
{
typename K::Orientation_3 o;
return ( o(pl.p(), pl.q(), pl.r(), p) == CGAL::POSITIVE );
}
};
template <class K, class OldK>
class Point_triple_construct_orthogonal_vector_3
{
public:
typedef typename K::Vector_3 Vector_3;
typedef typename K::Plane_3 Plane_3;
Vector_3 operator()(const Plane_3& plane) const
{
typename OldK::Construct_orthogonal_vector_3
construct_orthogonal_vector_3;
return construct_orthogonal_vector_3(plane.p(), plane.q(), plane.r());
}
};
template <class K>
class Point_triple_oriented_side_3
{
public:
typedef typename K::Point_3 Point_3;
typedef typename K::Plane_3 Plane_3;
typedef Oriented_side result_type;
result_type
operator()( const Plane_3& pl, const Point_3& p) const
{
typename K::Orientation_3 o;
Orientation ori = o(pl.p(), pl.q(), pl.r(), p) ;
if(ori > 0) return ON_POSITIVE_SIDE;
if(ori < 0) return ON_NEGATIVE_SIDE;
return ON_ORIENTED_BOUNDARY;
}
};
template <typename K, typename OldK>
class Point_triple_less_signed_distance_to_plane_3
{
public:
typedef typename K::Point_3 Point_3;
typedef typename K::Plane_3 Plane_3;
typedef bool result_type;
bool
operator()( const Plane_3& h, const Point_3& p, const Point_3& q) const
{
const Point_3& hp = h.p();
const Point_3& hq = h.q();
const Point_3& hr = h.r();
typename OldK::Less_signed_distance_to_plane_3
less_signed_distance_to_plane_3;
return less_signed_distance_to_plane_3(hp, hq, hr, p, q);
}
};
template <class T>
class Max_coordinate_3
{
public:
int operator()(const T& v)
{
if (CGAL_NTS abs(v.x()) >= CGAL_NTS abs(v.y()))
{
if (CGAL_NTS abs(v.x()) >= CGAL_NTS abs(v.z())) return 0;
return 2;
}
else
{
if (CGAL_NTS abs(v.y()) >= CGAL_NTS abs(v.z())) return 1;
return 2;
}
}
};
template <class R_>
class Convex_hull_traits_3
{
public:
typedef R_ R;
typedef Convex_hull_traits_3<R> Self;
typedef typename R::Point_3 Point_3;
typedef typename R::Segment_3 Segment_3;
typedef typename R::Triangle_3 Triangle_3;
typedef Point_triple<R> Plane_3;
typedef typename R::Vector_3 Vector_3;
typedef CGAL::Polyhedron_3<R> Polyhedron_3;
typedef typename R::Construct_segment_3 Construct_segment_3;
typedef typename R::Construct_ray_3 Construct_ray_3;
class Construct_plane_3 {
public:
Plane_3 operator ()(const Point_3& p, const Point_3& q, const Point_3& r)
{
return Plane_3(p,q,r);
}
};
typedef typename R::Construct_vector_3 Construct_vector_3;
typedef typename R::Construct_triangle_3 Construct_triangle_3;
typedef typename R::Construct_centroid_3 Construct_centroid_3;
typedef Point_triple_construct_orthogonal_vector_3<Self, R>
Construct_orthogonal_vector_3;
typedef typename R::Equal_3 Equal_3;
typedef typename R::Orientation_3 Orientation_3;
typedef typename R::Collinear_3 Collinear_3;
typedef typename R::Coplanar_3 Coplanar_3;
typedef typename R::Less_distance_to_point_3 Less_distance_to_point_3;
typedef Point_triple_has_on_positive_side_3<Self> Has_on_positive_side_3;
typedef Point_triple_less_signed_distance_to_plane_3<Self, R>
Less_signed_distance_to_plane_3;
// required for degenerate case of all points coplanar
typedef Convex_hull_projective_xy_traits_2<Point_3> Traits_xy;
typedef Convex_hull_projective_xz_traits_2<Point_3> Traits_xz;
typedef Convex_hull_projective_yz_traits_2<Point_3> Traits_yz;
typedef CGAL::Max_coordinate_3<Vector_3> Max_coordinate_3;
// for postcondition checking
typedef typename R::Ray_3 Ray_3;
typedef typename R::Has_on_3 Has_on_3;
typedef Point_triple_oriented_side_3<Self> Oriented_side_3;
typedef typename R::Intersect_3 Intersect_3;
typedef typename R::Do_intersect_3 Do_intersect_3;
Construct_segment_3
construct_segment_3_object() const
{ return Construct_segment_3(); }
Construct_ray_3
construct_ray_3_object() const
{ return Construct_ray_3(); }
Construct_plane_3
construct_plane_3_object() const
{ return Construct_plane_3(); }
Construct_triangle_3
construct_triangle_3_object() const
{ return Construct_triangle_3(); }
Construct_vector_3
construct_vector_3_object() const
{ return Construct_vector_3(); }
Construct_centroid_3
construct_centroid_3_object() const
{ return Construct_centroid_3(); }
Construct_orthogonal_vector_3
construct_orthogonal_vector_3_object() const
{ return Construct_orthogonal_vector_3(); }
Collinear_3
collinear_3_object() const
{ return Collinear_3(); }
Coplanar_3
coplanar_3_object() const
{ return Coplanar_3(); }
Has_on_3
has_on_3_object() const
{ return Has_on_3(); }
Less_distance_to_point_3
less_distance_to_point_3_object() const
{ return Less_distance_to_point_3(); }
Has_on_positive_side_3
has_on_positive_side_3_object() const
{ return Has_on_positive_side_3(); }
Oriented_side_3
oriented_side_3_object() const
{ return Oriented_side_3(); }
Equal_3
equal_3_object() const
{ return Equal_3(); }
Intersect_3
intersect_3_object() const
{ return Intersect_3(); }
Do_intersect_3
do_intersect_3_object() const
{ return Do_intersect_3(); }
Less_signed_distance_to_plane_3
less_signed_distance_to_plane_3_object() const
{ return Less_signed_distance_to_plane_3(); }
Max_coordinate_3
max_coordinate_3_object() const
{ return Max_coordinate_3(); }
};
} // namespace CGAL
#endif // CGAL_CONVEX_HULL_TRAITS_3_H
|
