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 
42 namespace 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