全部栏目

首页 行业资讯 美食菜系 特产小吃 健康饮食 教你做菜

如何使用C或C++结构建立八叉树的模型

发布网友

我来回答

共2个回答

热心网友

以下程序摘自互联网，是C++的
如果要用C语言编写，则
（1）使用C结构建立八叉树的模型
1.typedef struct OctreeNode 2.{ 3. int value; 4. struct OctreeNode *Up; 5. struct OctreeNode *Down; 6. struct OctreeNode *Left; 7. struct OctreeNode *Right; 8. struct OctreeNode *Front; 9. struct OctreeNode *Back; 10.}OctreeNode;
（2）递归添加上下左右前后邻居，我这里只给一面
1.void AddUp(OctreeNode *Me, int v) 2.{ 3. Me->Up = (OctreeNode *)malloc(sizeof (OctreeNode)); 4. Me->Up->vvalue = v; 5. Me->Up->Up = NULL; 6. Me->Up->Down = Me; 7. Me->Up->Front = NULL; 8. OctreeMe->Up->Back = NULL; 9. Me->Up->Right = NULL; 10. Me->Up->Left = NULL; 11.}
实现Octree的原理
(1). 设定最大递归深度
(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体
(3). 依序将单位元元素丢入能被包含且没有子节点的立方体
(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八
个子立方体
(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止
细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目
还是一样，会造成无穷切割的情形。
(6). 重复3，直到达到最大递归深度。

#include <iostream.h>
using namespace std;//定义八叉树节点类
template<class T>
struct OctreeNode
{
T data; //节点数据
T xmin,xmax; //节点坐标，即六面体个顶点的坐标
T ymin,ymax;
T zmin,zmax;
OctreeNode <T> *top_left_front,*top_left_back; //该节点的个子结点
OctreeNode <T> *top_right_front,*top_right_back;
OctreeNode <T> *bottom_left_front,*bottom_left_back;
OctreeNode <T> *bottom_right_front,*bottom_right_back;
OctreeNode //节点类
(T nodeValue = T(),
T xminValue = T(),T xmaxValue = T(),
T yminValue = T(),T ymaxValue = T(),
T zminValue = T(),T zmaxValue = T(),
OctreeNode<T>* top_left_front_Node = NULL,
OctreeNode<T>* top_left_back_Node = NULL,
OctreeNode<T>* top_right_front_Node = NULL,
OctreeNode<T>* top_right_back_Node = NULL,
OctreeNode<T>* bottom_left_front_Node = NULL,
OctreeNode<T>* bottom_left_back_Node = NULL,
OctreeNode<T>* bottom_right_front_Node = NULL,
OctreeNode<T>* bottom_right_back_Node = NULL )
:data(nodeValue),
xmin(xminValue),xmax(xmaxValue),
ymin(yminValue),ymax(ymaxValue),
zmin(zminValue),zmax(zmaxValue),
top_left_front(top_left_front_Node),
top_left_back(top_left_back_Node),
top_right_front(top_right_front_Node),
top_right_back(top_right_back_Node),
bottom_left_front(bottom_left_front_Node),
bottom_left_back(bottom_left_back_Node),
bottom_right_front(bottom_right_front_Node),
bottom_right_back(bottom_right_back_Node){}
};
//创建八叉树
template <class T>
void createOctree(OctreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
cout<<"处理中，请稍候……"<<endl;
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
if(maxdepth>=0)
{
root=new OctreeNode<T>();
root->data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为。
root->xmin=xmin; //为节点坐标赋值
root->xmax=xmax;
root->ymin=ymin;
root->ymax=ymax;
root->zmin=zmin;
root->zmax=zmax;
double xm=(xmax-xmin)/2;//计算节点个维度上的半边长
double ym=(ymax-ymin)/2;
double zm=(ymax-ymin)/2;
//递归创建子树，根据每一个节点所处（是几号节点）的位置决定其子结点的坐标。
createOctree(root->top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root->top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root->top_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root->top_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root->bottom_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root->bottom_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmin,zmax-zm);
createOctree(root->bottom_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root->bottom_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmin,zmax-zm);
}
}
int i=1;
//先序遍历八叉树
template <class T>
void preOrder( OctreeNode<T> * & p)
{
if(p)
{
cout<<i<<".当前节点的值为："<<p->data<<"\n坐标为：";
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
i+=1;
cout<<endl;
preOrder(p->top_left_front);
preOrder(p->top_left_back);
preOrder(p->top_right_front);
preOrder(p->top_right_back);
preOrder(p->bottom_left_front);
preOrder(p->bottom_left_back);
preOrder(p->bottom_right_front);
preOrder(p->bottom_right_back);
cout<<endl;
}
}
//求八叉树的深度
template<class T>
int depth(OctreeNode<T> *& p)
{
if(p == NULL)
return -1;
int h = depth(p->top_left_front);
return h+1;
}
//计算单位长度，为查找点做准备
int cal(int num)
{
int result=1;
if(1==num)
result=1;
else
{
for(int i=1;i<num;i++)
result=2*result;
}
return result;
}
//查找点
int maxdepth=0;
int times=0;
static double xmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;
int tmaxdepth=0;
double txm=1,tym=1,tzm=1;
template<class T>
void find(OctreeNode<T> *& p,double x,double y,double z)
{
double xm=(p->xmax-p->xmin)/2;
double ym=(p->ymax-p->ymin)/2;
double zm=(p->ymax-p->ymin)/2;
times++;
if(x>xmax || x<xmin || y>ymax || y<ymin || z>zmax || z<zmin)
{
cout<<"该点不在场景中！"<<endl;
return;
}
if(x<=p->xmin+txm && x>=p->xmax-txm && y<=p->ymin+tym && y>=p->ymax-tym && z<=p->zmin+tzm && z>=p->zmax-tzm )
{
cout<<endl<<"找到该点！"<<"该点位于"<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<"节点内！"<<endl;
cout<<"共经过"<<times<<"次递归！"<<endl;
}
else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_left_back,x,y,z);
}
else if(x<(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_left_back,x,y,z);
}
else if(x>(p->xmax-xm) && y<(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_right_back,x,y,z);
}
else if(x>(p->xmax-xm) && y<(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_right_back,x,y,z);
}
else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_left_front,x,y,z);
}
else if(x<(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_left_front,x,y,z);
}
else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z<(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->bottom_right_front,x,y,z);
}
else if(x>(p->xmax-xm) && y>(p->ymax-ym) && z>(p->zmax-zm))
{
cout<<"当前经过节点坐标："<<endl;
cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
cout<<endl;
find(p->top_right_front,x,y,z);
}
}
//main函数
int main ()
{
OctreeNode<double> * rootNode = NULL;
int choiced = 0;
while(true)
{
system("cls");
cout<<"请选择操作：\n";
cout<<"1.创建八叉树 2.先序遍历八叉树\n";
cout<<"3.查看树深度 4.查找节点 \n";
cout<<"0.退出\n\n";
cin>>choiced;
if(choiced == 0)
return 0;
else if(choiced == 1)
{
system("cls");
cout<<"请输入最大递归深度："<<endl;
cin>>maxdepth;
cout<<"请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax"<<endl;
cin>>xmin>>xmax>>ymin>>ymax>>zmin>>zmax;
if(maxdepth>=0 || xmax>xmin || ymax>ymin || zmax>zmin || xmin>0 || ymin>0 ||zmin>0)
{
tmaxdepth=cal(maxdepth);
txm=(xmax-xmin)/tmaxdepth;
tym=(ymax-ymin)/tmaxdepth;
tzm=(zmax-zmin)/tmaxdepth;
createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
}
else
{
cout<<"输入错误！";
return 0;
}
}
else if(choiced == 2)
{
system("cls");
cout<<"先序遍历八叉树结果：\n";
i=1;
preOrder(rootNode);
cout<<endl;
system("pause");
}
else if(choiced == 3)
{
system("cls");
int dep = depth(rootNode);
cout<<"此八叉树的深度为"<<dep+1<<endl;
system("pause");
}
else if(choiced == 4)
{
system("cls");
cout<<"请输入您希望查找的点的坐标，顺序如下：x,y,z\n";
double x,y,z;
cin>>x>>y>>z;
times=0;
cout<<endl<<"开始搜寻该点……"<<endl;
find(rootNode,x,y,z);
system("pause");
}
else
{
system("cls");
cout<<"\n\n错误选择！\n";
system("pause");
}
}
}
代码在C-free下测试可用

热心网友

采用链式结构存储

声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com