2
我有一套經緯度爲各種位置，也知道我的當前位置的經度和緯度。我必須找到從當前位置最近的地方。 哪一種算法最好從Kdtree和四叉樹中找出一組經緯度的鄰居位置？ 一個優於其他？ 你能否對此有所瞭解？ 另外，我們如何才能實現這些以c＃爲上述目的的算法？ 在此先感謝您的答案。四叉樹和Kd樹
Q
四叉樹和Kd樹
A
回答
1
我認爲在這種情況下，kd樹會比四叉樹做得更好，因爲當使用四叉樹來尋找最近的鄰居時，最接近的對象可能被放置在右邊的一個分區的另一邊節點。另一方面，Kd樹允許實現非常有效的最近鄰居搜索，儘管在保持平衡樹的同時插入和移除將更加困難。
3
比較空間索引技術我想把第三個比較研究稱爲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;
}
相關問題
- 1. 四叉樹和kd-tree之間的區別
- 2. 四叉樹性能
- 3. 構建四叉樹
- 4. 四叉樹刪除
- 5. 四叉樹遍歷
- 6. 遍歷四叉樹
- 7. 通用四叉樹
- 8. 平衡四叉樹
- 9. 四叉樹 - 多級分段樹
- 10. AVL樹的四叉樹相當於
- 11. KD樹，慢樹構建
- 12. 平衡KD樹
- 13. kd樹實現
- 14. KD樹在GLSL
- 15. 四叉樹物體移動
- 16. 四叉樹分解 - MATLAB
- 17. 如何紋理四叉樹
- 18. 無法構建四叉樹？
- 19. 四叉樹的遍歷
- 20. 純Python實現四叉樹
- 21. 重新排列四叉樹/八叉樹的數據
- 22. 在八叉樹/四叉樹中定位體素的性能
- 23. 如何處理R樹和四叉樹的重複點？
- 24. 優化Python KD樹搜索
- 25. KD樹 - 最近鄰算法
- 26. 建築kd樹在CUDA
- 27. 在android地圖上的四叉樹utils
- 28. 有多少片葉子有四叉樹？
- 29. 當代表使用四叉樹
- 30. python中有效的四叉樹實現