title: Photo mosaic web application. KD-tree
body: <p>Last month I have been working on a photomosaic website. I build everything in PHP and I got it working great. The only thing I don’t like is the execution time. This is too long I think because of a linear compare search.  So I have been asking around how to improve my search times and most people pointed me in to the direction of the KD-tree which will make k-nearest neighbor a lot quicker.</p>
  
  <p>So I have been looking in to the KD-tree and I understand how to construct such a tree manually. Now I want to code this of course, I could only find libraries for C++ and java. Since I’m only familiar with PHP I’ve been trying to make it myself but this isn’t as easy as I thought it would be.</p>
  
  <p>•   A problem I’m facing is how to store everything. When I get the first array with all points in it I’ll spit it in to 3 pieces. Left branch, node and right branch. Of course I will do the same with the left branch until I can’t split anymore ,of course I cycle through the axes (XYZ). But how do I store the all right branches do I leave them in an array? Or do I compute them again when I am ready to use them?</p>
  
  <p>•   Another thing I was wondering is why is there no PHP KD-tree script is it because PHP is not the right language for this job?</p>
  
  <p>This is what I have got so far.</p>
  
  <p>This function computes random colors (RGB) Which I use to test the rest.</p>
  
  <pre><code>&lt;?php
  function randomiser($number){
  
      if($number &lt;= 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 &lt;= $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;
  }
  ?&gt;
  </code></pre>
  
  <p>This function sort the multidimensional array on a specific key (default is R)</p>
  
  <pre><code>&lt;?php
  function sorter(&amp;$array, $key = 'R'){
  
      if(!is_array($array)){ 
          echo 'Error: The input of sorter() is not an array !!&lt;br&gt;';
          return FALSE;         
      }else{ 
          uasort($array, function ($a, $b) use ($key){
              return strnatcmp($a[$key], $b[$key]);
          }); 
      }
  }
  ?&gt;
  </code></pre>
  
  <p>This class splits the array in to a left branch, node and right branch.</p>
  
  <pre><code>&lt;?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 !!&lt;br&gt;';
              return FALSE;         
          }else{ 
              $number = count($array);
              $median = round($number / 2) - 1; 
  
              $this-&gt;left = array_slice($array, 0, $median);
              $this-&gt;node = array_slice($array, $median, 1);
              $this-&gt;right = array_slice($array, $median+1);
          }
      }
  }
  ?&gt;
  </code></pre>