ObjectARX之四叉树例子Source

gzxl

四叉树的原理网站介绍比较多，下面源码只是提供几个demo：

搜索最近的点
搜索最近的圆
搜索最近的矩形
圆碰撞检测
矩形碰撞检测
点搜索所在的三角形(即点在三角网内)

至于四叉树的原理大家有兴趣就bing，比较详细了。
在提供坐标的情况下，对于需要查询（可包括点、圆、矩形、三角形、线段等）利用四叉树进行查询的速度很快，搜索速度如下统计：

1. (1)测试搜索最近的点
   
2. 采集图元 100000 个用时: 47 毫秒
   
3. 共有100000个点参与构建四叉树，用时: 78 毫秒
   
4. 在四叉树中查询附近点个数为478个,用时: 16 毫秒
   
5. 
   
6. (2)测试搜索最近的圆
   
7. 采集图元 100000 个用时: 47 毫秒
   
8. 共有100000个圆参与构建四叉树，用时: 62 毫秒
   
9. 在四叉树中查询附近圆个数为475个,用时: 16 毫秒
   
10. 
    
11. (3)测试搜索最近的矩形
    
12. 采集图元 100000 个用时: 62 毫秒
    
13. 共有100000个矩形参与构建四叉树，用时: 63 毫秒
    
14. 在四叉树中查询附近矩形个数为70个,用时: 0 毫秒
    
15. 
    
16. (4)测试圆碰撞
    
17. 请框选构建四叉树的圆:指定对角点: 找到 100000 个
    
18. 采集圆 100000 个用时: 47 毫秒
    
19. 共有 100000 个圆参与构建四叉树，用时: 62 毫秒
    
20. 有 17684 个圆发生碰撞!
    
21. 碰撞检测用时: 297 毫秒
    
22. 
    
23. (4)测试矩形碰撞
    
24. 请框选构建四叉树的矩形:指定对角点: 找到 100000 个
    
25. 采集矩形 100000 个用时: 46 毫秒
    
26. 共有 100000 个矩形参与构建四叉树，用时: 63 毫秒
    
27. 有 19605 个矩形发生碰撞!
    
28. 碰撞检测用时: 344 毫秒
    
29. 
    
30. (5) 测试点搜索所在的三角形(即点在三角网内)
    
31. 测试指点坐标点，且在视图不可见的情况下
    
32. double xTest = 377.2347;
    
33. double yTest = 267.7196;
    
34. 采集图元 200437 个用时: 360 毫秒
    
35. 共有 200437 个三角网参与构建四叉树，用时: 94 毫秒
    
36. 三角网顶点1: x=377.6903,y=270.5267,z=1172.6420
    
37. 三角网顶点2: x=374.4403,y=267.3267,z=1172.7040
    
38. 三角网顶点3: x=379.8703,y=265.5137,z=1172.3000
    
39. 在四叉树中查询指定点所在的三角网用时: 140 毫秒

复制代码

先介绍这么多，有时间再根据补充。

橡皮

程序很顶，提供帮助极大，我在试用期间有以下疑问或者说问题（以添加圆为例，进行说明）：
1. 创建新节点的时候（代码964行），此处按理应该是先添加叶子节点 GQtree之后把数据添加上，以下代码会以待添加的圆圆心当做叶子节点的左下角，效果如下：

1. n->child[index] = new nodeType(x, y, r, data);
   
2. n->node_size -= 1;

复制代码

2. 判断两圆相交（259行处函数），这个计算原理是啥，想了半天没明白，我换了一种方法也贴在下边

1. // 两圆是否相交
   
2. bool Intersect(const nodeType* n, COOR_TYPE x, COOR_TYPE y, COOR_TYPE r) const
   
3. {
   
4.    COOR_TYPE x0 = (n->x + n->x1) / 2;
   
5.    COOR_TYPE y0 = (n->y + n->y1) / 2;
   
6.    COOR_TYPE vx = x > x0 ? x - x0 : x0 - x;
   
7.    COOR_TYPE vy = y > y0 ? y - y0 : y0 - y;
   
8.    COOR_TYPE hx = n->x > x0 ? n->x - x0 : x0 - n->x;
   
9.    COOR_TYPE hy = n->y > y0 ? n->y - y0 : y0 - n->y;
   
10.    COOR_TYPE ux = vx > hx ? vx - hx : 0;
    
11.    COOR_TYPE uy = vy > hy ? vy - hy : 0;
    
12.    return ux * ux + uy * uy <= r * r;
    
13. }
    
