c# - 四叉树和Kd树

我有一组不同位置的纬度和经度，也知道我当前位置的纬度和经度。我必须找出离当前位置最近的地方。

Kdtree 和四叉树中哪种算法最适合从一组纬度和经度中找出邻居位置？

一个比另一个有什么优势？

为了上述目的，我们如何在 C# 中实现这些算法？

最佳答案

比较空间索引技术我想将第三个技术引入我们的比较研究中，称为网格索引。为了理解四叉树，我想先进入网格索引。

什么是网格索引？

网格索引是一种基于网格的空间索引方法，其中研究区域像棋盘一样被划分为固定大小的瓦片(固定尺寸)。

使用网格索引，图块中的每个点都标有该图块编号，因此索引表可以为每个点提供一个标记，显示我们的编号所在的图块。

想象一下您需要在给定矩形中查找点的情况。
此查询分两步执行:

找到矩形重叠的瓦片，以及瓦片中的点(第一个过滤器)

在上面的步骤中找到实际位于我们矩形中的候选点。这需要使用点和矩形坐标准确地完成。(第二个过滤器)

第一个过滤器创建一组候选项，并防止测试我们研究区域中的所有点以逐个检查。

第二个过滤器是精确检查，使用直角坐标来测试候选人。

现在，看看上面图片中的瓷砖，如果瓷砖非常大或非常小会怎样？

例如，当瓷砖太大时，假设您有一个与您的研究区域大小相同的瓷砖，这只能制作一个瓷砖!所以第一个过滤器实际上是无用的，整个处理负载将由第二个过滤器负担。在这种情况下，第一个过滤器很快，而第二个过滤器非常慢。

现在想象图块非常小，在这种情况下，第一个过滤器非常慢，实际上它自己生成答案，而第二个过滤器很快。

确定瓷砖尺寸非常重要，直接影响性能，但如果您无法确定最佳瓷砖尺寸怎么办？如果您所在的区域同时具有备用和密集子区域怎么办？
是时候使用其他空间索引机制了，比如 R-Tree、KD-Tree 或 Quad-Tree!

什么是四叉树？

四叉树方法从一个覆盖整个研究区域的大块开始，将其除以两条水平和垂直线，得到四个相等的区域，即新的块，然后检查每个块，看它是否超过预先定义的阈值，点在其中。在这种情况下，瓷砖将再次使用水平和垂直分隔线分成四个相等的部分。该过程一直持续到不再有点数大于阈值的瓦片，这是一种递归算法。

所以在较密集的区域，当有备用点时，我们有较小的瓷砖和大瓷砖。

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

下图是一个平衡的KD-Tree，每条分割线都是一个中位数，将一个区域划分为两个点数大致相等的子区域。

结论:
如果您有一个分布良好的点，这在 map 中谈论地球的结构特征时并非如此，因为它们是随机的，但是当我们计划存储城市道路网络时是可以接受的。我会去网格索引。

如果您的资源有限(即汽车导航系统)，则需要实现 KD-Tree 或 Quad-Tree。每个都有自己的优点和缺点。

四叉树创建了很多空的子图块，因为即使我们的图块的整个数据可以放在四分之一中，每个图块也必须分为四个部分，所以其余的子图块被认为是多余的。(取一个看上面的四叉树图片)

四叉树有更简单的索引，可以更容易地实现。使用 Tile ID 访问 tile 不需要递归函数。

在二维 Kd-Tree 中，每个节点只有两个子节点或根本没有子节点，因此搜索 KD-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,0, 0, 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,%d\n",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,%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: %d\n", 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, 0, 0, 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;
}

关于c# - 四叉树和Kd树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42873508/

c# - 四叉树和Kd树

上一篇：c# - 如何使用 IEditableObject 对象在 WPF DataGrid 中执行单击复选框选择

下一篇：c# - 如何将 IdentityServer4 与 ASP.NET Microsoft Identity 的自定义密码验证结合使用