照片馬賽克網絡應用程序。 KD-tree

上個月我一直在photomosaic網站上工作。我使用PHP構建了所有東西，並且我的工作非常棒。我唯一不喜歡的就是執行時間。由於線性比較搜索，我認爲這太長了。所以我一直在問如何改善我的搜索時間，大多數人指出我的KD樹的方向，這將使K最近鄰居更快。照片馬賽克網絡應用程序。 KD-tree

所以我一直在找KD樹，我知道如何手動構建這樣一棵樹。現在我想編寫這個代碼，當然，我只能找到用於C++和java的庫。由於我只熟悉PHP，我一直試圖自己做，但這並不像我想象的那麼容易。

•我面臨的問題是如何存儲所有內容。當我得到所有點的第一個數組時，我會把它吐到3塊。左分支，節點和右分支。當然，我會對左側分支做同樣的處理，直到我再也不能分割了，當然我通過軸（XYZ）循環。但是，我如何將所有正確的分支存儲在數組中？或者當我準備好使用它們時再計算它們？

•我想知道的另一件事是爲什麼沒有PHP KD-tree腳本是因爲PHP不是這份工作的正確語言？

這就是我到目前爲止所得到的。

該函數計算隨機顏色（RGB），我用它來測試其餘的顏色。

<?php 
function randomiser($number){ 

    if($number <= 0){ 
     echo 'Error: The input of randomiser() is less than or equal to zero !!'; 
     return FALSE;   
    }else{ 
     $R = array(); 
     $G = array(); 
     $B = array(); 

     for($x = 1; $x <= $number; $x++){ 
      $r = rand(1, 255); 
      $g = rand(1, 255); 
      $b = rand(1, 255); 

      $rgb['pic ' . $x]['R'] = $r; 
      $rgb['pic ' . $x]['G'] = $g; 
      $rgb['pic ' . $x]['B'] = $b;  
     } 
    } 
return $rgb; 
} 
?>

此功能排序上的特定鍵的多維數組（默認爲R）

<?php 
function sorter(&$array, $key = 'R'){ 

    if(!is_array($array)){ 
     echo 'Error: The input of sorter() is not an array !!<br>'; 
     return FALSE;   
    }else{ 
     uasort($array, function ($a, $b) use ($key){ 
      return strnatcmp($a[$key], $b[$key]); 
     }); 
    } 
} 
?>

此類分割陣列中的左分支，節點和右分支。

<?php 
class splitting { 

    public $left; 
    public $node; 
    public $right; 

    function __construct($array){ 

     if(!is_array($array)){ 
      echo 'Error: The input of splitter() is not an array !!<br>'; 
      return FALSE;   
     }else{ 
      $number = count($array); 
      $median = round($number/2) - 1; 

      $this->left = array_slice($array, 0, $median); 
      $this->node = array_slice($array, $median, 1); 
      $this->right = array_slice($array, $median+1); 
     } 
    } 
} 
?>

來源

2012-12-18 Php Peter

你需要存儲指向離開了$ $和右側的變量不是一個數組，或者您需要使用的任何變量的樹。如果kd樹太複雜，我也會研究一棵r樹。一棵r-樹將平面分割成4條邊，即真正的2 euklidian維數，kd-tree只是一棵二叉樹。然後你需要一個變量$有效載荷或者其他東西來備份中位數。

不，你也可以找到php樹的例子。這裏是一個例子：http://blog.sandfox.co.uk/2012/09/10/php-kdtree/。你也可以在php中查找我的kart-trie實現。它也使用OO和節點以及邊緣類。這裏是一個腳本，用於將光照貼圖包裝到http://www.blackpawn.com/texts/lightmaps/default.html的kd樹中。

struct Node 
{ 
    Node* child[2] 
    Rectangle rc 
     int imageID 
} 

Node* Node::Insert(const Image& img) 
     if we're not a leaf then 
     (try inserting into first child) 
     newNode = child[0]->Insert(img) 
     if newNode != NULL return newNode 

(no room, insert into second) 
     return child[1]->Insert(img) 
    else 
(if there's already a lightmap here, return) 
if imageID != NULL return NULL 

(if we're too small, return) 
if img doesn't fit in pnode->rect 
    return NULL 

(if we're just right, accept) 
if img fits perfectly in pnode->rect 
    return pnode 

(otherwise, gotta split this node and create some kids) 
pnode->child[0] = new Node 
pnode->child[1] = new Node 

(decide which way to split) 
dw = rc.width - img.width 
dh = rc.height - img.height 

if dw > dh then 
    child[0]->rect = Rectangle(rc.left, rc.top, 
           rc.left+width-1, rc.bottom) 
    child[1]->rect = Rectangle(rc.left+width, rc.top, 
           rc.right, rc.bottom) 
else 
    child[0]->rect = Rectangle(rc.left, rc.top, 
           rc.right, rc.top+height-1) 
    child[1]->rect = Rectangle(rc.left, rc.top+height, 
           rc.right, rc.bottom) 

(insert into first child we created) 
return Insert(img, pnode->child[0])

來源

2012-12-18 12:17:01 Bytemain

照片馬賽克網絡應用程序。 KD-tree

回答

相關問題