00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 # ifndef shape_boundingbox_hpp
00014 # define shape_boundingbox_hpp
00015
00016 # include <iostream>
00017 # include <shape/shape.hpp>
00018 # include <shape/edge.hpp>
00019
00020 # define TMPL template<class C, class V>
00021 # define STMPL template<>
00022 # define SELF bounding_box<C,V>
00023
00024 namespace mmx {
00025 namespace shape {
00026
00027 TMPL class bounding_box;
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 struct bounding_box_def {};
00039
00040 template<> struct use<bounding_box_def> {
00041 typedef bounding_box<double,default_env> BoundingBox;
00042 };
00043
00044 template<class C, class V=default_env>
00045 class bounding_box : public use<shape_def,C,V>::Shape {
00046
00047 public:
00048 bounding_box(void) ;
00049 bounding_box(double xmin, double xmax) ;
00050 bounding_box(double xmin, double xmax, double ymin, double ymax) ;
00051 bounding_box(double xmin, double xmax, double ymin, double ymax, double zmin, double zmax) ;
00052 bounding_box(const SELF&) ;
00053 ~bounding_box(void) {};
00054
00055 inline double xmin(void) { return m_xmin ; }
00056 inline double xmax(void) { return m_xmax ; }
00057 inline double ymin(void) { return m_ymin ; }
00058 inline double ymax(void) { return m_ymax ; }
00059 inline double zmin(void) { return m_zmin ; }
00060 inline double zmax(void) { return m_zmax ; }
00061
00062 inline double xmin(void) const { return m_xmin ; }
00063 inline double xmax(void) const { return m_xmax ; }
00064 inline double ymin(void) const { return m_ymin ; }
00065 inline double ymax(void) const { return m_ymax ; }
00066 inline double zmin(void) const { return m_zmin ; }
00067 inline double zmax(void) const { return m_zmax ; }
00068
00069 inline double xsize(void) const { return m_xmax-m_xmin ; }
00070 inline double ysize(void) const { return m_ymax-m_ymin ; }
00071 inline double zsize(void) const { return m_zmax-m_zmin ; }
00072
00073 inline void set_xmin(double x) { this->m_xmin = x ; }
00074 inline void set_xmax(double x) { this->m_xmax = x ; }
00075 inline void set_ymin(double y) { this->m_ymin = y ; }
00076 inline void set_ymax(double y) { this->m_ymax = y ; }
00077 inline void set_zmin(double z) { this->m_zmin = z ; }
00078 inline void set_zmax(double z) { this->m_zmax = z ; }
00079
00080 inline bool is0D(void) const { return ((m_xmin == m_xmax) && (m_ymin == m_ymax) && (m_zmin == m_zmax)) ; }
00081 inline bool is1D(void) const { return ((m_xmin != m_xmax) && (m_ymin == m_ymax) && (m_zmin == m_zmax)) ; }
00082 inline bool is2D(void) const { return ((m_xmin != m_xmax) && (m_ymin != m_ymax) && (m_zmin == m_zmax)) ; }
00083 inline bool is3d(void) const { return ((m_xmin != m_xmax) && (m_ymin != m_ymax) && (m_zmin != m_zmax)) ; }
00084
00085 double operator()(unsigned v, unsigned s) const;
00086 double& operator()(unsigned v, unsigned s);
00087
00088 double size(void) ;
00089
00090 bool contains(double x, bool strict = false) ;
00091 bool contains(double x, double y, bool strict = false) ;
00092 bool contains(double x, double y, double z, bool strict = false) ;
00093
00094 bool intersects(SELF * other, bool strict = true) ;
00095 bool unites(SELF * other, bool strict = true) ;
00096
00097 void intersected(SELF * other) ;
00098 void united(SELF * other) ;
00099
00100 SELF * intersect(const SELF& other) ;
00101 SELF * unite(SELF * other) ;
00102
00103 inline SELF * operator * (const SELF& other) { return intersect(other) ; }
00104 inline SELF * operator + (const SELF& other) { return unite(other) ; }
00105
00106 protected:
00107 double m_xmin, m_xmax ;
00108 double m_ymin, m_ymax ;
00109 double m_zmin, m_zmax ;
00110 } ;
00111
00112 TMPL inline double
00113 lower(const SELF& bx, int v) {
00114 switch(v) {
00115 case 0:
00116 return bx.xmin(); break ;
00117 case 1:
00118 return bx.ymin(); break ;
00119 default:
00120 return bx.zmin(); break ;
00121 }
00122 }
00123
00124 TMPL inline double
00125 upper(const SELF& bx, int v) {
00126 switch(v) {
00127 case 0:
00128 return bx.xmax(); break ;
00129 case 1:
00130 return bx.ymax(); break ;
00131 default:
00132 return bx.zmax(); break ;
00133 }
00134 }
00135
00136
00137 inline double mmxmin(double a, double b)
00138 {
00139 return (a <= b) ? a : b ;
00140 }
00141
00142 inline double mmxmax(double a, double b)
00143 {
00144 return (a >= b) ? a : b ;
00145 }
00146
00147 TMPL SELF::bounding_box(void)
00148 {
00149 this->m_xmin = 0.0 ;
00150 this->m_xmax = 1.0 ;
00151 this->m_ymin = 0.0 ;
00152 this->m_ymax = 1.0 ;
00153 this->m_zmin = 0.0 ;
00154 this->m_zmax = 1.0 ;
00155 }
00156
00157 TMPL SELF::bounding_box(double xmin, double xmax)
00158 {
00159 this->m_xmin = xmin ;
00160 this->m_xmax = xmax ;
00161 this->m_ymin = 0.0 ;
00162 this->m_ymax = 0.0 ;
00163 this->m_zmin = 0.0 ;
00164 this->m_zmax = 0.0 ;
00165 }
00166
00167 TMPL SELF::bounding_box(double xmin, double xmax, double ymin, double ymax)
00168 {
00169 this->m_xmin = xmin ;
00170 this->m_xmax = xmax ;
00171 this->m_ymin = ymin ;
00172 this->m_ymax = ymax ;
00173 this->m_zmin = 0.0 ;
00174 this->m_zmax = 0.0 ;
00175 }
00176
00177 TMPL SELF::bounding_box(double xmin, double xmax, double ymin, double ymax, double zmin, double zmax)
00178 {
00179 this->m_xmin = xmin ;
00180 this->m_xmax = xmax ;
00181 this->m_ymin = ymin ;
00182 this->m_ymax = ymax ;
00183 this->m_zmin = zmin ;
00184 this->m_zmax = zmax ;
00185 }
00186
00187 TMPL SELF::bounding_box(const SELF& bx)
00188 {
00189 m_xmin = bx.xmin() ;
00190 m_xmax = bx.xmax() ;
00191 m_ymin = bx.ymin() ;
00192 m_ymax = bx.ymax() ;
00193 m_zmin = bx.zmin() ;
00194 m_zmax = bx.zmax() ;
00195 }
00196
00197
00198 TMPL double
00199 SELF::size(void)
00200 {
00201
00202 return std::max(m_xmax-m_xmin, std::max(m_ymax-m_ymin, m_zmax-m_zmin)) ;
00203 }
00204
00205 TMPL bool
00206 SELF::contains(double x, bool strict)
00207 {
00208 if(!strict)
00209 return (((m_xmin <= x) && (x <= m_xmax))) ;
00210 else
00211 return (((m_xmin < x) && (x < m_xmax))) ;
00212 }
00213
00214 TMPL bool
00215 SELF::contains(double x, double y, bool strict)
00216 {
00217 if(!strict)
00218 return (((m_xmin <= x) && (x <= m_xmax))
00219 && ((m_ymin <= y) && (y <= m_ymax))) ;
00220 else
00221 return (((m_xmin < x) && (x < m_xmax))
00222 && ((m_ymin < y) && (y < m_ymax))) ;
00223 }
00224
00225 TMPL bool
00226 SELF::contains(double x, double y, double z, bool strict)
00227 {
00228 if(!strict)
00229 return (((m_xmin <= x) && (x <= m_xmax))
00230 && ((m_ymin <= y) && (y <= m_ymax))
00231 && ((m_zmin <= z) && (z <= m_zmax))) ;
00232 else
00233 return (((m_xmin < x) && (x < m_xmax))
00234 && ((m_ymin < y) && (y < m_ymax))
00235 && ((m_zmin < z) && (z < m_zmax))) ;
00236 }
00237
00238 TMPL bool
00239 SELF::intersects(SELF * other, bool strict)
00240 {
00241 if(this->is0D())
00242 return (this->xmin() == other->xmin()) ;
00243 else if(this->is1D())
00244 if(strict)
00245 return ((mmxmax(this->xmin(), other->xmin()) < mmxmin(this->xmax(), other->xmax()))) ;
00246 else
00247 return ((mmxmax(this->xmin(), other->xmin()) <= mmxmin(this->xmax(), other->xmax()))) ;
00248 else if(this->is2D())
00249 if(strict)
00250 return ((mmxmax(this->xmin(), other->xmin()) < mmxmin(this->xmax(), other->xmax())) &&
00251 (mmxmax(this->ymin(), other->ymin()) < mmxmin(this->ymax(), other->ymax()))) ;
00252 else
00253 return ((mmxmax(this->xmin(), other->xmin()) <= mmxmin(this->xmax(), other->xmax())) &&
00254 (mmxmax(this->ymin(), other->ymin()) <= mmxmin(this->ymax(), other->ymax()))) ;
00255 else if(this->is3d()) {
00256 if(strict)
00257 return ((mmxmax(this->xmin(), other->xmin()) < mmxmin(this->xmax(), other->xmax())) &&
00258 (mmxmax(this->ymin(), other->ymin()) < mmxmin(this->ymax(), other->ymax())) &&
00259 (mmxmax(this->zmin(), other->zmin()) < mmxmin(this->zmax(), other->zmax()))) ;
00260 else
00261 return ((mmxmax(this->xmin(), other->xmin()) <= mmxmin(this->xmax(), other->xmax())) &&
00262 (mmxmax(this->ymin(), other->ymin()) <= mmxmin(this->ymax(), other->ymax())) &&
00263 (mmxmax(this->zmin(), other->zmin()) <= mmxmin(this->zmax(), other->zmax()))) ;
00264 }
00265 return false ;
00266 }
00267
00268 TMPL bool
00269 SELF::unites(SELF * other, bool strict)
00270 {
00271 if(this->is0D())
00272 return (this->xmin() == other->xmin()) ;
00273 else if(this->is1D()) {
00274 if(strict)
00275 return ((mmxmin(this->xmin(), other->xmin()) < mmxmax(this->xmax(), other->xmax()))) ;
00276 else
00277 return ((mmxmin(this->xmin(), other->xmin()) <= mmxmax(this->xmax(), other->xmax()))) ;
00278 } else if(this->is2D()) {
00279 if(strict)
00280 return ((mmxmin(this->xmin(), other->xmin()) < mmxmax(this->xmax(), other->xmax())) &&
00281 (mmxmin(this->ymin(), other->ymin()) < mmxmax(this->ymax(), other->ymax()))) ;
00282 else
00283 return ((mmxmin(this->xmin(), other->xmin()) <= mmxmax(this->xmax(), other->xmax())) &&
00284 (mmxmin(this->ymin(), other->ymin()) <= mmxmax(this->ymax(), other->ymax()))) ;
00285 } else if(this->is3d()) {
00286 if(strict)
00287 return ((mmxmin(this->xmin(), other->xmin()) < mmxmax(this->xmax(), other->xmax())) &&
00288 (mmxmin(this->ymin(), other->ymin()) < mmxmax(this->ymax(), other->ymax())) &&
00289 (mmxmin(this->zmin(), other->zmin()) < mmxmax(this->zmax(), other->zmax()))) ;
00290 else
00291 return ((mmxmin(this->xmin(), other->xmin()) <= mmxmax(this->xmax(), other->xmax())) &&
00292 (mmxmin(this->ymin(), other->ymin()) <= mmxmax(this->ymax(), other->ymax())) &&
00293 (mmxmin(this->zmin(), other->zmin()) <= mmxmax(this->zmax(), other->zmax()))) ;
00294 }
00295 return false ;
00296 }
00297
00298 TMPL void
00299 SELF::intersected(SELF * other) {
00300 set_xmin(mmxmax(this->xmin(), other->xmin())) ;
00301 set_xmax(mmxmin(this->xmax(), other->xmax())) ;
00302 set_ymin(mmxmax(this->ymin(), other->ymin())) ;
00303 set_ymax(mmxmin(this->ymax(), other->ymax())) ;
00304 set_zmin(mmxmax(this->zmin(), other->zmin())) ;
00305 set_zmax(mmxmin(this->zmax(), other->zmax())) ;
00306 }
00307
00308 TMPL void
00309 SELF::united(SELF * other) {
00310 set_xmin(mmxmin(this->xmin(), other->xmin())) ;
00311 set_xmax(mmxmax(this->xmax(), other->xmax())) ;
00312 set_ymin(mmxmin(this->ymin(), other->ymin())) ;
00313 set_ymax(mmxmax(this->ymax(), other->ymax())) ;
00314 set_zmin(mmxmin(this->zmin(), other->zmin())) ;
00315 set_zmax(mmxmax(this->zmax(), other->zmax())) ;
00316 }
00317
00318 TMPL SELF*
00319 SELF::intersect(const SELF& other) {
00320 SELF * bcell = new SELF ;
00321 bcell->set_xmin(mmxmax(this->xmin(), other.xmin())) ;
00322 bcell->set_xmax(mmxmin(this->xmax(), other.xmax())) ;
00323 bcell->set_ymin(mmxmax(this->ymin(), other.ymin())) ;
00324 bcell->set_ymax(mmxmin(this->ymax(), other.ymax())) ;
00325 bcell->set_zmin(mmxmax(this->zmin(), other.zmin())) ;
00326 bcell->set_zmax(mmxmin(this->zmax(), other.zmax())) ;
00327 return bcell ;
00328 }
00329
00330 TMPL SELF *
00331 SELF::unite(SELF * other) {
00332 SELF * bcell = new SELF ;
00333 bcell->set_xmin(mmxmin(this->xmin(), other->xmin())) ;
00334 bcell->set_xmax(mmxmax(this->xmax(), other->xmax())) ;
00335 bcell->set_ymin(mmxmin(this->ymin(), other->ymin())) ;
00336 bcell->set_ymax(mmxmax(this->ymax(), other->ymax())) ;
00337 bcell->set_zmin(mmxmin(this->zmin(), other->zmin())) ;
00338 bcell->set_zmax(mmxmax(this->zmax(), other->zmax())) ;
00339 return bcell ;
00340 }
00341
00342 TMPL double
00343 SELF::operator()(unsigned v, unsigned s) const {
00344 switch(v) {
00345 case 0:
00346 if(s==0) return xmin(); else return xmax();
00347 case 1:
00348 if(s==0) return ymin(); else return ymax();
00349 default:
00350 if(s==0) return zmin(); else return zmax();
00351 }
00352
00353 }
00354
00355 TMPL double&
00356 SELF::operator()(unsigned v, unsigned s) {
00357 switch(v) {
00358 case 0:
00359 if(s==0) return m_xmin; else return m_xmax;
00360 case 1:
00361 if(s==0) return m_ymin; else return m_ymax;
00362 default:
00363 if(s==0) return m_zmin; else return m_zmax;
00364 }
00365
00366 }
00367
00368 TMPL std::ostream&
00369 operator << (std::ostream& stream, const SELF & c) {
00370 if(c.is0D())
00371 return stream << "[]" ;
00372 else if(c.is1D())
00373 return stream << "[" << c.xmin() << ", " << c.xmax() << "]" ;
00374 else if(c.is2D())
00375 return stream << "[" << c.xmin() << ", " << c.xmax() << "] x [" << c.ymin() << ", " << c.ymax() << "]" ;
00376 else if(c.is3d())
00377 return stream << "[" << c.xmin() << ", " << c.xmax() << "] x [" << c.ymin() << ", " << c.ymax() << "] x [" << c.zmin() << ", " << c.zmax() << "]" ;
00378 else
00379 return stream << "???" ;
00380 }
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398 template<class C, class V, class T> void
00399 insert_bbx(T* t,SELF* bx) {
00400 typedef typename T::Point Point;
00401 typedef typename T::Edge Edge;
00402 Point
00403 *p0= new Point(bx->xmin(),bx->ymin(),bx->zmin()),
00404 *p1= new Point(bx->xmin(),bx->ymax(),bx->zmin()),
00405 *p2= new Point(bx->xmax(),bx->ymax(),bx->zmin()),
00406 *p3= new Point(bx->xmax(),bx->ymin(),bx->zmin());
00407 t->insert(p0);t->insert(p1); t->insert(new Edge(p0,p1));
00408 t->insert(p1);t->insert(p2); t->insert(new Edge(p1,p2));
00409 t->insert(p2);t->insert(p3); t->insert(new Edge(p2,p3));
00410 t->insert(p3);t->insert(p0); t->insert(new Edge(p3,p0));
00411
00412 Point
00413 *q0= new Point(bx->xmin(),bx->ymin(),bx->zmax()),
00414 *q1= new Point(bx->xmin(),bx->ymax(),bx->zmax()),
00415 *q2= new Point(bx->xmax(),bx->ymax(),bx->zmax()),
00416 *q3= new Point(bx->xmax(),bx->ymin(),bx->zmax());
00417 t->insert(q0);t->insert(q1); t->insert(new Edge(q0,q1));
00418 t->insert(q1);t->insert(q2); t->insert(new Edge(q1,q2));
00419 t->insert(q2);t->insert(q3); t->insert(new Edge(q2,q3));
00420 t->insert(q3);t->insert(q0); t->insert(new Edge(q3,q0));
00421
00422 t->insert(p0);t->insert(q0);t->insert(new Edge(p0,q0));
00423 t->insert(p1);t->insert(q1);t->insert(new Edge(p1,q1));
00424 t->insert(p2);t->insert(q2);t->insert(new Edge(p2,q2));
00425 t->insert(p3);t->insert(q3);t->insert(new Edge(p3,q3));
00426 }
00427
00428
00429
00430 template<class C, class V, class T> void
00431 insert_bbx(T* t,SELF* bx, int v, int s) {
00432 typedef typename T::Point Point;
00433 typedef typename T::Edge Edge;
00434
00435 Point
00436 *p0= new Point(bx->xmin(),bx->ymin(),bx->zmin()),
00437 *p1= new Point(bx->xmin(),bx->ymax(),bx->zmin()),
00438 *p2= new Point(bx->xmax(),bx->ymax(),bx->zmin()),
00439 *p3= new Point(bx->xmax(),bx->ymin(),bx->zmin());
00440 Point
00441 *q0= new Point(bx->xmin(),bx->ymin(),bx->zmax()),
00442 *q1= new Point(bx->xmin(),bx->ymax(),bx->zmax()),
00443 *q2= new Point(bx->xmax(),bx->ymax(),bx->zmax()),
00444 *q3= new Point(bx->xmax(),bx->ymin(),bx->zmax());
00445
00446 if(v==2) {
00447 if(s==0) {
00448 t->insert(p0);t->insert(p1); t->insert(new Edge(p0,p1));
00449 t->insert(p1);t->insert(p2); t->insert(new Edge(p1,p2));
00450 t->insert(p2);t->insert(p3); t->insert(new Edge(p2,p3));
00451 t->insert(p3);t->insert(p0); t->insert(new Edge(p3,p0));
00452 } else {
00453 t->insert(q0);t->insert(q1); t->insert(new Edge(q0,q1));
00454 t->insert(q1);t->insert(q2); t->insert(new Edge(q1,q2));
00455 t->insert(q2);t->insert(q3); t->insert(new Edge(q2,q3));
00456 t->insert(q3);t->insert(q0); t->insert(new Edge(q3,q0));
00457 }
00458 } else if(v==1) {
00459 if(s==0) {
00460 t->insert(p0);t->insert(q0);t->insert(new Edge(p0,q0));
00461 t->insert(q0);t->insert(q3);t->insert(new Edge(q0,q3));
00462 t->insert(q3);t->insert(p3);t->insert(new Edge(q3,p3));
00463 t->insert(p3);t->insert(p0);t->insert(new Edge(p3,p0));
00464 } else {
00465 t->insert(p1);t->insert(q1);t->insert(new Edge(p1,q1));
00466 t->insert(q1);t->insert(q2);t->insert(new Edge(q1,q2));
00467 t->insert(q2);t->insert(p2);t->insert(new Edge(q2,p2));
00468 t->insert(p2);t->insert(p1);t->insert(new Edge(p2,p1));
00469 }
00470 } else if (v==0) {
00471 if(s==0) {
00472 t->insert(p0);t->insert(q0);t->insert(new Edge(p0,q0));
00473 t->insert(q0);t->insert(q1);t->insert(new Edge(q0,q1));
00474 t->insert(q1);t->insert(p1);t->insert(new Edge(p1,q1));
00475 t->insert(p1);t->insert(p0);t->insert(new Edge(p1,p0));
00476 } else {
00477 t->insert(p2);t->insert(q2);t->insert(new Edge(p2,q2));
00478 t->insert(q2);t->insert(q3);t->insert(new Edge(q2,q3));
00479 t->insert(q3);t->insert(p3);t->insert(new Edge(p3,q3));
00480 t->insert(p3);t->insert(p2);t->insert(new Edge(p3,p2));
00481 }
00482 }
00483 }
00484
00485
00486
00487 } ;
00488 } ;
00489 # undef TMPL
00490 # undef SELF
00491 # endif // shape_bounding_box_hpp
