View CodeCPP | |
1 | cin>>choiced; |
View CodeCPP | |
1 | //定义BSP树节点类 |
View CodeCPP | |
1 | int i=1; |
View CodeCPP | |
1 | template<class T> |
/*
Author : 张聪
Date : 2008/05/01
Filename : bsptree.cpp
Platform : VC++ 2005
BSP树的实现
功能:
1、创建BSP树。
此BSP树为满树,即所有节点/叶子全部创建。
用户可以自定义此BSP树的深度和所处的三维场景中的位置。
注a:由于创建树时为满树创建,故层数太大时创建时间可能会比较久,请耐心等待。
注b:创建顺序为(1)切割平面左边的节点-(2)切割平面右边的节点-(1)-(2)……
2、先序遍历BSP树。
BSP树创建成功后用户可调用此子模块查看此BSP树,会显示每个结点的编号,值和在场景中的坐标。
3、查看BSP树的深度。
*/
#include <iostream>
using namespace std;
//定义BSP树节点类
template<class T>
struct BSPTreeNode
{
T data; //节点数据
T xmin,xmax; //节点坐标,即六面体各顶点的坐标
T ymin,ymax;
T zmin,zmax;
BSPTreeNode <T> *left,*right; //该节点的个子结点,即左右两个子六面体节点
BSPTreeNode //节点类
(T nodeValue = T(),
T xminValue = T(),T xmaxValue = T(),
T yminValue = T(),T ymaxValue = T(),
T zminValue = T(),T zmaxValue = T(),
BSPTreeNode<T>* left_Node = NULL,
BSPTreeNode<T>* right_Node = NULL )
:data(nodeValue),
xmin(xminValue),xmax(xmaxValue),
ymin(yminValue),ymax(ymaxValue),
zmin(zminValue),zmax(zmaxValue),
left(left_Node),
right(right_Node){}
};
//创建BSP树
int scale = -1; //切割平面属性初始化,根据切割平面属性决定当前切割的面是与X轴垂直的平面,还是Y轴的或Z轴的
template <class T>
void createBSPTree(BSPTreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
cout<<"处理中,请稍候……"<<endl;
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
scale++; //每递归一次就将切割平面属性+1,使下一次切割的平面更改一下
if(3==scale) scale=0; //如果切割属性达到峰值,则初始化
if(maxdepth>=0)
{
root=new BSPTreeNode<T>();
root->data = 9; //为节点赋值,可以存储节点信息,如物体可见性。由于是简单实现BSP树功能,简单赋值为。
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=(zmax-zmin)/2;
//递归创建子树
if(0==scale) //切割属性为,沿与X轴垂直的平面切割
{
createBSPTree(root->left,maxdepth,xmin,xmax-xm,ymin,ymax,zmin,zmax);//根据当前切割平面的属性决定其子结点的坐标
createBSPTree(root->right,maxdepth,xmax-xm,xmax,ymin,ymax,zmin,zmax);
}
else if(1==scale) //切割属性为,沿与Y轴垂直的平面切割
{
createBSPTree(root->left,maxdepth,xmin,xmax,ymin,ymax-ym,zmin,zmax);//根据当前切割平面的属性决定其子结点的坐标
createBSPTree(root->right,maxdepth,xmin,xmax,ymax-ym,ymax,zmin,zmax);
}
else if(2==scale) //切割属性为,沿与Z轴垂直的平面切割
{
createBSPTree(root->left,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax-zm);//根据当前切割平面的属性决定其子结点的坐标
createBSPTree(root->right,maxdepth,xmin,xmax,ymin,ymax,zmax-zm,zmax);
}
}
}
int i=1;
//先序遍历BSP树
template <class T>
void preOrder( BSPTreeNode<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->left);
preOrder(p->right);
cout<<endl;
}
}
//求BSP树的深度
template<class T>
int depth(BSPTreeNode<T> *& p)
{
if(p == NULL)
return -1;
int h = depth(p->left);
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;
}
//main函数
int main ()
{
BSPTreeNode<double> * rootNode = NULL;
int choiced = 0;
int maxdepth=0;
while(true)
{
double xmin,xmax,ymin,ymax,zmin,zmax;
system("cls");
cout<<"请选择操作:\n";
cout<<"1.创建BSP树 2.先序遍历BSP树\n";
cout<<"3.查看树深度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)
{
scale = -1; //切割平面属性初始化
createBSPTree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
}
else
{
cout<<"输入错误!";
return 0;
}
}
else if(choiced == 2)
{
system("cls");
cout<<"先序遍历BSP树结果:\n";
i=1;
preOrder(rootNode);
cout<<endl;
system("pause");
}
else if(choiced == 3)
{
system("cls");
int dep = depth(rootNode);
cout<<"此BSP树的深度为"<<dep+1<<endl;
system("pause");
}
else
{
system("cls");
cout<<"\n\n错误选择!\n";
system("pause");
}
}
}
联系客服