00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef WFMATH_BALL_FUNCS_H
00027 #define WFMATH_BALL_FUNCS_H
00028
00029 #include <wfmath/const.h>
00030 #include <wfmath/point.h>
00031 #include <wfmath/axisbox.h>
00032 #include <wfmath/ball.h>
00033 #include <wfmath/miniball.h>
00034
00035 namespace WFMath {
00036
00037 template<const int dim>
00038 inline bool Ball<dim>::isEqualTo(const Ball<dim>& b, double epsilon) const
00039 {
00040 return Equal(m_center, b.m_center, epsilon)
00041 && Equal(m_radius, b.m_radius, epsilon);
00042 }
00043
00044 template<const int dim>
00045 AxisBox<dim> Ball<dim>::boundingBox() const
00046 {
00047 Point<dim> p_low, p_high;
00048
00049 for(int i = 0; i < dim; ++i) {
00050 p_low[i] = m_center[i] - m_radius;
00051 p_high[i] = m_center[i] + m_radius;
00052 }
00053
00054 bool valid = m_center.isValid();
00055
00056 p_low.setValid(valid);
00057 p_high.setValid(valid);
00058
00059 return AxisBox<dim>(p_low, p_high, true);
00060 }
00061
00062 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00063 template<const int dim, template<class, class> class container>
00064 Ball<dim> BoundingSphere(const container<Point<dim>, std::allocator<Point<dim> > >& c)
00065 {
00066 _miniball::Miniball<dim> m;
00067 _miniball::Wrapped_array<dim> w;
00068
00069 typename container<Point<dim>, std::allocator<Point<dim> > >::const_iterator i, end = c.end();
00070 bool valid = true;
00071
00072 for(i = c.begin(); i != end; ++i) {
00073 valid = valid && i->isValid();
00074 for(int j = 0; j < dim; ++j)
00075 w[j] = (*i)[j];
00076 m.check_in(w);
00077 }
00078
00079 m.build();
00080
00081 #ifndef NDEBUG
00082 double dummy;
00083 #endif
00084 assert("Check that bounding sphere is good to library accuracy" &&
00085 m.accuracy(dummy) < WFMATH_EPSILON);
00086
00087 w = m.center();
00088 Point<dim> center;
00089
00090 for(int j = 0; j < dim; ++j)
00091 center[j] = w[j];
00092
00093 center.setValid(valid);
00094
00095 return Ball<dim>(center, sqrt(m.squared_radius()));
00096 }
00097
00098 template<const int dim, template<class, class> class container>
00099 Ball<dim> BoundingSphereSloppy(const container<Point<dim>, std::allocator<Point<dim> > >& c)
00100 {
00101
00102
00103
00104
00105 typename container<Point<dim>, std::allocator<Point<dim> > >::const_iterator i = c.begin(),
00106 end = c.end();
00107 assert(i != end);
00108
00109 CoordType min[dim], max[dim];
00110 typename container<Point<dim>, std::allocator<Point<dim> > >::const_iterator min_p[dim], max_p[dim];
00111 bool valid = i->isValid();
00112
00113 for(int j = 0; j < dim; ++j) {
00114 min[j] = max[j] = (*i)[j];
00115 min_p[j] = max_p[j] = i;
00116 }
00117
00118 while(++i != end) {
00119 valid = valid && i->isValid();
00120 for(int j = 0; j < dim; ++j) {
00121 if(min[j] > (*i)[j]) {
00122 min[j] = (*i)[j];
00123 min_p[j] = i;
00124 }
00125 if(max[j] < (*i)[j]) {
00126 max[j] = (*i)[j];
00127 max_p[j] = i;
00128 }
00129 }
00130 }
00131
00132 CoordType span = -1;
00133 int direction = -1;
00134
00135 for(int j = 0; j < dim; ++j) {
00136 CoordType new_span = max[j] - min[j];
00137 if(new_span > span) {
00138 span = new_span;
00139 direction = j;
00140 }
00141 }
00142
00143 assert("Have a direction of maximum size" && direction != -1);
00144
00145 Point<dim> center = Midpoint(*(min_p[direction]), *(max_p[direction]));
00146 CoordType dist = SloppyDistance(*(min_p[direction]), center);
00147
00148 for(i = c.begin(); i != end; ++i) {
00149 if(i == min_p[direction] || i == max_p[direction])
00150 continue;
00151
00152 CoordType new_dist = SloppyDistance(*i, center);
00153
00154 if(new_dist > dist) {
00155 CoordType delta_dist = (new_dist - dist) / 2;
00156
00157
00158 center += (*i - center) * delta_dist / new_dist;
00159 dist += delta_dist;
00160 assert("Shifted ball contains new point" &&
00161 SquaredDistance(*i, center) <= dist * dist);
00162 }
00163 }
00164
00165 center.setValid(valid);
00166
00167 return Ball<2>(center, dist);
00168 }
00169 #endif
00170
00171
00172
00173
00174 template<const int dim>
00175 inline Ball<dim> Point<dim>::boundingSphere() const
00176 {
00177 return Ball<dim>(*this, 0);
00178 }
00179
00180 template<const int dim>
00181 inline Ball<dim> Point<dim>::boundingSphereSloppy() const
00182 {
00183 return Ball<dim>(*this, 0);
00184 }
00185
00186 }
00187
00188 #endif // WFMATH_BALL_FUNCS_H