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
|
// Copyright (c) 1997 ETH Zurich (Switzerland).
// 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.2-branch/Min_sphere_of_spheres_d/include/CGAL/Min_sphere_of_spheres_d_pivot.C $
// $Id: Min_sphere_of_spheres_d_pivot.C 28567 2006-02-16 14:30:13Z lsaboret $
//
//
// Author(s) : Kaspar Fischer
#ifndef CGAL_MINIBALL_PIVOT_C
#define CGAL_MINIBALL_PIVOT_C
#include <CGAL/Min_sphere_of_spheres_d.h>
namespace CGAL_MINIBALL_NAMESPACE {
namespace Min_sphere_of_spheres_d_impl {
template<typename FT>
bool is_better(const FT& old,const FT& now,const Tag_false is_exact) {
return now > old;
}
template<typename FT>
bool is_better(const FT&,const FT&,const Tag_true is_exact) {
return true;
}
template<class Traits>
bool Support_set<Traits>::pivot(std::vector<const typename
Traits::Sphere *>& l,
int& e,
const int d) {
// remember old radius:
const Result old = radius();
// reset basis to {d}:
reset();
push(*l[d]);
// try all subsets:
std::bitset<Traits::D+1> T;
int pos = e;
bool up = true;
while (pos >= 0) {
if (pos == e) {
bool isEnclosingSupporting = is_spanning();
if (isEnclosingSupporting)
for(int i=0; i<e; ++i)
if (!T.test(i) && !contains(t.center_cartesian_begin(*l[i]),
t.radius(*l[i]),
Tol,Is_exact())) {
isEnclosingSupporting = false;
break;
}
if (isEnclosingSupporting) {
// rearrange balls:
int next = 0;
for(int i=0; i<e; ++i)
if (T.test(i))
std::swap(l[next++],l[i]);
std::swap(l[next++],l[d]);
e = next;
return is_better(old,radius(),Is_exact());
}
--pos;
up = false;
} else if (!T.test(pos)) {
if (up)
++pos;
else
if (push(*l[pos])) {
T.set(pos,true);
++pos;
up = true;
} else
--pos;
} else {
pop();
T.set(pos,false);
--pos;
up = false;
}
}
// Here, no basis has been found (this only happens because
// of rounding errors):
#ifdef CGAL_MINIBALL_WARNINGS
std::cerr << '!';
#endif
// revert basis:
reset();
for (int i=0; i<e; ++i)
push(*l[i]);
is_spanning();
// signal that we failed:
return false;
}
} // namespace Min_sphere_of_spheres_d_impl
} // namespace CGAL_MINIBALL_NAMESPACE
#endif // CGAL_MINIBALL_PIVOT_CC
|
