2D Circle Packing Algorithm Ported to C#

Yesterday, a friend asked me if I knew of any C# implementation of a Circle Packing algorithm. In fact, I didn’t, but searching a bit I found this algorithm, and this Java Applet implementation.

Packing of different circles into a 2D space, trying to minimize the unused space, is a typical geometrical problem. Humans can solve it quite quickly, but it is very hard to find a solution mathematically. The most frequent implementations use numeric algorithms that get closer to the solution in each iteration.

It is the case of the above algorithm. It doesn’t implement the limits of the available space, but reorders the circles around a center point quite well. The “flowing” nature of numerical algorithms like these fit specially well if you want to use them for some kind of graphical interface, as you can change the adaptation (or reordering) speed, giving a very nice animated result, or you can even interact with your circles, as moving some of them will make the algorithm to react adapting others (you can try the above applet).

So, with all that material, it was easy to port it to C#. The result is the following:

The code for a very easy Circle class (please note that I´m using the XNA framework for the maths – Vector2, etc.):

public class Circle
    {
        public Vector2 mCenter;
        public float mRadius;
 
        /// <summary>
        /// 
        /// </summary>
        /// <param name="iCenter"></param>
        /// <param name="Radius"></param>
        public Circle(Vector2 iCenter, float Radius)
        {
            mCenter = iCenter;
            mRadius = Radius;
        }
        /// <summary>
        /// 
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            return "Rad: " + mRadius + " _ Center: " + mCenter.ToString();
        }     
    }

And the important class. CirclePacker:

This class holds a list of circles that will be re-arranged around a “PackingCenter” point, with a “MinSeparation” between them. You only need to iteratively call the OnFrameMove method, passing an “iterationCounter” parameter, that will hold the damping on the adaptation speed (the bigger value, the slower adaptation). Reset this parameter to 1 always you want to reset speed (never set this parameter to 0).

public class CirclePacker
  {
      public List<Circle> mCircles = new List<Circle>();
      public Circle mDraggingCircle = null;
      protected Vector2 mPackingCenter;
      public float mMinSeparation = 1f;

      /// <summary>
      /// Generates a number of Packing circles in the constructor.
      /// Random distribution is linear
      /// </summary>
      public CirclePacker(Vector2 pPackingCenter, int pNumCircles,
                          double pMinRadius, double pMaxRadius)
      {
          this.mPackingCenter = pPackingCenter;

          // Create random circles
          this.mCircles.Clear();
          Random Rnd = new Random(System.DateTime.Now.Millisecond);
          for (int i = 0; i < pNumCircles; i++)
          {
              Vector2 nCenter = new Vector2((float)(this.mPackingCenter.X +
                                                    Rnd.NextDouble() * pMinRadius),
                                            (float)(this.mPackingCenter.Y +
                                                    Rnd.NextDouble() * pMinRadius));
              float nRadius = (float)(pMinRadius + Rnd.NextDouble() *
                                     (pMaxRadius - pMinRadius));
              this.mCircles.Add(new Circle(nCenter, nRadius));
          }
      }
      /// <summary>
      ///
      /// </summary>
      /// <param name="?"></param>
      /// <returns></returns>
      private float DistanceToCenterSq(Circle pCircle)
      {
          return (pCircle.mCenter - mPackingCenter).LengthSquared();
      }
      /// <summary>
      ///
      /// </summary>
      private int Comparer(Circle p1, Circle P2)
      {
          float d1 = DistanceToCenterSq(p1);
          float d2 = DistanceToCenterSq(P2);
          if (d1 < d2)
              return 1;
          else if (d1 > d2)
              return -1;
          else return 0;
      }
      /// <summary>
      ///
      /// </summary>
      public void OnFrameMove(long iterationCounter)
      {
          // Sort circles based on the distance to center
          mCircles.Sort(Comparer);

          float minSeparationSq = mMinSeparation * mMinSeparation;
          for (int i = 0; i < mCircles.Count - 1; i++)
          {
              for (int j = i + 1; j < mCircles.Count; j++)
              {
                  if (i == j)
                      continue;

                  Vector2 AB = mCircles[j].mCenter - mCircles[i].mCenter;
                  float r = mCircles[i].mRadius + mCircles[j].mRadius;

                  // Length squared = (dx * dx) + (dy * dy);
                  float d = AB.LengthSquared() - minSeparationSq;
                  float minSepSq = Math.Min(d, minSeparationSq);
                  d -= minSepSq;

                  if (d < (r * r) - 0.01 )
                  {
                      AB.Normalize();

                      AB *= (float)((r - Math.Sqrt(d)) * 0.5f);

                      if (mCircles[j] != mDraggingCircle)
                          mCircles[j].mCenter += AB;
                      if (mCircles[i] != mDraggingCircle)
                          mCircles[i].mCenter -= AB;
                  }
              }
          }


          float damping = 0.1f / (float)(iterationCounter);
          for (int i = 0; i < mCircles.Count; i++)
          {
              if (mCircles[i] != mDraggingCircle)
              {
                  Vector2 v = mCircles[i].mCenter - this.mPackingCenter;
                  v *= damping;
                  mCircles[i].mCenter -= v;
              }
          }
      }
      /// <summary>
      ///
      /// </summary>
      public void OnMouseDown(MouseEventArgs e)
      {
          Vector2 center = new Vector2(e.X, e.Y);
          mDraggingCircle = null;
          foreach (Circle circle in mCircles)
          {
              float dist = (circle.mCenter - center).LengthSquared();
              if (dist < (circle.mRadius * circle.mRadius))
              {
                  mDraggingCircle = circle;
                  break;
              }
          }
      }
      /// <summary>
      ///
      /// </summary>
      public void OnMouseMove(MouseEventArgs e)
      {
          if (mDraggingCircle == null)
              return;

          mDraggingCircle.mCenter = new Vector2(e.X, e.Y);
      }
  }

To Do

A variable speed system could be done, and a way to interactively change the PackingCenter point would be nice too. It would also be necessary to implement the limits of the available space, changing the radius of the circles proportionally if they don´t fit.

Cheers!