3
* Copyright (C) 2007 Guillaume Chereau
5
* This program is free software; you can redistribute it and/or
6
* modify it under the terms of the GNU General Public License
7
* as published by the Free Software Foundation; either version 2
8
* of the License, or (at your option) any later version.
10
* This program is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
* GNU General Public License for more details.
15
* You should have received a copy of the GNU General Public License
16
* along with this program; if not, write to the Free Software
17
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20
#ifndef _TREEGRID_HPP_
21
#define _TREEGRID_HPP_
23
//#define TREEGRIDDEBUG 1
31
TreeGridNode(const StelGeom::ConvexPolygon& s) : triangle(s) {}
33
typedef std::vector<GridObject*> Objects;
36
StelGeom::ConvexPolygon triangle;
38
typedef std::vector<TreeGridNode> Children;
42
double draw(class Projector *prj, const StelGeom::ConvexS&, float opacity = 1.) const;
46
class TreeGrid : public Grid, public TreeGridNode
49
TreeGrid(unsigned int maxobj = 1000);
52
void insert(GridObject* obj)
58
void filterIntersect(const Shape& s);
60
unsigned int depth() const
61
{ return depth(*this); }
63
//! Get all the objects loaded into the grid structure
64
//! This is quite slow and should not used for time critical operations
65
virtual std::vector<GridObject*> getAllObjects();
69
void insert(GridObject* obj, TreeGridNode& node);
70
void split(TreeGridNode& node);
73
void fillIntersect(const S& s, const TreeGridNode& node, Grid& grid) const;
75
void fillAll(const TreeGridNode& node, Grid& grid) const;
76
void fillAll(const TreeGridNode& node, std::vector<GridObject*>& result) const;
77
unsigned int depth(const TreeGridNode& node) const;
79
unsigned int maxObjects;
87
void TreeGrid::fillIntersect(const S& s, const TreeGridNode& node, Grid& grid) const
89
for (TreeGridNode::Objects::const_iterator io = node.objects.begin(); io != node.objects.end(); ++io)
91
if (intersect(s, (*io)->getPositionForGrid()))
93
grid.insertResult(*io);
96
for (Children::const_iterator ic = node.children.begin(); ic != node.children.end(); ++ic)
98
if (contains(s, ic->triangle))
104
if(intersect(s, ic->triangle))
106
fillIntersect(s, *ic, grid);
112
template<class Shape>
113
struct NotIntersectPred
117
NotIntersectPred(const Shape& s) : shape(s) {}
118
bool operator() (const GridObject* obj) const
120
return !intersect(shape, obj->getPositionForGrid());
124
template<class Shape>
125
void TreeGrid::filterIntersect(const Shape& s)
127
// first we remove all the objects that are not in the disk
128
// this->remove_if(NotIntersectPred<Shape>(s));
129
// // now we add all the objects that are in the disk, but not in the old disk
130
// fillIntersect(Difference<Shape, ConvexS>(s, filter), *this, *this);
132
fillIntersect(s, *this, *this);
134
//filter = ConvexS(s);
138
#endif // _TREEGRID_HPP_