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 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 bool Ball<dim>::operator< (const Ball<dim>& b) const
00046 {
00047 if(!Equal(m_radius, b.m_radius))
00048 return m_radius < b.m_radius;
00049
00050 return m_center < b.m_center;
00051 }
00052
00053 template<const int dim>
00054 AxisBox<dim> Ball<dim>::boundingBox() const
00055 {
00056 Point<dim> p_low, p_high;
00057
00058 for(int i = 0; i < dim; ++i) {
00059 p_low[i] = m_center[i] - m_radius;
00060 p_high[i] = m_center[i] + m_radius;
00061 }
00062
00063 bool valid = m_center.isValid();
00064
00065 p_low.setValid(valid);
00066 p_high.setValid(valid);
00067
00068 return AxisBox<dim>(p_low, p_high, true);
00069 }
00070
00071 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00072 template<const int dim, template<class> class container>
00073 Ball<dim> BoundingSphere(const container<Point<dim> >& c)
00074 {
00075 _miniball::Miniball<dim> m;
00076 _miniball::Wrapped_array<dim> w;
00077
00078 typename container<Point<dim> >::const_iterator i, end = c.end();
00079 bool valid = true;
00080
00081 for(i = c.begin(); i != end; ++i) {
00082 valid = valid && i->isValid();
00083 for(int j = 0; j < dim; ++j)
00084 w[j] = (*i)[j];
00085 m.check_in(w);
00086 }
00087
00088 m.build();
00089
00090 #ifndef NDEBUG
00091 double dummy;
00092 #endif
00093 assert("Check that bounding sphere is good to library accuracy" &&
00094 m.accuracy(dummy) < WFMATH_EPSILON);
00095
00096 w = m.center();
00097 Point<dim> center;
00098
00099 for(int j = 0; j < dim; ++j)
00100 center[j] = w[j];
00101
00102 center.setValid(valid);
00103
00104 return Ball<dim>(center, sqrt(m.squared_radius()));
00105 }
00106
00107 template<const int dim, template<class> class container>
00108 Ball<dim> BoundingSphereSloppy(const container<Point<dim> >& c)
00109 {
00110
00111
00112
00113
00114 typename container<Point<dim> >::const_iterator i = c.begin(),
00115 end = c.end();
00116 assert(i != end);
00117
00118 CoordType min[dim], max[dim];
00119 typename container<Point<dim> >::const_iterator min_p[dim], max_p[dim];
00120 bool valid = i->isValid();
00121
00122 for(int j = 0; j < dim; ++j) {
00123 min[j] = max[j] = (*i)[j];
00124 min_p[j] = max_p[j] = i;
00125 }
00126
00127 while(++i != end) {
00128 valid = valid && i->isValid();
00129 for(int j = 0; j < dim; ++j) {
00130 if(min[j] > (*i)[j]) {
00131 min[j] = (*i)[j];
00132 min_p[j] = i;
00133 }
00134 if(max[j] < (*i)[j]) {
00135 max[j] = (*i)[j];
00136 max_p[j] = i;
00137 }
00138 }
00139 }
00140
00141 CoordType span = -1;
00142 int direction = -1;
00143
00144 for(int j = 0; j < dim; ++j) {
00145 CoordType new_span = max[j] - min[j];
00146 if(new_span > span) {
00147 span = new_span;
00148 direction = j;
00149 }
00150 }
00151
00152 assert("Have a direction of maximum size" && direction != -1);
00153
00154 Point<dim> center = Midpoint(*(min_p[direction]), *(max_p[direction]));
00155 CoordType dist = SloppyDistance(*(min_p[direction]), center);
00156
00157 for(i = c.begin(); i != end; ++i) {
00158 if(i == min_p[direction] || i == max_p[direction])
00159 continue;
00160
00161 CoordType new_dist = SloppyDistance(*i, center);
00162
00163 if(new_dist > dist) {
00164 CoordType delta_dist = (new_dist - dist) / 2;
00165
00166
00167 center += (*i - center) * delta_dist / new_dist;
00168 dist += delta_dist;
00169 assert("Shifted ball contains new point" &&
00170 SquaredDistance(*i, center) <= dist * dist);
00171 }
00172 }
00173
00174 center.setValid(valid);
00175
00176 return Ball<2>(center, dist);
00177 }
00178 #endif
00179
00180
00181
00182
00183 template<const int dim>
00184 inline Ball<dim> Point<dim>::boundingSphere() const
00185 {
00186 return Ball<dim>(*this, 0);
00187 }
00188
00189 template<const int dim>
00190 inline Ball<dim> Point<dim>::boundingSphereSloppy() const
00191 {
00192 return Ball<dim>(*this, 0);
00193 }
00194
00195 }
00196
00197 #endif // WFMATH_BALL_FUNCS_H