1 /*************************************************************************************
2 * Copyright (C) 2012 by Percy Camilo T. Aucahuasi <percy.camilo.ta@gmail.com> *
3 * *
4 * This program is free software; you can redistribute it and/or *
5 * modify it under the terms of the GNU General Public License *
6 * as published by the Free Software Foundation; either version 2 *
7 * of the License, or (at your option) any later version. *
8 * *
9 * This program is distributed in the hope that it will be useful, *
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
12 * GNU General Public License for more details. *
13 * *
14 * You should have received a copy of the GNU General Public License *
15 * along with this program; if not, write to the Free Software *
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
17 *************************************************************************************/
18
19 #include "quadtree.h"
20
21
Square(double x,double y,double hEdge)22 Square::Square(double x, double y, double hEdge)
23 : QRectF(QPointF(x-hEdge, y-hEdge), QPointF(x+hEdge, y+hEdge))
24 {
25
26 }
27
Square(const QPointF & c,double hEdge)28 Square::Square(const QPointF& c, double hEdge)
29 : QRectF(QPointF(c.x()-hEdge, c.y()-hEdge), QPointF(c.x()+hEdge, c.y()+hEdge))
30 { }
31
setCeter(const QPointF & c)32 void Square::setCeter(const QPointF& c)
33 {
34 QSizeF s=size();
35 double he = halfEdge();
36
37 setTopLeft(QPointF(c.x()-he, c.y()-he));
38 setSize(s);
39 }
40
setCenter(double x,double y)41 void Square::setCenter(double x, double y)
42 {
43 QSizeF s=size();
44 double he = halfEdge();
45
46 setTopLeft(QPointF(x-he, y-he));
47 setSize(s);
48 }
49
halfEdge() const50 double Square::halfEdge() const
51 {
52 return width()*0.5;
53 }
54
55
setHalfEdge(double he)56 void Square::setHalfEdge(double he)
57 {
58 QPointF c = center();
59
60 setTopLeft(QPointF(c.x()-he, c.y()-he));
61 setBottomRight(QPointF(c.x()+he, c.y()+he));
62 }
63
64
65
Quadtree(double largo_mundo)66 Quadtree::Quadtree(double largo_mundo) {
67 root = new QNode;
68
69 root->cubo.setCenter(largo_mundo/2,largo_mundo/2);
70
71 root->cubo.setHalfEdge(largo_mundo/2);
72 for(unsigned int i=0; i<8; i++) {
73 root->nodos[i]=nullptr;
74 }
75 }
76
Quadtree(const Square & cubo)77 Quadtree::Quadtree(const Square &cubo) {
78 root = new QNode;
79 root->cubo = cubo;
80 for(unsigned int i=0; i<8; i++) {
81 root->nodos[i]=nullptr;
82 }
83 }
~Quadtree()84 Quadtree::~Quadtree() {
85 borrar_rec(root);
86 }
87
inicializar_nodos(QNode * padre)88 void Quadtree::inicializar_nodos(QNode* padre)
89 {
90 double hhedge = padre->cubo.halfEdge()/2;
91
92 for(unsigned int i=0; i<4; i++) {
93 padre->nodos[i] = new QNode;
94 padre->nodos[i]->cubo.setHalfEdge(hhedge);
95 for(unsigned int j=0; j<4; j++) {
96 padre->nodos[i]->nodos[j]=nullptr;
97 }
98 }
99
100 double x = padre->cubo.center().x();
101 double y = padre->cubo.center().y();
102 padre->nodos[0]->cubo.setCenter(x-hhedge, y-hhedge);
103 padre->nodos[1]->cubo.setCenter(x-hhedge, y+hhedge);
104 padre->nodos[2]->cubo.setCenter(x+hhedge, y-hhedge);
105 padre->nodos[3]->cubo.setCenter(x+hhedge, y+hhedge);
106 }
107
borrar_rec(QNode * nodo)108 void Quadtree::borrar_rec(QNode* nodo) {
109 if(nodo == nullptr) {
110 return;
111 }
112 for(unsigned int i=0; i<4; i++) {
113 borrar_rec(nodo->nodos[i]);
114 }
115 delete nodo;
116 }
117
118
crear_rec(QNode * nodo,unsigned int nivel_actual,unsigned int nivel_max)119 void Quadtree::crear_rec(QNode* nodo, unsigned int nivel_actual, unsigned int nivel_max) {
120 if(nivel_actual > nivel_max) {
121 return;
122 }
123 inicializar_nodos(nodo);
124 for(unsigned int i=0; i<4; i++) {
125 crear_rec(nodo->nodos[i],nivel_actual+1,nivel_max);
126 }
127 }
128
get_raiz()129 QNode* Quadtree::get_raiz() {
130 return root;
131 }
132
crearNivel(unsigned int nivel)133 void Quadtree::crearNivel(unsigned int nivel) {
134 crear_rec(root,0,nivel);
135 }
136
bajarNivel(QNode * nodo)137 void Quadtree::bajarNivel(QNode* nodo) {
138 inicializar_nodos(nodo);
139 }
140
borrarHijos(QNode * padre)141 void Quadtree::borrarHijos(QNode* padre) {
142 for(unsigned int i=0; i<4; i++) {
143 borrar_rec(padre->nodos[i]);
144 padre->nodos[i] = nullptr;
145 }
146 }
147