1
2#include <stdlib.h>
3#include <stdio.h>
4#include <assert.h>
5
6
7
8// search_box 时候还需要判断是否有叶子节点。没有的话。则不返回该非叶子节点。
9
10// delete
11
12
13
14
15#define QUAD_SUB_NODE_COUNT 4
16
17
enum 
{
18
NE, // 0
19 NW, // 1
20 SW, // 2
21 SE, // 3
22
};
23
24bool overlap_box (int v1_minx, int v1_miny, int v1_maxx, int v1_maxy,
25 int v2_minx, int v2_miny, int v2_maxx, int v2_maxy)
26{
27 //return (this->_min._x > rv._max._x || this->_max._x < rv._min._x ||
28 // this->_min._y > rv._max._y || this->_max._y < rv._min._y) ?
29 // false : true;
30 return !(v1_minx > v2_maxx || v1_maxx < v2_minx ||
31 v1_miny >v2_maxy || v1_maxy <v2_miny); // ? false : true;
32}
33
34
35bool at_point (int v1_minx, int v1_miny, int v1_maxx, int v1_maxy,
36 int v2_minx, int v2_miny, int v2_maxx, int v2_maxy)
37{
38 return (v1_minx == v2_minx && v1_maxx == v2_maxx &&
39 v1_miny == v2_miny && v1_maxy == v2_maxy);
40}
41
42
43
44#include <list>
45
46struct Node;
47struct Leaf_Node
48{
49 Node * _parent;
50 typedef std::list <void *> List;
51 List data_list;
52};
53
54struct Node
55{
56 void init (Node * parent)
57
{
58 _parent = parent;
59 _leaf_node = 0;
60 _sub[NE] = 0;
61 _sub[NW] = 0;
62 _sub[SW] = 0;
63 _sub[SE] = 0;
64
}
65
66 void set (int min_x, int min_y, int max_x, int max_y)
67 {
68 _min_x = min_x;
69 _min_y = min_y;
70 _max_x = max_x;
71 _max_y = max_y;
72 }
73
74 bool has_child ()
75 {
76 return _sub[NE] != 0;
77 }
78
79 bool is_sub_empty ()
80 {
81 return
82 !(_sub[NE]->_sub[NE] &&
83 //_sub[NE]->_sub[NW] &&
84 //_sub[NE]->_sub[SW] &&
85 //_sub[NE]->_sub[SE] &&
86
87 _sub[NW]->_sub[NE] &&
88 //_sub[NW]->_sub[NW] &&
89 //_sub[NW]->_sub[SW] &&
90 //_sub[NW]->_sub[SE] &&
91
92 _sub[SW]->_sub[NE] &&
93 //_sub[SW]->_sub[NW] &&
94 //_sub[SW]->_sub[SW] &&
95 //_sub[SW]->_sub[SE] &&
96
97 _sub[SE]->_sub[NE] //&&
98 //_sub[SE]->_sub[NW] &&
99 //_sub[SE]->_sub[SW] &&
100 //_sub[SE]->_sub[SE]
101 );
102 }
103
104 void create_child ()
105 {
106 _sub[NE] = (Node *) malloc (sizeof Node);
107 _sub[NW] = (Node *) malloc (sizeof Node);
108 _sub[SW] = (Node *) malloc (sizeof Node);
109 _sub[SE] = (Node *) malloc (sizeof Node);
110
111 _sub[NE]->init (this);
112 _sub[NW]->init (this);
113 _sub[SW]->init (this);
114 _sub[SE]->init (this);
115
116 _sub[NE]->_index_in_parent = NE;
117 _sub[NW]->_index_in_parent = NW;
118 _sub[SW]->_index_in_parent = SW;
119 _sub[SE]->_index_in_parent = SE;
120
121 int center_x = (_max_x + _min_x) >> 1; /**//// 2;
122 int center_y = (_max_y + _min_y) >> 1; /**//// 2;
123
124 _sub[NE]->set (center_x, center_y,
125 _max_x, _max_y);
126
127 _sub[NW]->set (_min_x, center_y,
128 center_x, _max_y);
129
130 _sub[SW]->set (_min_x, _min_y,
131 center_x, center_y);
132
133 _sub[SE]->set (center_x, _min_y,
134 _max_x, center_y);
135}
136
137 Node * _sub[QUAD_SUB_NODE_COUNT];
138 Node * _parent;
139 int _index_in_parent;
140 Leaf_Node * _leaf_node;
141 int _min_x;
142 int _min_y;
143 int _max_x;
144 int _max_y;
145 //int x;
146 //int y;
147};
148
149
150// 回调
151typedef int (* search_box_callback) (Node * node);
152
153
154class Quadtree
155{
156public:
157
158 Quadtree ()
159 {
160 _root = 0;
161 _depth = 6;
162 }
163
164 // 初始化 四叉树大小
165 void init (int width, int height)
166 {
167 _width = width;
168 _height = height;
169
170 _root = (Node *) malloc (sizeof Node);
171 _root->init (0);
172 _root->set (0, 0, width, height);
173 }
174
175 // 递归销毁
176 void destroy (Node * curr_node)
177 {
178 if (curr_node) {
179 if (curr_node->has_child()) {
180 destroy (curr_node->_sub[NE]);
181 destroy (curr_node->_sub[NW]);
182 destroy (curr_node->_sub[SW]);
183 destroy (curr_node->_sub[SE]);
184 }
185 free (curr_node);
186 }
187 }
188
189 // 在x， y上插入四叉树
190 void insert (int x, int y)
191 {
192 assert (x <= _width && y <=_height);
193 //int deep = 5;
194 _insert (_root, x, y, 0, 0, _width, _height, _depth);
195 }
196
197 // 判断点在哪个象限，然后再往那个象限细分。
198 void _insert (Node * curr_node, int x, int y,
199 int min_x, int min_y, int max_x, int max_y, int deep)
200 {
201 if (deep <= 0) {
202 // 到了最深层了。该结束了。
203 if (x >= min_x && x <= max_x && y >= min_y && y <= max_y) {
204 printf ("add leaf: (%d,%d) (%d,%d)\n", min_x, min_y,
205 max_x, max_y);
206 if (!curr_node->_leaf_node) {
207 Leaf_Node * leaf = new Leaf_Node;
208 leaf->_parent = curr_node;
209 curr_node->_leaf_node = leaf;
210 }
211 }
212 return ;
213 }
214
215 if (! curr_node->has_child ()) {
216 curr_node->create_child ();
217 }
218
219 int center_x = (max_x + min_x) >> 1; // / 2;
220 int center_y = (max_y + min_y) >> 1; // / 2;
221
222 if (x < center_x) {
223 if (y < center_y) {
224 // 设置子节点
225 //curr_node->_sub[SW]->set (min_x, min_y, center_x, center_y);
226 //_insert (curr_node->_sub[SW], x, y,
227 // min_x, min_y, center_x, center_y, -- deep);
228 _insert (curr_node->_sub[SW], x, y,
229 curr_node->_sub[SW]->_min_x,
230 curr_node->_sub[SW]->_min_y,
231 curr_node->_sub[SW]->_max_x,
232 curr_node->_sub[SW]->_max_y,
233 -- deep);
234 printf ("insert SW sub node: (%d, %d), (%d, %d)\n",
235 min_x, min_y, center_x, center_y);
236
237 }
238 else {
239 //curr_node->_sub[NW]->set (min_x, center_y, center_x, max_y);
240 //_insert (curr_node->_sub[NW], x, y,
241 // min_x, center_y, center_x, max_y, -- deep);
242 _insert (curr_node->_sub[NW], x, y,
243 curr_node->_sub[NW]->_min_x,
244 curr_node->_sub[NW]->_min_y,
245 curr_node->_sub[NW]->_max_x,
246 curr_node->_sub[NW]->_max_y,
247 -- deep);
248 printf ("insert NW sub node: (%d, %d), (%d, %d)\n",
249 min_x, center_y, center_x, max_y);
250 }
251 }
252 else {
253 if (y < center_y) {
254 //curr_node->_sub[SE]->set (center_x, min_y, max_x, center_y);
255 //_insert (curr_node->_sub[SE], x, y,
256 // center_x, min_y, max_x, center_y, -- deep);
257 _insert (curr_node->_sub[SE], x, y,
258 curr_node->_sub[SE]->_min_x,
259 curr_node->_sub[SE]->_min_y,
260 curr_node->_sub[SE]->_max_x,
261 curr_node->_sub[SE]->_max_y,
262 -- deep);
263 printf ("insert SE sub node: (%d, %d), (%d, %d)\n",
264 center_x, min_y, max_x, center_y);
265
266 }
267 else {
268 //curr_node->_sub[NE]->set (center_x, center_y, max_x, max_y);
269 //_insert (curr_node->_sub[NE], x, y,
270 // center_x, center_y, max_x, max_y, -- deep);
271
272 _insert (curr_node->_sub[NE], x, y,
273 curr_node->_sub[NE]->_min_x,
274 curr_node->_sub[NE]->_min_y,
275 curr_node->_sub[NE]->_max_x,
276 curr_node->_sub[NE]->_max_y,
277 -- deep);
278
279
280 printf ("insert NE sub node: (%d, %d), (%d, %d)\n",
281 center_x, center_y, max_x, max_y);
282 }
283
284 }
285 }
286
287 // 搜索的次数还是太多。当一个空节点的时候。
288 void search_box (int x, int y,
289 int dx, int dy,
290 search_box_callback cb)
291 {
292 _search_box (_root, /**//*x, y,*/ x-dx, y-dy, x+dx, y+dy, cb);
293 }
294
295
296 void _search_box (Node * node, /**//*int x, int y,*/
297 int min_x, int min_y, int max_x, int max_y,
298 search_box_callback cb)
299 {
300 printf ("search_box\n");
301 if (overlap_box (min_x, min_y,
302 max_x, max_y,
303 node->_min_x, node->_min_y,
304 node->_max_x, node->_max_y)) {
305 if (node->has_child()) {
306 _search_box (node->_sub[NE], /**//*x, y,*/ min_x, min_y, max_x, max_y, cb);
307 _search_box (node->_sub[NW],/**//* x, y,*/ min_x, min_y, max_x, max_y, cb);
308 _search_box (node->_sub[SW], /**//*x, y,*/ min_x, min_y, max_x, max_y, cb);
309 _search_box (node->_sub[SE], /**//*x, y,*/ min_x, min_y, max_x, max_y, cb);
310 }
311 // 不再有子节点。说明已经是叶子了。可以返回给上一层了。
312 else {
313 if (node->_leaf_node) {
314 printf ("search_box finded: ");
315 cb (node);
316 }
317 }
318 }
319 }
320
321
322
323 void search_line (int x, int y,
324 int end_x, int end_y, search_box_callback cb)
325 {
326 int min_x = x < end_x ? x: end_x;
327 int min_y = y < end_y ? y: end_y;
328 int max_x = x > end_x ? x : end_x;
329 int max_y = y > end_y ? y : end_y;
330
331 // 斜率
332 float h = ((float) max_y - (float)min_y) / ((float)max_x - (float)min_x);
333 _search_line (_root, h, x, y, min_x, min_y, max_x, max_y, cb);
334 }
335
336 void _search_line (Node * curr_node, float h, int x, int y, // x, y, h用来算一个点在不在一个直线上
337 int min_x, int min_y, int max_x, int max_y, search_box_callback cb)
338 {
339 printf ("search_line\n");
340 if (overlap_box (min_x, min_y,
341 max_x, max_y,
342 curr_node->_min_x, curr_node->_min_y,
343 curr_node->_max_x, curr_node->_max_y)) {
344 if (curr_node->has_child()) {
345 _search_line (curr_node->_sub[NE], h, x, y, min_x, min_y, max_x, max_y, cb);
346 _search_line (curr_node->_sub[NW], h, x, y, min_x, min_y, max_x, max_y, cb);
347 _search_line (curr_node->_sub[SW], h, x, y, min_x, min_y, max_x, max_y, cb);
348 _search_line (curr_node->_sub[SE], h, x, y, min_x, min_y, max_x, max_y, cb);
349 }
350 // 不再有子节点。说明已经是叶子了。可以返回给上一层了。
351 else {
352 // 是否在直线内，并且有叶子节点
353 if (abs((float)(curr_node->_min_y) - (float)y - ((float)(curr_node->_min_x) - (float)x) * h) < 0.01f) {
354 if (curr_node->_leaf_node) {
355 printf ("search_line finded: ");
356 cb (curr_node);
357 }
358 }
359
360 }
361 }
362
363 }
364
365 void _delete_empty_node (Node * node)
366 {
367 printf ("_delete_empty_node\n");
368 if (_root == node) {
369 return;
370 }
371 // 上一层的其他子节点没有叶子了。
372 if (!(node->_parent->_sub[NE]->_leaf_node || node->_parent->_sub[NW]->_leaf_node
373 || node->_parent->_sub[SW]->_leaf_node || node->_parent->_sub[SE]->_leaf_node)) {
374 Node * parent = node->_parent;
375 free (parent->_sub[NE]);
376 free (parent->_sub[NW]);
377 free (parent->_sub[SW]);
378 free (parent->_sub[SE]);
379
380 parent->_sub[NE] = 0;
381 parent->_sub[NW] = 0;
382 parent->_sub[SW] = 0;
383 parent->_sub[SE] = 0;
384
385 _delete_empty_node (parent);
386 }
387 }
388
389 void delete_node (Leaf_Node * leaf/**//*, Node * curr_node*/)
390 {
391 Node * in_node = leaf->_parent;
392 in_node->_leaf_node = 0;
393 delete leaf;
394
395 _delete_empty_node (in_node);
396
397 }
398
399
400 Node * get_node (int x, int y)
401 {
402 return _search (x, y, x+1, y+1, _root);
403 }
404
405 // 搜索的次数还是太多。当一个空节点的时候。
406 Node * _search (int min_x, int min_y, int max_x, int max_y, Node * curr_node)
407 {
408 printf ("_search() \n");
409 if (overlap_box (min_x, min_y, max_x, max_y,
410 curr_node->_min_x, curr_node->_min_y,
411 curr_node->_max_x, curr_node->_max_y)) {
412
413 if (curr_node->_leaf_node) {
414 if (at_point (min_x, min_y, max_x, max_y,
415 curr_node->_min_x, curr_node->_min_y,
416 curr_node->_max_x, curr_node->_max_y)) {
417 printf ("find! %d %d\n", min_x, min_y);
418 return curr_node;
419 }
420 }
421
422
423 if (curr_node->has_child()) {
424 printf ("serach :(%d,%d):(%d,%d)\n", min_x, min_y, max_x, max_y);
425
426 for (int i = 0; i < QUAD_SUB_NODE_COUNT; i ++) {
427 Node * ret = _search(min_x, min_y,
428 max_x, max_y, curr_node->_sub[i]);
429 if (ret) {
430 return ret;
431 }
432 }
433 }
434 }
435 return 0;
436 }
437
438
439 // 递归打印
440 void dump (Node * node, int deep = 0)
441 {
442 if (node) {
443 for (int i = 0; i < deep; i ++) {
444 printf ("+");
445 }
446 printf ("minx: %d, miny: %d, maxx: %d, maxy: %d\n",
447 node->_min_x, node->_min_y, node->_max_x, node->_max_y);
448 if (node->has_child()) {
449 dump (node->_sub[NE], ++deep);
450 dump (node->_sub[NW], deep);
451 dump (node->_sub[SW], deep);
452 dump (node->_sub[SE], deep);
453 }
454 }
455 }
456
457 // 获取root
458 Node * root ()
459 {
460 return _root;
461 }
462
463protected:
464 Node * _root;
465 int _width;
466 int _height;
467 int _depth;
468};
469
470
posted on 2009-06-12 23:18
风化血 阅读(369)
评论(0) 编辑 收藏 引用