title: Clustering of a set of 3D points
body: <p>I have a 2D array of size <code>n</code> representing <code>n</code> number of points in the 3D space, <code>position[][]</code> for XYZ (e.g. <code>position[0][0]</code> is <code>X</code>, <code>position[0][1]</code> is Y, and <code>position[0][2]</code> is Z coordinate of point 0.</p>
  
  <p>What I need to do is to do clustering on the points, so to have <code>n/k</code> number of clusters of size <code>k</code> so that each cluster consists of the <code>k</code> <strong>closest</strong> points in the 3D space. For instance, if <code>n=100</code> and <code>k=5</code>, I want to have 20 clusters of 5 points which are the closest neighbors in space. </p>
  
  <p>How can I achieve that? (I need pseudo-code. For snippets preferably in Java)</p>
  
  <p>What I was doing so far was a simple sorting based on each component. But this does <strong>NOT</strong> give me necessarily the closest neighbors.</p>
  
  <ol>
  <li>Sort based on X (<code>position[0][0]</code>)</li>
  <li>Then sort based on Y (<code>position[0][1]</code>)</li>
  <li>Then sort based on Z (<code>position[0][2]</code>)</li>
  </ol>
  
  <p><br/></p>
  
  <pre><code>for (int i=0; i&lt;position.length; i++){
    for (int j=i+1; j&lt;position.length; j++){
      if(position[i][0] &gt; position[i+1][0]){
        swap (position[i+1][0], position[i][0]);
       }
     }
  }
  // and do this for position[i][1] (i.e. Y) and then position[i+2][2] (i.e. Z)
  </code></pre>
  
  <p>I believe my question slightly differs from the <strong>Nearest neighbor search with kd-trees</strong> because neighbors in each iteration should not overlap with others. I guess we might need to use it as a component, but how, that's the question.</p>