前一阵做实验 要用到R树 在网上找了好多代码 都不是很理想 不过最后在一篇博客上找到了一个很靠谱 而且简单易懂 清晰明了的代码 完成了R树的构建 我把原文的代码稍稍修饰了一下 并提取出我所需要的 即R树的构建 再加上我自己写的用R树查询KNN 已经调试过了 可以运行 代码如下
#include "stdafx.h"
#include "math.h"
#include <iostream>
#define Invalid_Rect(x) ((x).bound[0] > (x).bound[2])
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define Maxfill 3 //此处将叶子节点包含对象个数的最大值和R树分值的最大值都设为maxfill
#define Minfill (Maxfill/2) //如上的最小值
#define FALSE 0
#define TRUE 1
using namespace std;
//定义矩形框的四个界值
typedef struct RTreeMBR
{
float bound[4];
}RTreeMBR;
//定义R树结点分支的结构体
typedef struct RTreeBranch
{
RTreeMBR mbr;//分支所在的矩形框
struct RTreeNode* child;//分支指向的孩子结点
int leafchild; //若为叶子节点（即无孩子节点），存储对象（点）的ID。
}RTreeBranch;
//定义R树结点的结构体
typedef struct RTreeNode
{
int mbrcount;//结点矩形框的个数
int level;//结点的高度
RTreeBranch branch[Maxfill];//结点的分支
}RTreeNode;
//结点划分时的结构体
typedef struct RTreePartition
{
int partition[Maxfill+1];
int total;
int minfill;
int taken[Maxfill+1];//记录小矩形框是否被划分
int ncount[2]; //划分成两块的各自矩形框的个数
RTreeMBR cover[2];//划分成两块的各自总的矩形框覆盖
double area[2]; //划分成两块的各自面积
}RTreePartition;
//搜索R树时放入优先队列（堆）的结点的结构体
typedef struct Node
{
RTreeNode* RNode;
float data;
char type;
int ID;
}Node;
RTreeBranch BranchBuf[Maxfill+1];
int BranchCount;
RTreeMBR CoverSplit;
double CoverSplitArea;
RTreePartition Partition[1];
int length;
void RTreeSplitNode(RTreeNode *node, RTreeBranch br, RTreeNode **new_node);
//创建r-tree，初始化根
RTreeNode* RTreeCreate()
{
RTreeNode *root=new RTreeNode;
root->mbrcount=0;
root->level=0;
for (int i=0;i<Maxfill;i++)
{
root->branch[i].child=NULL;
}
return root;
}
//合并两个矩形框
RTreeMBR RTreeCombineRect( RTreeMBR rc1, RTreeMBR rc2 )
{
int i, j;
RTreeMBR new_rect;
for (i = 0; i < 2; i++)
{
new_rect.bound[i] = MIN(rc1.bound[i], rc2.bound[i]);
j = i + 2;
new_rect.bound[j] = MAX(rc1.bound[j], rc2.bound[j]);
}
return new_rect;
}
//求矩形框的面积
double RTreeRectSurfaceArea( RTreeMBR rc )
{
double sum = (double) 0;
sum=(rc.bound[2]-rc.bound[0])*(rc.bound[3]-rc.bound[1]);
return sum;
}
//初始化矩形框
void RTreeInitRect( RTreeMBR *rc)
{
int i;
for (i=0; i<4; i++)
rc->bound[i] = (double) 0;
}
//初始化一个分支的矩形框和孩子指针
static void _RTreeInitBranch( RTreeBranch &br )
{
RTreeInitRect(&br.mbr);
br.child = NULL;
}
//初始化一个r树结点的分支个数和层数以及分支
void RTreeInitNode( RTreeNode *node )
{
int i;
node->mbrcount = 0;
node->level = -1;
for (i = 0; i < Maxfill; i++)
_RTreeInitBranch(node->branch[i]);
}
//结点溢出时计算合并所有的矩形框
static void _RTreeGetBranches( RTreeNode *node, RTreeBranch br)
{
int i;
for (i=0;i<Maxfill;i++)
{
BranchBuf[i]=node->branch[i];
}
BranchBuf[Maxfill]=br;
BranchCount=Maxfill+1;
CoverSplit = BranchBuf[0].mbr;
for (i=1;i<Maxfill+1;i++)
{
CoverSplit = RTreeCombineRect(CoverSplit,BranchBuf[i].mbr);
}
CoverSplitArea = RTreeRectSurfaceArea(CoverSplit);
RTreeInitNode(node);
}
//将矩形框初始化
RTreeMBR RTreeNullRect(void)
{
RTreeMBR rc;
int i;
rc.bound[0] = (double) 1;
rc.bound[2] = (double)-1;
for (i=1; i<2; i++)
rc.bound[i] = rc.bound[i+2] = (double) 0;
return rc;
}
//初始化划分p的各属性值
static void _RTreeInitPart( RTreePartition *p, int maxrects, int minfill)
{
int i;
p->ncount[0] = p->ncount[1] = 0;
p->cover[0] = p->cover[1] = RTreeNullRect();
p->area[0] = p->area[1] = (double)0;
p->total = maxrects;
p->minfill = minfill;
for (i=0; i<maxrects; i++)
{
p->taken[i] = FALSE;
p->partition[i] = -1;
}
}
//将第i个矩形框分到第group组
static void _RTreeClassify(int i, int group, RTreePartition *p)
{
p->partition[i] = group;
p->taken[i] = TRUE;
if (p->ncount[group] == 0)
p->cover[group] = BranchBuf[i].mbr;
else
p->cover[group] = RTreeCombineRect(BranchBuf[i].mbr, p->cover[group]);
p->area[group] = RTreeRectSurfaceArea(p->cover[group]);
p->ncount[group]++;
}
//挑选出两组的首对矩形框（即合并起来浪费最大的）
static void _RTreePickSeeds(RTreePartition *p)
{
int i, j, seed0=0, seed1=0;
double worst, waste, area[Maxfill+1];
for (i=0; i<p->total; i++)
area[i] = RTreeRectSurfaceArea(BranchBuf[i].mbr);
worst = -CoverSplitArea - 1;
for (i=0; i<p->total-1; i++)
{
for (j=i+1; j<p->total; j++)
{
RTreeMBR one_rect;
one_rect = RTreeCombineRect(BranchBuf[i].mbr, BranchBuf[j].mbr);
waste = RTreeRectSurfaceArea(one_rect) - area[i] - area[j];
if (waste > worst)
{
worst = waste;
seed0 = i;
seed1 = j;
}
}
}
_RTreeClassify(seed0, 0, p);
_RTreeClassify(seed1, 1, p);
}
//进行划分
static void _RTreeMethodZero( RTreePartition *p, int minfill )
{
int i;
double biggestDiff;
int group, chosen=0, betterGroup=0;
_RTreeInitPart(p, BranchCount, minfill);//初始化划分p的各属性值
_RTreePickSeeds(p);//挑选出两组的首对矩形框（即合并起来浪费最大的）
while (p->ncount[0] + p->ncount[1] < p->total &&
p->ncount[0] < p->total - p->minfill &&
p->ncount[1] < p->total - p->minfill)
{
biggestDiff = (double)-1.;
for (i=0; i<p->total; i++)
{
if (!p->taken[i])
{
RTreeMBR r, rect_0, rect_1;
double growth0, growth1, diff;
r = BranchBuf[i].mbr;
rect_0 = RTreeCombineRect(r, p->cover[0]);
rect_1 = RTreeCombineRect(r, p->cover[1]);
growth0 = RTreeRectSurfaceArea(rect_0) - p->area[0];
growth1 = RTreeRectSurfaceArea(rect_1) - p->area[1];
diff = growth1 - growth0;
if (diff >= 0)
group = 0;
else
{
group = 1;
diff = -diff;
}
if (diff > biggestDiff)
{
biggestDiff = diff;
chosen = i;
betterGroup = group;
}
else if (diff==biggestDiff && p->ncount[group]<p->ncount[betterGroup])
{
chosen = i;
betterGroup = group;
}
}
}
_RTreeClassify(chosen, betterGroup, p);//将其余矩形框依次分组
}
/* if one group too full, put remaining rects in the other */
if (p->ncount[0] + p->ncount[1] < p->total)
{
if (p->ncount[0] >= p->total - p->minfill)
group = 1;
else
group = 0;
for (i=0; i<p->total; i++)
{
if (!p->taken[i])
_RTreeClassify(i, group, p);
}
}
}
//new一个新节点并初始化
RTreeNode *RTreeNewNode(void)
{
RTreeNode *node = new RTreeNode;
RTreeInitNode(node);
return node;
}
//将分支br插入到结点，没有分裂返回0，否则返回1
int RTreeAddBranch(RTreeBranch br, RTreeNode *node, RTreeNode **new_node)
{
int i;
if (node->mbrcount<Maxfill)
{
for (i=0;i<Maxfill;i++)
{
if (node->branch[i].child == NULL)
{
node->branch[i]=br;
node->mbrcount++;
break;
}
}
return 0;
}
RTreeSplitNode(node, br, new_node);
return 1;
}
//将缓存中的分支分别分配给结点n和q
static void _RTreeLoadNodes( RTreeNode *r, RTreeNode *q, RTreePartition *p)
{
int i;
for (i=0; i<p->total; i++)
{
if (p->partition[i] == 0)
{
RTreeAddBranch(BranchBuf[i], r, NULL);
}
else if (p->partition[i] == 1)
{
RTreeAddBranch(BranchBuf[i], q, NULL);
}
}
}
//分裂结点形成node和newnode
void RTreeSplitNode(RTreeNode *node, RTreeBranch br, RTreeNode **new_node)
{
RTreePartition *p;
int level;
level=node->level;
_RTreeGetBranches(node, br);//结点溢出时计算合并所有的矩形框
/* find partition */
p = &Partition[0];
/* Note: can't use MINFILL(n) below since node was cleared by GetBranches() */
//进行划分
_RTreeMethodZero(p, Minfill);
/* put branches from buffer into 2 nodes according to chosen partition */
//划分时产生的新节点
*new_node = RTreeNewNode();
(*new_node)->level = node->level = level;
_RTreeLoadNodes(node, *new_node, p);//将缓存中的分支分别分配给结点n和q
}
//挑选最合适的分支插入
int RTreePickBranch( RTreeMBR rc, RTreeNode *node)
{
RTreeMBR r;
int i, first_time = 1;
double increase, bestIncr=(double)-1, area, bestArea=0;
int best=0;
RTreeMBR tmp_rect;
for (i=0; i<Maxfill; i++)
{
if (node->branch[i].child)
{
r = node->branch[i].mbr;
area = RTreeRectSurfaceArea(r);
tmp_rect = RTreeCombineRect(rc, r);
increase = RTreeRectSurfaceArea(tmp_rect) - area;
if (increase < bestIncr || first_time)
{
best = i;
bestArea = area;
bestIncr = increase;
first_time = 0;
}
else if (increase == bestIncr && area < bestArea)
{
best = i;
bestArea = area;
bestIncr = increase;
}
}
}
return best;
}
//合并结点各个分支的矩形框
RTreeMBR RTreeNodeCover(RTreeNode *node)
{
int i, first_time=1;
RTreeMBR rc;
RTreeInitRect(&rc);
for (i = 0; i < node->mbrcount; i++)
{
if (first_time)
{
rc = node->branch[i].mbr;
first_time = 0;
}
else
{
rc = RTreeCombineRect(rc, node->branch[i].mbr);
}
}
return rc;
}
//插入矩形框，
static int _RTreeInsertRect( RTreeMBR rc, int tid, RTreeNode *node, RTreeNode **new_node, int level)
{
int i;
RTreeBranch b;
RTreeNode *n2;
if (node->level>level)
{
i = RTreePickBranch(rc, node);//挑选最适合的分支
if (!_RTreeInsertRect(rc, tid, node->branch[i].child, &n2, level))//递归挑选最适合的分支
{
/* child was not split */
node->branch[i].mbr = RTreeCombineRect(rc, node->branch[i].mbr);
return 0;
}
/* child was split */
node->branch[i].mbr = RTreeNodeCover(node->branch[i].child);
b.child = n2;
b.mbr = RTreeNodeCover(n2);
return RTreeAddBranch(b,node,new_node);
}
else if (node->level == level)
{
b.mbr=rc;
b.leafchild=tid;
return RTreeAddBranch(b,node,new_node);//将矩形框结点插进去
}
return 0;
}
//插入矩形框。若根分裂返回1.否则返回0
int RTreeInsertRect(RTreeMBR rc,int tid,RTreeNode *&root,int level)
{
RTreeNode *newroot;
RTreeNode *newnode;
RTreeBranch b;
if (_RTreeInsertRect(rc,tid,root,&newnode,level))
{
newroot = RTreeNewNode(); /* grow a new root, & tree taller */
newroot->level = root->level + 1;
b.mbr = RTreeNodeCover(root);
b.child = root;
RTreeAddBranch(b, newroot, NULL);
b.mbr = RTreeNodeCover(newnode);
b.child = newnode;
RTreeAddBranch(b, newroot, NULL);
root = newroot;
return 1;
}
return 0;
}
void HeapAdjust(Node H[30],int s,int m)
{
int j;
Node temp = H[s];
for (j = 2*s; j<=m; j*=2)
{
if (j<m && H[j].data > H[j+1].data)
{
j++;
}
if (temp.data <= H[j].data)
{
break;
}
else
{
H[s] = H[j];
s = j;
}
}
H[s] = temp;
}
Node DelHeap(Node H[30])
{
Node temp = H[1];
H[1]=H[length];
length--;
HeapAdjust(H,1,length);
return temp;
}
void InsertHeap(Node H[30], Node temp)
{
int i;
length++;
H[length]=temp;
for (i = length/2; i > 0; i/=2)
{
HeapAdjust(H,i,length);
if (H[i].data >= H[i/2].data && i/2>0)
{
break;
}
}
}
//计算点到矩形框的最短距离
double DistRect(RTreeMBR rc1,RTreeMBR rc2)
{
double x=rc1.bound[0];
double y=rc1.bound[1];
double xmin=rc2.bound[0];
double xmax=rc2.bound[2];
double ymin=rc2.bound[1];
double ymax=rc2.bound[3];
double dist,tempx,tempy;
if (x>=xmin && x<=xmax && y>=ymin && y<=ymax)//当点在矩形框内为0
{
return 0;
}
else if (x>=xmin && x<=xmax)
{
if (y>=ymax)
{
dist=y-ymax;
return dist;
}
else
{
dist=ymin-y;
return dist;
}
}
else if (y>=ymin && y<=ymax)
{
if (x>=xmax)
{
dist=x-xmax;
return dist;
}
else
{
dist=xmin-x;
return dist;
}
}
else
{
if (x>=xmax && y>=ymax)
{
tempx=pow((x-xmax),2);
tempy=pow((y-ymax),2);
dist=sqrt(tempx+tempy);
return dist;
}
else if (x>=xmax && y<=ymin)
{
tempx=pow((x-xmax),2);
tempy=pow((ymin-y),2);
dist=sqrt(tempx+tempy);
return dist;
}
else if (x<=xmin && y<=ymin)
{
tempx=pow((xmin-x),2);
tempy=pow((ymin-y),2);
dist=sqrt(tempx+tempy);
return dist;
}
else
{
tempx=pow((xmin-x),2);
tempy=pow((y-ymax),2);
dist=sqrt(tempx+tempy);
return dist;
}
}
}
//给定查询点，在R树上搜索最近的点
void RTreeSearch(RTreeNode *node, RTreeMBR rc)
{
int k=0;
float dist=0;
Node H[30];
Node node1,temp;
length=0;
for (int i=0;i<node->mbrcount;i++)
{
dist=DistRect(rc,node->branch[i].mbr);
if (node->level>0)
{
temp.data=dist;
temp.RNode=node->branch[i].child;
temp.type='N';
InsertHeap(H,temp);
}
else
{
temp.data=dist;
temp.ID=node->branch[i].leafchild;
temp.type='Y';
InsertHeap(H,temp);
}
}
while (length >0)
{
node1 = DelHeap(H);
if (node1.type == 'N')
{
for (int i=0;i<node1.RNode->mbrcount;i++)
{
dist=DistRect(rc,node1.RNode->branch[i].mbr);
if (node1.RNode->level>0)
{
temp.data=dist;
temp.RNode=node1.RNode->branch[i].child;
temp.type='N';
InsertHeap(H,temp);
}
else
{
temp.data=dist;
temp.ID=node1.RNode->branch[i].leafchild;
temp.type='Y';
InsertHeap(H,temp);
}
}
}
else
{
k++;
cout<<"据查询点第"<<k<<"近的点为："<<node1.ID<<" 距离为:"<<node1.data<<endl;
if (k == 3)
{
return;
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
//定义要插入的点，这里用矩形表示(两个对角点重合)
RTreeMBR rects[]=
{ {0,2,0,2},//xmin,ymin,xmax,ymax，表示点(x,y)=(0,2）
{1,2,1,2},
{3,4,3,4},
{3,5,3,5},
{4,6,4,6},
{1,3,1,3}
};
int msize = sizeof(rects) / sizeof(rects[0]);//要插入点的个数
RTreeNode *root;
root=RTreeCreate();//初始化根结点
for(int i=0;i<msize;i++)
{
RTreeInsertRect(rects[i],i,root,0); //(待插入点的矩形框，点的ID,R树的根，level)
}
RTreeMBR rect={5,6,5,6};//查询点的坐标（x,y）=(5,6)
RTreeSearch(root,rect);//搜索距查询点最近的点
return 0;
}
最后再贴上原博客的链接 <a target=_blank href="http://blog.csdn.net/ubuntu64fan/article/details/1898129">http://blog.csdn.net/ubuntu64fan/article/details/1898129</a> 里面很全 还有R树的删除等等之类的操作
