四叉树

  1 #include <cmath> 
  2 #include <vector>
  3 #include <iostream>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 const int NUME_PLANETS = 10;//星球数量
  9 const int TIME_COUNT = 20;
 10 const int BORDER_LIMIT = 3200;//所有坐标绝对值都不超过3200
 11 
 12 const double G = 1e-3;//万有引力常量
 13 const double pi = acos(-1.0);//圆周率
 14 
 15 double sqr(double x) {//平方
 16     return x * x;
 17 };
 18 
 19 //二维向量
 20 class Vector {
 21 public:
 22     double x, y;
 23 
 24     Vector():x(0), y(0){}
 25     Vector(double x, double y):x(x), y(y){}
 26     ~Vector() {}
 27 
 28     void operator = (const Vector &v) {
 29         x = v.x;
 30         y = v.y;
 31     }
 32 
 33     Vector operator + (const Vector &v) {
 34         return Vector(x + v.x, y + v.y);
 35     }
 36 
 37     Vector operator - (const Vector &v) {
 38         return Vector(x - v.x, y - v.y);
 39     }
 40 
 41     Vector operator * (double f) {
 42         return Vector(x * f, y * f);
 43     }
 44 
 45     Vector operator / (double f) {
 46         //return (*this) * (1.0 / f);
 47         return Vector(x / f, y / f);
 48     }
 49 
 50     double length() {//返回长度的平方
 51         return sqr(x) + sqr(y);
 52     }
 53 
 54     void factor() {//将该向量变为单位向量
 55         double len = sqrt(length());
 56         x /= len;
 57         y /= len;
 58     }
 59 
 60     void print() {
 61         cout << "(" << x << "," << y << ")";
 62     }
 63 };
 64 
 65 //星球结构体
 66 class Planet {
 67 public:
 68     Vector pos;//位置
 69     Vector v;//速度
 70     Vector a;//加速度
 71     double m;//质量
 72 };
 73 
 74 //封装四叉树 
 75 namespace QuatTree {
 76     const int SON = 4;//儿子个数，使用常量易于拓展，比如想拓展为八叉树只需要修改此常量为8即可
 77     const int SIZE = 1e5 + 5;//预开SIZE个Node节点备用，应保证 SIZE >= NUME_PLANETS * log2(N), N表示初始边界大小
 78 
 79     //四叉树的节点
 80     struct Node {
 81         double mass;//质量
 82         Vector center;//重心
 83         bool isleaf;//是否为叶子节点
 84         Node* child[SON];
 85         /*当前节点的四个儿子节点,分布如下
 86          * 01
 87          * 23
 88          */
 89         
 90         Node():mass(0), isleaf(0), center(){
 91             for (int i = 0; i < SON; i ++)
 92                 child[i] = NULL;
 93         }
 94         ~Node() {}
 95 
 96         void init(Planet *p);//使用一个星球对四叉树节点进行初始化
 97         void update();//使用四个儿子节点的信息更新当前节点的信息
 98     };
 99 
100     Node *null = new Node();//空指针，使用自定义null而不用NULL可以减少 if(Node == NULL) 的判断
101     Node *root;//四叉树的根
102 
103     void Node::init(Planet *p) {
104         mass = p -> m;
105         isleaf = 1;
106         center = p -> pos;
107         child[0] = null;
108         child[1] = null;
109         child[2] = null;
110         child[3] = null;
111     }
112 
113     void Node::update() {
114         mass = 0;
115         isleaf = 1;
116         center.x = center.y = 0;
117         for (int i = 0; i < SON; i ++) {
118             if (child[i] == null) continue;
119             isleaf = 0;
120             mass += child[i] -> mass; 
121             center.x += child[i] -> mass * (child[i] -> center).x;
122             center.y += child[i] -> mass * (child[i] -> center).y;
123         }
124         center.x /= mass;
125         center.y /= mass;
126     }
127 
128     Node pool[SIZE];//内存池
129     int count;//内存池的计数器
130 
131     void init() {//四叉树初始化
132         count = 0;
133         root = null;
134     }
135 
136     Node *getNewNode() {//从内存池中获得一个Node指针
137         return &(pool[count ++]);
138     }    
139 
140     void insert(Node *&o, Planet *p, 
141         double lx = -BORDER_LIMIT, double rx = BORDER_LIMIT, 
142         double ly = -BORDER_LIMIT, double ry = BORDER_LIMIT) {
143         //当前处理的二位平面为 lx <= x < rx, ly <= y < ry
144         if (o == null) {
145             o = getNewNode();
146             o -> init(p);
147             return;
148         }
149         double midx = (lx + rx) / 2, midy = (ly + ry) / 2;
150         if ((p -> pos).x < midx) {
151             if ((p -> pos).y < midy) insert(o -> child[0], p, lx, midx, ly, midy);
152             else insert(o -> child[2], p, lx, midx, midy, ry);
153         }    
154         else {
155             if ((p -> pos).y < midy) insert(o -> child[1], p, lx, midx, ly, midy);
156             else insert(o -> child[3], p, lx, midx, midy, ry);
157         }
158         o -> update();
159     }
160 
161     Planet calc(Planet *p, Node *o, int tim = 1000) {
162         //计算星球p，在已建好的四叉树o中，经过时间tim之后的状态
163 
164     }
165 
166     vector<Planet> getQuatTree(vector<Planet> planets, int tim = 1000) {
167         //星球集合planets经过时间tim后的状态，tim单位为ms，默认为1000ms
168         init();//初始化
169         int n = planets.size();//获得星球数量
170 
171         for (int i = 0; i < n; i ++) {
172             insert(root, &planets[i]);
173         }
174 
175         vector<Planet> result(n);
176         for (int i = 0; i < n; i ++) {
177             result[i] = calc(&planets[i], root, tim);
178         }
179 
180         return result;
181     }
182 } 
183 
184 int main() {
185     vector<Planet> planets(NUME_PLANETS);
186     int num = NUME_PLANETS;
187 
188     /*生成所有星球初始值
189      */ 
190 
191     /*每隔一定时间进行一次计算即可，使用方法如下
192      * for (int i = 0; i < times; i ++) {//计算times次
193      *     planets = QuatTree::getQuatTree(planets);
194      *        print(planets);//输出所有星球信息
195      * }
196      */
197     return 0;
198 }