26 #include <tulip/Rectangle.h> 27 #include <tulip/Coord.h> 48 QuadTreeNode(
const tlp::Rectangle<float> &box) : _box(box) {
49 assert(_box.isValid());
51 for (
int i = 0; i < 4; ++i)
52 children[i] =
nullptr;
58 for (
int i = 0; i < 4; ++i)
59 if (children[i] !=
nullptr)
65 void insert(
const tlp::Rectangle<float> &box,
const TYPE
id) {
66 assert(box.isValid());
67 assert(_box.isValid());
73 Vec2f subBox((_box[0] + _box[1]) / 2.f);
75 if (!((subBox == _box[0]) || (subBox == _box[1]))) {
76 for (
int i = 0; i < 4; ++i) {
77 if (getChildBox(i).isInside(box)) {
78 QuadTreeNode *child = getChild(i);
81 child->insert(box,
id);
83 entities.push_back(
id);
90 entities.push_back(
id);
98 void getElements(
const tlp::Rectangle<float> &box, std::vector<TYPE> &result)
const {
99 assert(box.isValid());
100 assert(_box.isValid());
102 if (_box.intersect(box)) {
103 for (
size_t i = 0; i < entities.size(); ++i) {
104 result.push_back(entities[i]);
107 for (
unsigned int i = 0; i < 4; ++i) {
108 if (children[i] !=
nullptr)
109 children[i]->getElements(box, result);
117 void getElements(std::vector<TYPE> &result)
const {
118 for (
size_t i = 0; i < entities.size(); ++i) {
119 result.push_back(entities[i]);
122 for (
unsigned int i = 0; i < 4; ++i) {
123 if (children[i] !=
nullptr)
124 children[i]->getElements(result);
137 void getElementsWithRatio(
const tlp::Rectangle<float> &box, std::vector<TYPE> &result,
138 float ratio = 1000.)
const {
139 assert(_box.isValid());
140 assert(box.isValid());
142 if (_box.intersect(box)) {
143 float xRatio = (box[1][0] - box[0][0]) / (_box[1][0] - _box[0][0]);
144 float yRatio = (box[1][1] - box[0][1]) / (_box[1][1] - _box[0][1]);
147 if (xRatio < ratio || yRatio < ratio) {
148 for (
size_t i = 0; i < entities.size(); ++i) {
149 result.push_back(entities[i]);
152 for (
unsigned int i = 0; i < 4; ++i) {
153 if (children[i] !=
nullptr)
154 children[i]->getElementsWithRatio(box, result, ratio);
161 if (entities.size() > 0) {
162 result.push_back(entities[0]);
167 for (
unsigned int i = 0; i < 4; ++i) {
168 if (children[i] !=
nullptr && children[i]->_box.intersect(box)) {
171 children[i]->getElementsWithRatio(box, result, ratio);
182 QuadTreeNode *getChild(
int i) {
183 if (children[i] ==
nullptr) {
184 Rectangle<float> box(getChildBox(i));
186 if (box[0] == _box[0] && box[1] == _box[1])
189 children[i] =
new QuadTreeNode<TYPE>(box);
195 Rectangle<float> getChildBox(
int i) {
196 assert(_box.isValid());
208 I[0] = (_box[0][0] + _box[1][0]) / 2.;
212 E[1] = (_box[0][1] + _box[1][1]) / 2.;
225 return Rectangle<float>(_box[0], F);
229 return Rectangle<float>(I, G);
233 return Rectangle<float>(F, _box[1]);
237 return Rectangle<float>(E, H);
240 tlp::error() <<
"ERROR" << __PRETTY_FUNCTION__ << std::endl;
245 QuadTreeNode *children[4];
246 std::vector<TYPE> entities;
247 tlp::Rectangle<float> _box;