File indexing completed on 2024-09-15 11:46:13
0001 /************************************************************************************* 0002 * Copyright (C) 2012 by Percy Camilo T. Aucahuasi <percy.camilo.ta@gmail.com> * 0003 * * 0004 * This program is free software; you can redistribute it and/or * 0005 * modify it under the terms of the GNU General Public License * 0006 * as published by the Free Software Foundation; either version 2 * 0007 * of the License, or (at your option) any later version. * 0008 * * 0009 * This program is distributed in the hope that it will be useful, * 0010 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 0011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 0012 * GNU General Public License for more details. * 0013 * * 0014 * You should have received a copy of the GNU General Public License * 0015 * along with this program; if not, write to the Free Software * 0016 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA * 0017 *************************************************************************************/ 0018 0019 #include "quadtree.h" 0020 0021 0022 Square::Square(double x, double y, double hEdge) 0023 : QRectF(QPointF(x-hEdge, y-hEdge), QPointF(x+hEdge, y+hEdge)) 0024 { 0025 0026 } 0027 0028 Square::Square(const QPointF& c, double hEdge) 0029 : QRectF(QPointF(c.x()-hEdge, c.y()-hEdge), QPointF(c.x()+hEdge, c.y()+hEdge)) 0030 { } 0031 0032 void Square::setCeter(const QPointF& c) 0033 { 0034 QSizeF s=size(); 0035 double he = halfEdge(); 0036 0037 setTopLeft(QPointF(c.x()-he, c.y()-he)); 0038 setSize(s); 0039 } 0040 0041 void Square::setCenter(double x, double y) 0042 { 0043 QSizeF s=size(); 0044 double he = halfEdge(); 0045 0046 setTopLeft(QPointF(x-he, y-he)); 0047 setSize(s); 0048 } 0049 0050 double Square::halfEdge() const 0051 { 0052 return width()*0.5; 0053 } 0054 0055 0056 void Square::setHalfEdge(double he) 0057 { 0058 QPointF c = center(); 0059 0060 setTopLeft(QPointF(c.x()-he, c.y()-he)); 0061 setBottomRight(QPointF(c.x()+he, c.y()+he)); 0062 } 0063 0064 0065 0066 Quadtree::Quadtree(double largo_mundo) { 0067 root = new QNode; 0068 0069 root->cubo.setCenter(largo_mundo/2,largo_mundo/2); 0070 0071 root->cubo.setHalfEdge(largo_mundo/2); 0072 for(unsigned int i=0; i<8; i++) { 0073 root->nodos[i]=nullptr; 0074 } 0075 } 0076 0077 Quadtree::Quadtree(const Square &cubo) { 0078 root = new QNode; 0079 root->cubo = cubo; 0080 for(unsigned int i=0; i<8; i++) { 0081 root->nodos[i]=nullptr; 0082 } 0083 } 0084 Quadtree::~Quadtree() { 0085 borrar_rec(root); 0086 } 0087 0088 void Quadtree::inicializar_nodos(QNode* padre) 0089 { 0090 double hhedge = padre->cubo.halfEdge()/2; 0091 0092 for(unsigned int i=0; i<4; i++) { 0093 padre->nodos[i] = new QNode; 0094 padre->nodos[i]->cubo.setHalfEdge(hhedge); 0095 for(unsigned int j=0; j<4; j++) { 0096 padre->nodos[i]->nodos[j]=nullptr; 0097 } 0098 } 0099 0100 double x = padre->cubo.center().x(); 0101 double y = padre->cubo.center().y(); 0102 padre->nodos[0]->cubo.setCenter(x-hhedge, y-hhedge); 0103 padre->nodos[1]->cubo.setCenter(x-hhedge, y+hhedge); 0104 padre->nodos[2]->cubo.setCenter(x+hhedge, y-hhedge); 0105 padre->nodos[3]->cubo.setCenter(x+hhedge, y+hhedge); 0106 } 0107 0108 void Quadtree::borrar_rec(QNode* nodo) { 0109 if(nodo == nullptr) { 0110 return; 0111 } 0112 for(unsigned int i=0; i<4; i++) { 0113 borrar_rec(nodo->nodos[i]); 0114 } 0115 delete nodo; 0116 } 0117 0118 0119 void Quadtree::crear_rec(QNode* nodo, unsigned int nivel_actual, unsigned int nivel_max) { 0120 if(nivel_actual > nivel_max) { 0121 return; 0122 } 0123 inicializar_nodos(nodo); 0124 for(unsigned int i=0; i<4; i++) { 0125 crear_rec(nodo->nodos[i],nivel_actual+1,nivel_max); 0126 } 0127 } 0128 0129 QNode* Quadtree::get_raiz() { 0130 return root; 0131 } 0132 0133 void Quadtree::crearNivel(unsigned int nivel) { 0134 crear_rec(root,0,nivel); 0135 } 0136 0137 void Quadtree::bajarNivel(QNode* nodo) { 0138 inicializar_nodos(nodo); 0139 } 0140 0141 void Quadtree::borrarHijos(QNode* padre) { 0142 for(unsigned int i=0; i<4; i++) { 0143 borrar_rec(padre->nodos[i]); 0144 padre->nodos[i] = nullptr; 0145 } 0146 }