c# – 四叉树和Kd树

什么是R-Tree？

R-Tree是一种基于网格的空间索引方法,其中研究区域被划分为具有固定尺寸的棋盘,如棋盘.

使用R-Tree,图块中的每个点都标记有该图块编号,因此Index表可以为每个点提供一个标记,显示我们的编号所在的图块.

想象一下,您需要在给定矩形中找到点.
此查询分两步执行,使用R-tree：

>找到矩形重叠的切片,以及切片中的点(第一个过滤器)
>在上面的步骤中找到实际位于矩形中的候选点.这需要使用点和矩形坐标精确完成.(第二个过滤器)

第一个过滤器创建一组候选项,并阻止测试我们的研究区域中的所有点一个接一个地进行检查.

第二个过滤器是精确检查并使用矩形坐标来测试候选者.

现在,看看上面图片中的瓷砖,如果瓷砖非常大或非常小,会发生什么？

当瓷砖太大时,例如假设您的研磨区域具有相同大小的瓷砖,这只能制作一个瓷砖！所以第一个过滤器实际上是无用的,整个处理负荷将是第二个过滤器的负担.在这种情况下,第一个过滤器很快,第二个过滤器很慢.

现在想象一下,瓷砖非常小,在这种情况下,第一个过滤器非常慢,实际上它会自动生成答案,第二个过滤器很快.

确定图块大小非常重要并直接影响性能,但如果无法确定最佳图块尺寸会怎样？如果你所在地区有备用和密集的子区域怎么办？
这是使用Quad-Tree的时候了！

什么是Quad-Tree？

Quad Tree方法以覆盖整个研究区域的大块开始,并将其除以两条水平和垂直线以具有四个相等的区域,这些区域是新的区块,然后检查每个区块以查看它是否具有超过预定义的阈值,其中的一点.在这种情况下,瓷砖将再次使用水平和垂直分割线分成四个相等的部分.该过程继续进行,直到不再存在具有大于阈值的点数的瓦片,这是递归算法.

所以在更密集的区域,当有备用点时,我们有更小的瓷砖和大瓷砖.

什么是KD-Tree？
在KD-Tree中,如果区域中有一个以上的阈值点(可以使用其他标准),我们将区域划分为使用(K-1)维度几何进行划分,例如在3D树中我们需要一个平面划分空间,在二维树中我们需要一条线来划分区域.
划分几何是迭代和循环的,例如在3D树中,第一个分割平面是X轴对齐平面,下一个分割平面是Y轴对齐,下一个是Z,每个空间部分的循环继续变为可接受(满足标准)

下图显示了一个平衡的KD树,每条分界线是一个中间值,它将一个区域划分为两个具有大致相同点数的子区域.

结论：
如果你有一个分布均匀的点,而在地图中谈论地球的结构特征时并非如此,因为它们是随机的,但在我们计划存储城市道路网时是可以接受的.我会去做一个R树索引.

如果您的资源有限(即汽车导航系统),则需要实现KD树或四叉树.每个人都有自己的优点和缺点.

> Quad-Tree创建了许多空子图块,因为即使我们的图块的整个数据可以适合四分之一,每个图块也必须分成四个部分,因此其余的子图块被认为是多余的.看看上面的Quad-Tree图片)
> Quad-Tree具有更容易的索引,可以更容易实现.访问具有Tile ID的磁贴不需要递归函数.
>在二维Kd树中,每个节点只有两个子节点或根本没有子节点,因此搜索KD树本质上是二分搜索.
>更新Quad-Tree比更新平衡KD树要容易得多.

根据上面的描述,我建议从Quad-Tree开始

这是一个四叉树的示例代码,打算创建5000个随机点.

#include<stdio.h>
#include<stdlib.h>
//Removed windows-specific header and functions

//-------------------------------------
// STRUCTURES
//-------------------------------------
struct Point
{
    int x;
    int y;
};


