wfmath 1.0.3
A math library for the Worldforge system.
miniball.h
1
2
3// Copright (C) 1999
4// $Revision$
5// $Date$
6//
7// This program is free software; you can redistribute it and/or modify
8// it under the terms of the GNU General Public License as published by
9// the Free Software Foundation; either version 2 of the License, or
10// (at your option) any later version.
11//
12// This program is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15// GNU General Public License for more details.
16//
17// You should have received a copy of the GNU General Public License
18// along with this program; if not, write to the Free Software
19// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA,
20// or download the License terms from prep.ai.mit.edu/pub/gnu/COPYING-2.0.
21//
22// Contact:
23// --------
24// Bernd Gaertner
25// Institut f. Informatik
26// ETH Zuerich
27// ETH-Zentrum
28// CH-8092 Zuerich, Switzerland
29// http://www.inf.ethz.ch/personal/gaertner
30//
31
32// 2001-1-9: included in WFMath backend. Namespace wrapping added
33// and filename changed to follow WFMath conventions, but otherwise
34// unchanged.
35
36#ifndef WFMATH_MINIBALL_H
37#define WFMATH_MINIBALL_H
38
39#include <list>
40#include <wfmath/wrapped_array.h>
41
42namespace WFMath { namespace _miniball {
43
44 template <int d> class Miniball;
45 template <int d> class Basis;
46
47 // Miniball
48 // --------
49
50 template <int d>
51 class Miniball {
52 public:
53 // types
54 typedef Wrapped_array<d> Point;
55 typedef typename std::list<Point>::iterator It;
56 typedef typename std::list<Point>::const_iterator Cit;
57
58 private:
59 // data members
60 std::list<Point> L; // STL list keeping the points
61 Basis<d> B; // basis keeping the current ball
62 It support_end; // past-the-end iterator of support set
63
64 // private methods
65 void mtf_mb (It k);
66 void pivot_mb (It k);
67 void move_to_front (It j);
68 double max_excess (It t, It i, It& pivot) const;
69 double abs (double r) const {return (r>0)? r: (-r);}
70 double sqr (double r) const {return r*r;}
71
72 public:
73 // construction
74 Miniball() : L(), B(), support_end() {}
75 void check_in (const Point& p);
76 void build (bool pivoting = true);
77
78 // access
79 Point center() const;
80 double squared_radius () const;
81 int nr_points () const;
82 Cit points_begin () const;
83 Cit points_end () const;
84 int nr_support_points () const;
85 Cit support_points_begin () const;
86 Cit support_points_end () const;
87
88 // checking
89 double accuracy (double& slack) const;
90 bool is_valid (double tolerance = 1e-15) const;
91 };
92
93
94
95 // Basis
96 // -----
97
98 template <int d>
99 class Basis {
100 private:
101 // types
102 typedef Wrapped_array<d> Point;
103
104 // data members
105 int m, s; // size and number of support points
106 double q0[d];
107
108 double z[d+1];
109 double f[d+1];
110 double v[d+1][d];
111 double a[d+1][d];
112
113 double c[d+1][d];
114 double sqr_r[d+1];
115
116 double* current_c; // points to some c[j]
117 double current_sqr_r;
118
119 double sqr (double r) const {return r*r;}
120
121 public:
122 Basis();
123
124 // access
125 const double* center() const;
126 double squared_radius() const;
127 int size() const;
128 int support_size() const;
129 double excess (const Point& p) const;
130
131 // modification
132 void reset(); // generates empty sphere with m=s=0
133 bool push (const Point& p);
134 void pop ();
135
136 // checking
137 double slack() const;
138 };
139
140}} // namespace WFMath::_miniball
141
142#endif // WFMATH_MINIBALL_H
Generic library namespace.
Definition: shape.h:41