14. 
    
15. 
    
16. bool Intersect(const nodeType* n, const COOR_TYPE& x, const COOR_TYPE& y, const COOR_TYPE& r) const
    
17. {
    
18.     COOR_TYPE delta = n->r + r;
    
19.     COOR_TYPE left = n->x - delta;
    
20.     COOR_TYPE right = n->x1 + delta;
    
21.     COOR_TYPE top = n->y1 + delta;
    
22.     COOR_TYPE bottom = n->y - delta;
    
23.    
    
24.     if (Inbound(left, bottom, right, top, x, y)) return true;
    
25.     else return false;
    
26. 
    
27.     //// 详细筛选规则
    
28.     //if (Between(left, right, x) && Between(n->y, n->y1, y)) return true;
    
29.     //if (Between(bottom, top, y) && Between(n->x, n->x1, x)) return true;
    
30.     //if (InReach(n->x, n->y, x, y, delta) || InReach(n->x1, n->y, x, y, delta) || InReach(n->x1, n->y1, x, y, delta) || InReach(n->x, n->y1, x, y, delta)) return true;
    
31.     //else return false;
    
32. }

复制代码

why1025

1. // 搜索指定宽、高内的节点(点的x y值 宽w 高h)
   
2.         void Search(const nodeType* n, COOR_TYPE x, COOR_TYPE y, COOR_TYPE w, COOR_TYPE h, std::vector<const nodeType*>& result) const
   
3.         {
   
4.             if (n != NULL)
   
5.             {
   
6.                 if (n->leaf)
   
7.                 {
   
8.                     acutPrintf(_T("n->leaf true"));
   
9.                                         // 判断两个矩形是否相交
   
10.                     if (Intersect(n->x, n->y, n->w, n->h, x, y, w, h))
    
11.                     {
    
12.                         acutPrintf(_T(" push_back  "));
    
13.                         result.push_back(n);
    
14.                     }
    
15.                 }
    
16.                 else if (Intersect(n, x, y, w, h) && n->node_size > 0)
    
17.                 {
    
18.                     acutPrintf(_T("n->leaf false"));
    
19.                                         for (int i = 0; i < 4; i++)
    
20.                     {
    
21.                         if (n->child[i])
    
22.                         {
    
23.                             Search(n->child[i], x, y, w, h, result);
    
24.                             acutPrintf(_T("n->node Search  "));
    
25.                         }
    
26.                     }
    
27.                 }
    
28.             }
    
29.         }

复制代码

这段矩形碰撞的原理是什么？？？为什么判断两个矩形碰撞，先要判断一个矩形和另一个的nodeType，也就是另一个矩形所在的节点是否碰撞？？？我测试的例子大部分都是检查出来了，就有一个怎么都不对，这个没检查出来的就是我说的这种，一个矩形和节点没碰撞，但是和这个节点里的一个child是碰撞的，不知道我这么理解对不对，这导致循序直接跳过这个nodeType，他的四个child也被跳过了，想完善完善还是能力不足，问题先放着，先谢谢g大，确实牛b

飞雪神光

不会用啊

gzxl

飞雪神光 发表于 2022-11-2 20:12
不会用啊

可以学啊，代码之供参考。

东升铮

学到了~~谢谢大佬

cable2004

支持一下大师

czb203

学到了~~谢谢大佬

dcl1214

我需要很多不等直径的圆排列，可以实现吗？

gzxl

cable2004 发表于 2022-11-2 23:50
支持一下大师

谢谢支持，但不是大师，还在学习arx中。

gzxl

dcl1214 发表于 2022-11-3 14:31
我需要很多不等直径的圆排列，可以实现吗？

这应该与四叉树无关吧。有规则应该可以，但看不懂规则。

cjt472017713

学到了~~谢谢大佬