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;
public Circle(Vector2 iCenter, float Radius)
{
mCenter = iCenter;
mRadius = Radius;
}
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;
public CirclePacker(Vector2 pPackingCenter, int pNumCircles,
double pMinRadius, double pMaxRadius)
{
this.mPackingCenter = pPackingCenter;
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));
}
}
private float DistanceToCenterSq(Circle pCircle)
{
return (pCircle.mCenter - mPackingCenter).LengthSquared();
}
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;
}
public void OnFrameMove(long iterationCounter)
{
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;
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;
}
}
}
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;
}
}
}
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!

Inaki Ayucar is a Microsoft MVP in DirectX/XNA, and a software engineer involved in development since his first Spectrum 48k, in the year 1987. He is the founder and chief developer of The Simax Project (www.simaxvirt.com) and is very interested in DirectX/XNA, physics, game development, simulation, C++ and C#.

His blog is: http://graphicdna.blogspot.com

To contact Inaki: iayucar@simax.es