四叉樹和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樹

回答

相關問題