kdtree.h

处理网格数据点的KDTREE数据结构程序

#include <iostream>
#include <math.h>
#include <osg/array>

//KD树类，创建一棵K-D树，创建，查找，插入节点，前序遍历输出


//KDTree节点，包含一个VEC3，保存坐标，指向左子树，右子树的指针，key指示当前节点的x-y方向
typedef struct KDTreeNode
{
	/*Point p;*/
	osg::Vec3 p;
	struct KDTreeNode *l;
	struct KDTreeNode *r;  
	int key;
}*kdt;


//类KDTree
class KDTree
{
private:
	//根节点
	int kkk;
	kdt root;
	osg::Vec3Array* temparray;
public:
	//构造函数，根节点赋值NULL
	KDTree():root(NULL){temparray=new osg::Vec3Array;kkk=0;};
	//创建树
	kdt CreateSubTree(osg::Vec3Array *p,int low,int high,int k);
	//查找树中是否包含坐标（x,y）的节点
	bool SearchKDT(kdt t,float x,float y,int real,kdt f,kdt *p);
	//向树中插入vec3类型的值e
	int InsertKDT(kdt *t,osg::Vec3 e);
	//show是创建一棵树的主要创建函数
	int show(osg::Vec3Array *pa,int low,int high,int k);
	//前序遍历树
	osg::Vec3Array* PreOrderTraverse(kdt t);
	
	//以下为快速排序算法的各个函数，在InsertKDT函数中使用，分别对X方向和Y方向快速排序
	void exchange(osg::Vec3 *p1,osg::Vec3 *p2);
	int partitionX(osg::Vec3Array *pa,int p,int r);
	int partitionY(osg::Vec3Array *pa,int p,int r);
	void quick_sortX(osg::Vec3Array *pa,int p,int r);
	void quick_sortY(osg::Vec3Array *pa,int p,int r);
};