四叉树和Kd树

我有一套经纬度为各种位置，也知道我的当前位置的经度和纬度。我必须找到从当前位置最近的地方。哪一种算法最好从Kdtree和四叉树中找出一组经纬度的邻居位置？一个优于其他？你能否对此有所了解？另外，我们如何才能实现这些以c＃为上述目的的算法？在此先感谢您的答案。四叉树和Kd树

来源

2017-03-18 Kesiya Abraham

我认为在这种情况下，kd树会比四叉树做得更好，因为当使用四叉树来寻找最近的邻居时，最接近的对象可能被放置在右边的一个分区的另一边节点。另一方面，Kd树允许实现非常有效的最近邻居搜索，尽管在保持平衡树的同时插入和移除将更加困难。

来源

2017-03-18 11:15:03

比较空间索引技术我想把第三个比较研究称为R-tree。为了理解Quad-Tree，我想先进入R-tree。

什么是R-Tree？

R-Tree是一种基于网格的空间索引方法，将研究区域划分为固定尺寸的瓦片，如棋盘。

使用R-树，在瓦片中的每一个点都标记有瓦数，所以索引表可以为您提供的每个点显示，我们的数字在瓷砖的标签。

想象一下你需要在给定矩形中找到点的情况。此查询是在两个步骤中进行，基于R-树：

查找瓦片，所述矩形是重叠的砖，和点（第一过滤器）
查找在上述步骤中的候选点，实际上躺在我们的矩形。（第二个过滤器）

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

第二个过滤器是准确的检查，并使用矩形坐标来测试候选人。

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

当瓷砖太大时，例如，假设您有一个与您的学习区域大小相同的瓷砖，这只会形成一个瓷砖！所以第一个过滤器实际上是无用的，整个处理负荷将由第二个过滤器负担。在这种情况下，第一个过滤器很快，第二个过滤器非常慢。

现在设想瓷砖非常小，在这种情况下，第一个过滤器非常慢，实际上它会自行生成答案，而第二个过滤器很快。

确定瓷砖尺寸非常重要，并直接影响性能，但如果无法确定最佳瓷砖尺寸，该怎么办？如果你的地区有备用和密集的地区呢？这里是使用四叉树的时间！

什么是四叉树？

四叉树方法开始于一个覆盖整个研究区域的大瓦片，并将其分为两条水平线和垂直线以具有四个相等面积，这些是新瓦片，然后检查每个瓦片以查看它是否具有多于一个预先定义的阈值，点在其中。在这种情况下，再次使用水平和垂直分割线将瓦片分成四个相等的部分。该过程继续进行，直到没有更多的点数大于阈值，这是递归算法。

因此，在密集的地区，我们有更小的瓷砖和大瓷砖时有备用点。

什么是kd树？在KD-Tree中，如果一个区域的阈值点多于一个区域（可以使用其他标准），我们划分一个区域，使用（K-1）维度几何体完成划分，例如在3D树中，我们需要一个平面来划分空间，并且在2D-Tree中我们需要一条线来划分该区域。划分几何图形是迭代的和循环的，例如在三维树中，第一个分割平面是X轴对齐的平面，下一个分割平面是Y轴对齐，下一个是Z，循环继续为每个空间部分变为可接受（满足标准）

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

结论： 如果你有一个良好的分布点在谈论地图地球的结构特征时，这是不是这样的，因为他们是随机的，但是是可以接受的，当我们计划存储城市道路网络。我会去做一个R-tree索引。

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

四叉树创造了很多空分瓷砖的，因为每个瓦片已被分为四个部分，即使我们瓷砖的整个数据可以在一个季度契合，所以子片的其余部分是（看看上面的四叉树图片）
四叉树有更容易索引，可以更容易地实现。使用Tile ID访问tile不需要递归功能。
在二维Kd-Tree中，每个节点只有两个子节点或根本没有子节点，因此通过KD-Tree搜索本质上是一个二分查找。
更新四叉树比更新平衡的KD树要容易得多。

与上面的描述，我建议先从四叉树

这是四叉树是打算创建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; 
}

来源

2017-04-21 17:38:09 Zich

四叉树和Kd树

回答

相关问题