比较空间索引技术 我想将第三种技术带入我们的比较研究中，称为网格索引。为了理解四叉树，我想首先了解网格索引。
什么是网格索引？
网格索引是一种基于网格的空间索引方法，其中研究区域像棋盘一样被划分为固定大小的图块（固定尺寸）。
使用网格索引，图块中的每个点都标有该图块编号，因此索引表可以为每个点提供一个标签，显示我们的数字所在的图块。
想象一下您需要在给定矩形中查找点的情况。
该查询分两步执行：
- 找到矩形重叠的图块，以及图块中的点（第一个过滤器）
- 在上述步骤中找到实际位于矩形中的候选点。这需要使用点和矩形坐标准确地完成。（第二个过滤器）
第一个过滤器创建一组候选点，并防止依次测试我们研究区域中要检查的所有点。
第二个过滤器是精确检查，使用直角坐标来测试候选人。
现在，看看上面图片中的瓷砖，如果瓷砖很大或很小会发生什么？
例如，当瓷砖太大时，假设您有一块与学习区域大小相同的瓷砖，这样就只剩下一块瓷砖了！所以第一个过滤器实际上没什么用，整个处理负载将由第二个过滤器承担。在这种情况下，第一个过滤器很快，第二个过滤器非常慢。
现在想象一下图块非常小，在这种情况下，第一个过滤器非常慢，实际上它自己生成答案，而第二个过滤器很快。
确定瓦片尺寸非常重要，直接影响性能，但是如果无法确定最佳瓦片尺寸怎么办？如果您所在的区域既有空闲子区域又有密集子区域怎么办？
现在是时候使用其他空间索引机制了，比如 R 树、KD 树或四叉树！
什么是四叉树？
四叉树方法从覆盖整个研究区域的大图块开始，然后将其除以两条水平线和垂直线以得到四个相等的区域，这些区域是新图块，然后检查每个图块以查看其是否超过预定义的阈值，其中的点。在这种情况下，瓷砖将再次使用水平和垂直分割线分为四个相等的部分。这个过程一直持续到不再有点数大于阈值的图块为止，这是一种递归算法。
因此，在较密集的区域，当有空闲点时，我们会使用较小的瓷砖和较大的瓷砖。
什么是KD树？
在 KD 树中，如果一个区域中的点超过阈值（可以使用其他标准），则我们会对其进行划分，划分是使用 (K-1) 维几何体完成的，例如在 3D 树中，我们需要一个平面来划分空间，在二维树中我们需要一条线来划分区域。
划分几何体是迭代和循环的，例如在 3D 树中，第一个划分平面是 X 轴对齐的平面，下一个划分平面是 Y 轴对齐的，下一个是 Z，循环继续使每个空间部分变得可接受（满足条件）
下图是一个平衡的KD树，每条分割线都是一个中位数，它将一个区域划分为两个点数大致相等的子区域。
结论 ：如果您有一个分布均匀的点，那么在地图中讨论地球的结构特征时情况并非如此，因为它们是随机的，但当我们计划存储城市道路网时是可以接受的。我会选择网格索引。
如果您的资源有限（即汽车导航系统），您需要实现 KD 树或四叉树。每个都有自己的优点和缺点。
- 四叉树创建了很多空的子图块，因为即使我们图块的整个数据可以容纳四分之一，每个图块也必须分为四个部分，所以其余的子图块被认为是多余的。（取一个看上面的四叉树图片）
- 四叉树有更容易的索引，并且可以更容易地实现。使用图块 ID 访问图块不需要递归函数。
- 在二维 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;
}
