core/vgl/algo/vgl_rtree_c.h
Go to the documentation of this file.
00001 // This is core/vgl/algo/vgl_rtree_c.h
00002 #ifndef vgl_rtree_c_h_
00003 #define vgl_rtree_c_h_
00004 //:
00005 // \file
00006 // \brief C helper classes for vgl_rtree
00007 // \author J.L. Mundy
00008 // \date November 14, 2008
00009 // \verbatim
00010 //  Modifications
00011 //   <None yet>
00012 // \endverbatim
00013 //
00014 // vgl_rtree stores elements of type V with regions described by
00015 // bounds type B. The C helper class implements the bounding predicates
00016 // between V and B. Thus V and B remain independent of each other.
00017 //
00018 #include <vgl/vgl_point_2d.h>
00019 #include <vgl/vgl_box_2d.h>
00020 #include <vgl/vgl_polygon.h>
00021 #include <vgl/vgl_intersection.h>
00022 template <class V, class B, class C> class vgl_rtree_probe;
00023 
00024 //: vgl_rtree Class C for V=vgl_point_2d<T>, B = vgl_box_2d<T>
00025 template <class T>
00026 class vgl_rtree_point_box_2d
00027 {
00028   // only static methods
00029   vgl_rtree_point_box_2d();
00030   ~vgl_rtree_point_box_2d();
00031 
00032  public:
00033   typedef vgl_point_2d<T> v_type;
00034   typedef vgl_box_2d<T> b_type;
00035   typedef T t_type;
00036   // Operations------
00037   static void  init  (vgl_box_2d<T>& b, vgl_point_2d<T> const& p)
00038   { b = vgl_box_2d<T>();  b.add(p); }
00039 
00040   static void  update(vgl_box_2d<T>& b, vgl_point_2d<T> const& p)
00041   { b.add(p); }
00042 
00043   static void  update(vgl_box_2d<T>& b0, vgl_box_2d<T> const &b1)
00044   { b0.add(b1.min_point());  b0.add(b1.max_point()); }
00045 
00046   static bool  meet(vgl_box_2d<T> const& b, vgl_point_2d<T> const& p)
00047   { return b.contains(p); }
00048 
00049   static bool  meet(vgl_box_2d<T> const& b0, vgl_box_2d<T> const& b1) {
00050     vgl_point_2d<T> b0min = b0.min_point();
00051     vgl_point_2d<T> b1min = b1.min_point();
00052     vgl_point_2d<T> b0max = b0.max_point();
00053     vgl_point_2d<T> b1max = b1.max_point();
00054     vgl_point_2d<T> max_of_mins(b0min.x() > b1min.x() ? b0min.x() : b1min.x(), b0min.y() > b1min.y() ? b0min.y() : b1min.y());
00055     vgl_point_2d<T> min_of_maxs(b0min.x() < b1min.x() ? b0min.x() : b1min.x(), b0min.y() < b1min.y() ? b0min.y() : b1min.y());
00056 
00057     return ( b0.contains(b1min) || b0.contains(b1max) ||
00058              b1.contains(b0min) || b1.contains(b0max) ||
00059              ( (b0.contains(max_of_mins) || b0.contains(min_of_maxs)) &&
00060                (b1.contains(max_of_mins) || b1.contains(min_of_maxs)) ) );
00061   }
00062 
00063   static float volume(vgl_box_2d<T> const& b)
00064   { return static_cast<float>(b.area()); }
00065 
00066   // point meets for a polygon, used by generic rtree probe
00067   static bool meets(vgl_point_2d<T> const& v, vgl_polygon<T> poly)
00068   { return poly.contains(v); }
00069 
00070   // box meets for a polygon, used by generic rtree probe
00071   static bool meets(vgl_box_2d<T> const& b, vgl_polygon<T> poly)
00072   { return vgl_intersection<T>(b, poly); }
00073 };
00074 
00075 
00076 //: vgl_rtree Class C for V=vgl_box_2d<T>, B = vgl_rbox_2d<T>
00077 //  Need to distinguish bounds type from stored element type,
00078 //  so create minimal subclass of vgl_box_2d
00079 template <class Type>
00080 class vgl_bbox_2d : public vgl_box_2d<Type>
00081 {
00082  public:
00083   //: Default constructor (creates empty box)
00084   vgl_bbox_2d() {}
00085 
00086   //: Construct using two corner points
00087   vgl_bbox_2d(Type const min_position[2],
00088               Type const max_position[2])
00089   : vgl_box_2d<Type>(min_position[2], max_position[2]) {}
00090 
00091   //: Construct using two corner points
00092   vgl_bbox_2d(vgl_point_2d<Type> const& min_pos,
00093               vgl_point_2d<Type> const& max_pos)
00094   : vgl_box_2d<Type>(min_pos, max_pos) {}
00095 
00096   //: Construct using ranges in \a x (first two args) and \a y (last two)
00097   vgl_bbox_2d(Type xmin, Type xmax, Type ymin, Type ymax)
00098   : vgl_box_2d<Type>(xmin, xmax, ymin, ymax) {}
00099 
00100   //: Equality test
00101   inline bool operator==(vgl_bbox_2d<Type> const& b) const {
00102     // All empty boxes are equal:
00103     if (b.is_empty()) return this->is_empty();
00104     return  this->min_x() == b.min_x() && this->min_y() == b.min_y()
00105          && this->max_x() == b.max_x() && this->max_y() == b.max_y();
00106   }
00107 };
00108 
00109 template <class T>
00110 class vgl_rtree_box_box_2d
00111 {
00112   // only static methods
00113   vgl_rtree_box_box_2d();
00114   ~vgl_rtree_box_box_2d();
00115 
00116  public:
00117   typedef vgl_box_2d<T> v_type;
00118   typedef vgl_bbox_2d<T> b_type;
00119   typedef T t_type;
00120   // Operations------
00121   static void  init  (vgl_bbox_2d<T>& b, vgl_box_2d<T> const& v)
00122   { b = vgl_bbox_2d<T>();  b.add(v.min_point()); b.add(v.max_point()); }
00123 
00124   static void  update(vgl_bbox_2d<T>& b, vgl_box_2d<T> const& v)
00125   { b.add(v.min_point()); b.add(v.max_point()); }
00126 
00127   static void  update(vgl_bbox_2d<T>& b0, vgl_bbox_2d<T> const &b1)
00128   { b0.add(b1.min_point());  b0.add(b1.max_point()); }
00129 
00130   static bool  meet(vgl_bbox_2d<T> const& b0, vgl_box_2d<T> const& v) {
00131     bool resultf =(b0.contains(v.min_point()) || b0.contains(v.max_point()));
00132     bool resultr =(v.contains(b0.min_point()) || v.contains(b0.max_point()));
00133     return resultf||resultr;
00134   }
00135 
00136   static bool  meet(vgl_bbox_2d<T> const& b0, vgl_bbox_2d<T> const& b1) {
00137     bool resultf =(b0.contains(b1.min_point()) || b0.contains(b1.max_point()));
00138     bool resultr =(b1.contains(b0.min_point()) || b1.contains(b0.max_point()));
00139     return resultf||resultr;
00140   }
00141 
00142   static float volume(vgl_box_2d<T> const& b)
00143   { return static_cast<float>(b.area()); }
00144 
00145   // box_2d meets for a polygon, used by generic rtree probe
00146   static bool meets(vgl_box_2d<T> const& b, vgl_polygon<T> poly)
00147   { return vgl_rtree_point_box_2d<T>::meets(b, poly); }
00148 
00149   static bool meets(vgl_bbox_2d<T> const& b, vgl_polygon<T> poly)
00150   { return vgl_rtree_point_box_2d<T>::meets(b, poly); }
00151 };
00152 
00153 template <class V, class B, class C>
00154 class vgl_rtree_polygon_probe : public vgl_rtree_probe<V, B, C>
00155 {
00156   typedef typename C::t_type T;
00157   vgl_polygon<T> poly_;
00158  public:
00159   vgl_rtree_polygon_probe(vgl_polygon<T> const& poly): poly_(poly) {}
00160 
00161   //: return true if the probe "meets" the given object.
00162   virtual bool meets(V const &v) const {return C::meets(v, poly_); }
00163   virtual bool meets(B const &b) const {return C::meets(b, poly_); }
00164 };
00165 
00166 #endif // vgl_rtree_c_h_