ObjectARX之四叉树例子Source
本帖最后由 gzxl 于 2024-4-5 23:22 编辑四叉树的原理网站介绍比较多，下面源码只是提供几个demo：
搜索最近的点
搜索最近的圆
搜索最近的矩形
圆碰撞检测
矩形碰撞检测
点搜索所在的三角形(即点在三角网内)
至于四叉树的原理大家有兴趣就bing，比较详细了。
在提供坐标的情况下，对于需要查询（可包括点、圆、矩形、三角形、线段等）利用四叉树进行查询的速度很快，搜索速度如下统计：
(1)测试搜索最近的点
采集图元 100000 个用时: 47 毫秒
共有100000个点参与构建四叉树，用时: 78 毫秒
在四叉树中查询附近点个数为478个,用时: 16 毫秒
(2)测试搜索最近的圆
采集图元 100000 个用时: 47 毫秒
共有100000个圆参与构建四叉树，用时: 62 毫秒
在四叉树中查询附近圆个数为475个,用时: 16 毫秒
(3)测试搜索最近的矩形
采集图元 100000 个用时: 62 毫秒
共有100000个矩形参与构建四叉树，用时: 63 毫秒
在四叉树中查询附近矩形个数为70个,用时: 0 毫秒
(4)测试圆碰撞
请框选构建四叉树的圆:指定对角点: 找到 100000 个
采集圆 100000 个用时: 47 毫秒
共有 100000 个圆参与构建四叉树，用时: 62 毫秒
有 17684 个圆发生碰撞!
碰撞检测用时: 297 毫秒
(4)测试矩形碰撞
请框选构建四叉树的矩形:指定对角点: 找到 100000 个
采集矩形 100000 个用时: 46 毫秒
共有 100000 个矩形参与构建四叉树，用时: 63 毫秒
有 19605 个矩形发生碰撞!
碰撞检测用时: 344 毫秒
(5) 测试点搜索所在的三角形(即点在三角网内)
测试指点坐标点，且在视图不可见的情况下
double xTest = 377.2347;
double yTest = 267.7196;
采集图元 200437 个用时: 360 毫秒
共有 200437 个三角网参与构建四叉树，用时: 94 毫秒
三角网顶点1: x=377.6903,y=270.5267,z=1172.6420
三角网顶点2: x=374.4403,y=267.3267,z=1172.7040
三角网顶点3: x=379.8703,y=265.5137,z=1172.3000
在四叉树中查询指定点所在的三角网用时: 140 毫秒
先介绍这么多，有时间再根据补充。
本帖最后由 橡皮 于 2023-5-13 15:02 编辑
程序很顶，提供帮助极大，我在试用期间有以下疑问或者说问题（以添加圆为例，进行说明）：
1. 创建新节点的时候（代码964行），此处按理应该是先添加叶子节点 GQtree之后把数据添加上，以下代码会以待添加的圆圆心当做叶子节点的左下角，效果如下：
n->child = new nodeType(x, y, r, data);
n->node_size -= 1;
2. 判断两圆相交（259行处函数），这个计算原理是啥，想了半天没明白，我换了一种方法也贴在下边
// 两圆是否相交
bool Intersect(const nodeType* n, COOR_TYPE x, COOR_TYPE y, COOR_TYPE r) const
{
COOR_TYPE x0 = (n->x + n->x1) / 2;
COOR_TYPE y0 = (n->y + n->y1) / 2;
COOR_TYPE vx = x > x0 ? x - x0 : x0 - x;
COOR_TYPE vy = y > y0 ? y - y0 : y0 - y;
COOR_TYPE hx = n->x > x0 ? n->x - x0 : x0 - n->x;
COOR_TYPE hy = n->y > y0 ? n->y - y0 : y0 - n->y;
COOR_TYPE ux = vx > hx ? vx - hx : 0;
COOR_TYPE uy = vy > hy ? vy - hy : 0;
return ux * ux + uy * uy <= r * r;
}
bool Intersect(const nodeType* n, const COOR_TYPE& x, const COOR_TYPE& y, const COOR_TYPE& r) const
{
COOR_TYPE delta = n->r + r;
COOR_TYPE left = n->x - delta;
COOR_TYPE right = n->x1 + delta;
COOR_TYPE top = n->y1 + delta;
COOR_TYPE bottom = n->y - delta;
if (Inbound(left, bottom, right, top, x, y)) return true;
else return false;
//// 详细筛选规则
//if (Between(left, right, x) && Between(n->y, n->y1, y)) return true;
//if (Between(bottom, top, y) && Between(n->x, n->x1, x)) return true;
//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;
//else return false;
}
// 搜索指定宽、高内的节点(点的x y值 宽w 高h)
void Search(const nodeType* n, COOR_TYPE x, COOR_TYPE y, COOR_TYPE w, COOR_TYPE h, std::vector<const nodeType*>& result) const
{
if (n != NULL)
{
if (n->leaf)
{
acutPrintf(_T("n->leaf true"));
// 判断两个矩形是否相交
if (Intersect(n->x, n->y, n->w, n->h, x, y, w, h))
{
acutPrintf(_T(" push_back"));
result.push_back(n);
}
}
else if (Intersect(n, x, y, w, h) && n->node_size > 0)
{
acutPrintf(_T("n->leaf false"));
for (int i = 0; i < 4; i++)
{
if (n->child)
{
Search(n->child, x, y, w, h, result);
acutPrintf(_T("n->node Search"));
}
}
}
}
}
这段矩形碰撞的原理是什么？？？为什么判断两个矩形碰撞，先要判断一个矩形和另一个的nodeType，也就是另一个矩形所在的节点是否碰撞？？？我测试的例子大部分都是检查出来了，就有一个怎么都不对，这个没检查出来的就是我说的这种，一个矩形和节点没碰撞，但是和这个节点里的一个child是碰撞的，不知道我这么理解对不对，这导致循序直接跳过这个nodeType，他的四个child也被跳过了，想完善完善还是能力不足，问题先放着，先谢谢g大，确实牛b 不会用啊 飞雪神光 发表于 2022-11-2 20:12
不会用啊
:(可以学啊，代码之供参考。 学到了~~谢谢大佬:lol 支持一下大师
学到了~~谢谢大佬 我需要很多不等直径的圆排列，可以实现吗？ cable2004 发表于 2022-11-2 23:50
支持一下大师
谢谢支持，但不是大师，还在学习arx中。 dcl1214 发表于 2022-11-3 14:31
我需要很多不等直径的圆排列，可以实现吗？
这应该与四叉树无关吧。有规则应该可以，但看不懂规则。 学到了~~谢谢大佬
页:
[1]
2