title: Clustering same Size Clusters
body: <p>I got a List of X and Y Points which map a real world position.
  What I would like to do is, to create clusters of approximately the same size based on this given points.</p>
  
  <p>I tryed to write my own implementation based on the k-means algorithm since I could not understand or recreate any of the examples I found online.</p>
  
  <p>I create a (sorted) list of distances for every point to every cluster.
  Every point gets pushed on to a stack and I will work through the stack the following way:</p>
  
  <p>while the stack is not empty<br>
  Get first point p from stack (stack.pop)<br>
  for all distances from p to all clusters<br>
  if the first (closest) cluster is not full - put the point into this cluster<br>
  else (the closest cluster is full)<br>
  Is there a point pt in the desired cluster with dst to desired > p.dst to desired<br>
  Yes - remove pt and add p, then add pt to the pointStack to recompute pt<br>
  No - WHAT DO I DO HERE?</p>
  
  <p>So what I'm doing is basically optimizing the cluster to have the lowest total distance of all points within the cluster while the cluster also has a certain max of points that it can have.</p>
  
  <p>Code:</p>
  
  <pre><code>  Stack&lt;Point2D&gt; pointsStack = new Stack&lt;Point2D&gt;();
  
    //Find distances for every Point to every cluster
    for (PT p : points) {
       List&lt;Distance&gt; pDsts = new ArrayList&lt;Distance&gt;();
       for (Cluster c : clusters) {
          Distance d = null;
          switch (dstFunction) {
             case EUKLID:
                d = new Distance(p, p.distanceFunc(c.x, c.y), c);
                break;
             case LINEAR:
                d = new Distance(p, p.geoDistanceFunc(c.x, c.y), c);
                break;
          }
          pDsts.add(d);
       }
       Collections.sort(pDsts);
       p.dstsToClusters = pDsts;
       pointsStack.push(p);
    }
  
    //For all points in the pointStack
    while (!pointsStack.isEmpty()) {
       Point2D p = pointsStack.pop();
       //for all distances from p to all clusters
       for (Distance d : p.dstsToClusters) {
          boolean foundSwap = false;
          if (d.cluster.size() &lt; maxSizeCluster) {
             d.cluster.addPoint(p);
             break;
          } else { //this cluster is full
             //Is there a point pt in the desired cluster with dst to desired &gt; p.dst to desired
             //Yes - remove pt and add p, then add pt to the pointStack to recompute pt; No - find another cluster
             for (Point2D pt : d.cluster.points) {//for ever point in the desired cluster 
                for (Distance dpt : pt.dstsToClusters) {//for every distance in every point in the desired cluster
                   //find a point in the desired cluster with dst &lt; than p.dst to desired
                   if (dpt.cluster.clusterNumber() == d.cluster.clusterNumber() &amp;&amp; d.dstToCluster &lt; dpt.dstToCluster) {
                      d.cluster.addPoint(p);
                      d.cluster.removePoint(pt);
  
                      pointsStack.push(pt);
                      foundSwap = true;
                      break;
                   }
                }
                if (foundSwap) {
                   break;
                }
             }
          }
          if (foundSwap) {
             break;
          }
          //ELSE -&gt; All points are closer to cluster center than the one that 
          //wants to get into this cluster, so the point will be assigned to 
          //another cluster.
       }
    }
  </code></pre>
  
  <p>My results are very pleasing and most of the time exactly what I wanted, but in some occasions the result will suffer from not doing anything if a point would like to swap into a cluster, but that cluster is already full and no point is further away than the current one. So this point will be put into the second best cluster, or even third if the same (no point further from cluster than current) happens again. You can see this clearly in this image here: <a href="https://i.stack.imgur.com/EDJvo.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/EDJvo.png" alt="IMAGE"></a> The pink/rose points around the blues don't really make sense and its (what I would say) "bad" clustering.</p>
  
  <p>Can someone suggest how to solve this issue?<br><br>
  Again.. these formations happen because the blue cluster is already full. Then one of the pink/rose points (which at this moment don't actually have any color, but lets just call them pink/rose points) wants to go into the blue cluster, because its the closest cluster of all surrounding. However, none of the points in the blue cluster have a greater distance to the cluster center than the pink/rose point that wants to enter the blue cluster. The pink/rose point therefore gets assigned to the next best cluster with the second best distance (orange or cyan in this case). Unfortunately trying to insert into these two clusters results in the same problem. And now the pink/rose point will be assigned to the forth best cluster - which is the pink/rose cluster. This means that clusters will grow around other clusters, which I do not want.</p>
  
  <p>The solution I thought of would be, to swap the pink/rose points with some of the points from the blue cluster - preferably with the points that are closest to another cluster (that shouldn't be full [preferably the second best cluster for the point that gets swapped]), so that the blue cluster "grows" a little bit towards the bottom left, just so much that all the pink/rose points will be in the blue cluster and the pink/rose cluster would just be a bit bigger and also slightly re orientated. However I currently don't know how to implement this logic.</p>