随笔-2  评论-0  文章-0  trackbacks-0
  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
 17enum {
 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 (00, 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, 00, _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 风化血 阅读(340) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理