00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef _STELTREEGRID_HPP_
00021 #define _STELTREEGRID_HPP_
00022
00023
00024
00025 #include <vector>
00026 #include "StelGrid.hpp"
00027
00028 struct StelTreeGridNode
00029 {
00030 StelTreeGridNode() {}
00031 StelTreeGridNode(const StelGeom::ConvexPolygon& s) : triangle(s) {}
00032
00033 typedef std::vector<StelGridObject*> Objects;
00034 Objects objects;
00035
00036 StelGeom::ConvexPolygon triangle;
00037
00038 typedef std::vector<StelTreeGridNode> Children;
00039 Children children;
00040
00041 #ifdef STELTREEGRIDDEBUG
00042 double draw(class StelProjector *prj, const StelGeom::ConvexS&, float opacity = 1.) const;
00043 #endif
00044 };
00045
00046 class StelTreeGrid : public StelGrid, public StelTreeGridNode
00047 {
00048 public:
00049 StelTreeGrid(unsigned int maxobj = 1000);
00050 virtual ~StelTreeGrid();
00051
00052 void insert(StelGridObject* obj)
00053 {
00054 insert(obj, *this);
00055 }
00056
00057 template<class Shape>
00058 void filterIntersect(const Shape& s);
00059
00060 unsigned int depth() const
00061 { return depth(*this); }
00062
00065 virtual std::vector<StelGridObject*> getAllObjects();
00066
00067 private:
00068
00069 void insert(StelGridObject* obj, StelTreeGridNode& node);
00070 void split(StelTreeGridNode& node);
00071
00072 template<class S>
00073 void fillIntersect(const S& s, const StelTreeGridNode& node, StelGrid& grid) const;
00074
00075 void fillAll(const StelTreeGridNode& node, StelGrid& grid) const;
00076 void fillAll(const StelTreeGridNode& node, std::vector<StelGridObject*>& result) const;
00077 unsigned int depth(const StelTreeGridNode& node) const;
00078
00079 unsigned int maxObjects;
00080
00081
00082 ConvexS filter;
00083 };
00084
00085
00086 template<class S>
00087 void StelTreeGrid::fillIntersect(const S& s, const StelTreeGridNode& node, StelGrid& grid) const
00088 {
00089 for (StelTreeGridNode::Objects::const_iterator io = node.objects.begin(); io != node.objects.end(); ++io)
00090 {
00091 if (intersect(s, (*io)->getPositionForGrid()))
00092 {
00093 grid.insertResult(*io);
00094 }
00095 }
00096 for (Children::const_iterator ic = node.children.begin(); ic != node.children.end(); ++ic)
00097 {
00098 if (contains(s, ic->triangle))
00099 {
00100 fillAll(*ic, grid);
00101 }
00102 else
00103 {
00104 if(intersect(s, ic->triangle))
00105 {
00106 fillIntersect(s, *ic, grid);
00107 }
00108 }
00109 }
00110 }
00111
00112 template<class Shape>
00113 struct NotIntersectPred
00114 {
00115 Shape shape;
00116
00117 NotIntersectPred(const Shape& s) : shape(s) {}
00118 bool operator() (const StelGridObject* obj) const
00119 {
00120 return !intersect(shape, obj->getPositionForGrid());
00121 }
00122 };
00123
00124 template<class Shape>
00125 void StelTreeGrid::filterIntersect(const Shape& s)
00126 {
00127
00128
00129
00130
00131 this->clear();
00132 fillIntersect(s, *this, *this);
00133
00134
00135 }
00136
00137
00138 #endif // _STELTREEGRID_HPP_
00139
00140