struct Node
{
    int posX;
    int posY;
    int width;
    int height;
    Node *child[4];         //Changed to Node *child[4] rather than Node ** child[4]
    Point pointArray[5000];
};
//-------------------------------------
// DEFINITIONS
//-------------------------------------

void BuildQuadTree(Node *n);
void PrintQuadTree(Node *n,int depth = 0);
void DeleteQuadTree(Node *n);
Node *BuildNode(Node *n,Node  *nParent,int index);

//-------------------------------------
// FUNCTIONS
//-------------------------------------

void setnode(Node *xy,int x,int y,int w,int h)
{
    int i;
    xy->posX = x;
    xy->posY = y;
    xy->width= w;
    xy->height= h;
    for(i=0;i<5000;i++)
    {
        xy->pointArray[i].x=560;
        xy->pointArray[i].y=560;
    }
    //Initialises child-nodes to NULL - better safe than sorry
    for (int i = 0; i < 4; i++)
        xy->child[i] = NULL;
}
int randn()
{
    int a;
    a=rand()%501;
    return a;
}

int pointArray_size(Node *n)
{
    int m = 0,i;
    for (i = 0;i<=5000; i++)
        if(n->pointArray[i].x <= 500 && n->pointArray[i].y <= 500)
            m++;
    return (m + 1);
}
//-------------------------------------
// MAIN
//-------------------------------------
int main()
{
    // Initialize the root node
    Node * rootNode = new Node;     //Initialised node
    int i,x[5000],y[5000];
    FILE *fp;
    setnode(rootNode,500,500);


    // WRITE THE RANDOM POINT FILE  
    fp = fopen("POINT.C","w");

    if ( fp == NULL )
    {
        puts ( "Cannot open file" );
        exit(1);
    }
    for(i=0;i<5000;i++)
    {
        x[i]=randn();
        y[i]=randn();
        fprintf(fp,"%d,%dn",x[i],y[i]);
    }
    fclose(fp);

    // READ THE RANDOM POINT FILE AND ASSIGN TO ROOT Node
    fp=fopen("POINT.C","r");
    for(i=0;i<5000;i++)
    {
        if(fscanf(fp,%d",&x[i],&y[i]) != EOF)
        {
            rootNode->pointArray[i].x=x[i];
            rootNode->pointArray[i].y=y[i];
        }
    }

    fclose(fp);

    // Create the quadTree
    BuildQuadTree(rootNode);
    PrintQuadTree(rootNode);    //Added function to print for easier debugging
    DeleteQuadTree(rootNode);

    return 0;
}

//-------------------------------------
// BUILD QUAD TREE
//-------------------------------------
void BuildQuadTree(Node *n)
{
    Node * nodeIn = new Node;   //Initialised node

    int points = pointArray_size(n);

    if(points > 100)
    {
        for(int k =0; k < 4; k++)
        {
            n->child[k] = new Node;     //Initialised node
            nodeIn = BuildNode(n->child[k],n,k);
            BuildQuadTree(nodeIn);
        }
    }
}
//-------------------------------------
// PRINT QUAD TREE
//-------------------------------------
void PrintQuadTree(Node *n,int depth)
{
    for (int i = 0; i < depth; i++)
        printf("t");

    if (n->child[0] == NULL)
    {
        int points = pointArray_size(n);
        printf("Points: %dn",points);
        return;
    }
    else if (n->child[0] != NULL)
    {
        printf("Children:n");
        for (int i = 0; i < 4; i++)
            PrintQuadTree(n->child[i],depth + 1);
        return;
    }
}
//-------------------------------------
// DELETE QUAD TREE
//-------------------------------------
void DeleteQuadTree(Node *n)
{
    if (n->child[0] == NULL)
    {
        delete n;
        return;
    }
    else if (n->child[0] != NULL)
    {
        for (int i = 0; i < 4; i++)
            DeleteQuadTree(n->child[i]);
        return;
    }
}
//-------------------------------------
// BUILD NODE
//-------------------------------------
Node *BuildNode(Node *n,Node *nParent,int index)
{
    int numParentPoints,i,j = 0;

    // 1) Creates the bounding box for the node
    // 2) Determines which points lie within the box

    /*
     Position of the child node,based on index (0-3),is determined in this order:
     | 1 | 0 |
     | 2 | 3 |
     */

    setnode(n,0);

    switch(index)
    {
        case 0: // NE

            n->posX = nParent->posX+nParent->width/2;
            n->posY = nParent->posY+nParent->height/2;
            break;

        case 1: // NW

            n->posX = nParent->posX;
            n->posY = nParent->posY+nParent->height/2;
            break;

        case 2: // SW

            n->posX = nParent->posX;
            n->posY = nParent->posY;
            break;

        case 3: // SE

            n->posX = nParent->posX+nParent->width/2;
            n->posY = nParent->posY;
            break;

    }

    // Width and height of the child node is simply 1/2 of the parent node's width and height
    n->width = nParent->width/2;
    n->height = nParent->height/2;

    // The points within the child node are also based on the index,similiarily to the position
    numParentPoints = pointArray_size(nParent);

    switch(index)
    {
        case 0: // NE
            for(i = 0; i < numParentPoints-1; i++)
            {
                // Check all parent points and determine if it is in the top right quadrant
                if(nParent->pointArray[i].x<=500 && nParent->pointArray[i].x > nParent->posX+nParent->width/2 && nParent->pointArray[i].y > nParent->posY + nParent->height/2 && nParent->pointArray[i].x <= nParent->posX + nParent->width && nParent->pointArray[i].y <= nParent->posY + nParent-> height)
                {
                    // Add the point to the child node's point array
                    n->pointArray[j].x = nParent ->pointArray[i].x;
                    n->pointArray[j].y = nParent ->pointArray[i].y;
                    j++;
                }
            }
            break;
        case 1: // NW
            for(i = 0; i < numParentPoints-1; i++)
            {
                // Check all parent points and determine if it is in the top left quadrant
                if(nParent->pointArray[i].x<=500 && nParent->pointArray[i].x > nParent->posX && nParent->pointArray[i].y > nParent->posY+ nParent-> height/2 && nParent->pointArray[i].x <= nParent->posX + nParent->width/2 && nParent->pointArray[i].y <= nParent->posY + nParent->height)
                {
                    // Add the point to the child node's point array
                    n->pointArray[j].x = nParent ->pointArray[i].x;
                    n->pointArray[j].y = nParent ->pointArray[i].y;
                    j++;
                }
            } 
            break;
        case 2: // SW
            for(i = 0; i < numParentPoints-1; i++)
            {
                // Check all parent points and determine if it is in the bottom left quadrant
                if(nParent->pointArray[i].x<=500 && nParent->pointArray[i].x > nParent->posX && nParent->pointArray[i].y > nParent->posY && nParent->pointArray[i].x <= nParent->posX + nParent->width/2 && nParent->pointArray[i].y <= nParent->posY + nParent->height/2)
                {   
                    // Add the point to the child node's point array
                    n->pointArray[j].x = nParent ->pointArray[i].x;
                    n->pointArray[j].y = nParent ->pointArray[i].y;
                    j++;
                }
            }
            break;

        case 3: // SE
            for(i = 0; i < numParentPoints-1; i++)
            {
                // Check all parent points and determine if it is in the bottom right quadrant
                if(nParent->pointArray[i].x<=500 && nParent->pointArray[i].x > nParent->posX +  nParent->width/2 && nParent->pointArray[i].y > nParent->posY && nParent->pointArray[i].x <= nParent->posX + nParent->width && nParent->pointArray[i].y <= nParent->posY + nParent->height/2)
                {
                    // Add the point to the child node's point array
                    n->pointArray[j].x = nParent ->pointArray[i].x;
                    n->pointArray[j].y = nParent ->pointArray[i].y;
                    j++;
                }
            }
            break;

    }
    return n;
}