四叉树和Kd树 [英] Quad tree and Kd tree
问题描述
我在各个位置都有一组经度和纬度，并且也知道我当前位置的经度和纬度.我必须从当前位置找出最近的地方.
I have a set of latitude and longitude for various locations and also know the latitude and longitude of my current location. I have to find out the nearest places from current location.
- 从Kdtree和Quadtree中哪种算法是最好的算法，以便从经度和纬度集中找出相邻的位置?
- 一个人比另一个人有什么优势?
- 出于上述目的，我们如何在C#中实现这些算法?
推荐答案
比较空间索引技术我想将第3种方法引入我们的比较研究中，这称为网格索引.为了理解四叉树，我想先进入网格索引.
Comparing spatial indexing techniques I would like to bring a 3rd one into our comparative study which is called Grid indexing. and in order to understand Quad-Tree I would like to go into Grid indexing first.
什么是网格索引?
网格索引是一种基于网格的空间索引方法，其中，将研究区域划分为固定大小的图块(固定尺寸)，如国际象棋棋盘.
Grid indexing is a grid-base spatial indexing method in which the study area is divided into fixed size tiles (fixed dimensions) like chess board.
使用Grid索引，一个图块中的每个点都标记有该图块编号，因此索引表可以为您提供每个点的标签，以显示我们的编号所属的图块.
Using Grid index, every point in a tile are tagged with that tile number, so the Index table could provide you a tag for each point showing the tile which our number falls in.
想象一下您需要在给定矩形中查找点的情况.该查询分两个步骤执行:
Imagine a situation in which you need to find points in a given rectangle. This query is performed in two steps :
- 找到矩形重叠的图块以及图块中的点(第一个过滤器)
- 在上述步骤中找到实际上位于矩形中的候选点.这需要使用点和矩形坐标精确地完成.(第二个过滤器)
第一个过滤器会创建一组候选项，并阻止依次检查我们研究区域中的所有点.
The first filter creates a set of candidates and prevents to test all points in our study area to be checked one after the other.
第二个过滤器是准确的检查，并使用矩形坐标来测试候选对象.
The second filter is the accurate check and uses rectangle coordinates to test the candidates.
现在，看看上图中的磁贴，如果磁贴太大或很小，会发生什么?
Now, Take a look at the tiles in above pictures, what happens if the tiles are very big or very Small?
例如，当磁贴太大时，假设您有一个与您的学习区域大小相等的磁贴，那么只能制作一个磁贴！因此，第一个过滤器实际上是无用的，整个处理负荷将由第二个过滤器负担.在这种情况下，第一个过滤器速度很快，第二个过滤器速度很慢.
When the tiles are too big, for example assume that you have a tile with equal size of your study area, which makes only one tile! so the first filter is practically useless, the whole processing load will be burden by the second filter. In this case the first filter is fast and the second filter is very slow.
现在想象一下，瓦片很小，在这种情况下，第一个过滤器非常慢，实际上它会自行生成答案，而第二个过滤器很快.
Now imagine that the tiles are very small, in this case the first filter is very slow and practically it generates the answer it self, and the second filter is fast.
确定图块大小非常重要，并且会直接影响性能，但是如果您无法确定最佳的图块尺寸怎么办?如果您所在的区域同时具有备用和密集子区域，该怎么办?现在是时候使用其他空间索引机制，例如R-Tree，KD-Tree或Quad-Tree！
Determining the tile size is very important and affects the performance directly but what if you can not determine the best tile dimension? what if you you area has both spare and dense sub-areas? Here it is the time to use other spatial indexing mechanisms like R-Tree, KD-Tree or Quad-Tree!
什么是四叉树?
Quad Tree方法从覆盖整个研究区域的大图块开始，然后将其划分为两条水平线和垂直线，以得到四个相等的面积(即新图块)，然后检查每个图块以查看其是否大于预定义图块.定义的阈值，指向其中.在这种情况下，将再次使用水平和垂直分隔线将图块划分为四个相等的部分.这个过程一直持续到不再有点数大于阈值的图块为止，这是一种递归算法.
Quad Tree method starts with a big tile that covers whole study area,and divides it by two horizontal and vertical lines to have four equal area which are new tiles and then inspect each tile to see if it has more than a pre-defined threshold, points in it. in this case the tile will be divided into four equal parts using a horizontal and a vertical dividing lines,again. The process continues till there would be no more tile with number of points bigger than threshold, which is a recursive algorithm.
因此，在较密集的区域中，拥有备用点时，我们会使用较小的瓷砖和较大的瓷砖.
So in denser areas we have smaller tiles and big tiles when having spare points.
什么是KD树?在KD-Tree中，如果一个区域中有多个阈值点(可以使用其他标准)，则我们将其划分为一个(K-1)尺寸的几何图形，例如在3D-Tree中，我们需要一个平面来划分空间，在2D树中，我们需要一条线来划分区域.划分几何是迭代的和循环的，例如在3D树中，第一个划分平面是X轴对齐的平面，下一个划分平面是Y轴对齐的，下一个是Z的，每个空间部分的循环都可以接受(满足条件)
What is KD-Tree? In KD-Tree, we divide an area if it has more than a threshold points in it (other criterias can be used) dividing is done using a (K-1) dimension geometry, for example in a 3D-Tree we need a plane to divide the space, and in a 2D-Tree we need a line to divide the area. Dividing geometry is iterative and cyclic, for example in a 3D-Tree, the first splitting plane is a X axis aligned plane and the next dividing plane is Y axis aligned and the next is Z, the cycle continue for each space parts to become acceptable(satisfy the criteria)
下图显示了一个平衡的KD树，每条分界线都是一个中位数，将一个区域划分为两个具有大约相等点数的子区域.
The following picture shows a balanced KD-Tree that each dividing line is a median, that divides an area into two sub-area with approximately equal number of points.
结论:如果您的点分布均匀，而在地图中谈论地球的结构特征时并非如此，则原因是它们是随机的，但在我们计划存储城市道路网络时是可以接受的.我会去网格索引.
Conclusion : If you have a well-distributed points which is not the case when talking about structural features of earth in a map, cause they are random, but is acceptable when we plan to store a city roads network. I would go for a Grid indexing.
如果资源有限(例如汽车导航系统)，则需要实施KD-Tree或Quad-Tree.每个人都有自己的优点和缺点.
If you have a limited resource(i.e. Car navigation Systems) you need to implement KD-Tree or Quad-Tree. Each has its own pros and cons.
- Quad-Tree创建了许多空的子图块，因为即使我们的图块的整个数据可以容纳四分之一，每个图块也必须分为四个部分，所以其余的子图块被认为是多余的.(看看上面的四叉树图片)
- Quad-Tree的索引更容易实现，并且可以更轻松地实现.使用图块ID访问图块不需要递归功能.
- 在二维Kd-树中，每个节点只有两个子节点或根本没有子节点，因此通过KD-Tree进行搜索本质上是 binary搜索.
- 更新四叉树比更新平衡的KD树要容易得多.
基于以上描述，我建议从四叉树开始
这是四叉树的示例代码，打算创建5000个随机点.
Here it is a sample code for quad-tree that intend to create 5000 random point.
#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;
}
这篇关于四叉树和Kd树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
