15,610,707 members
Articles / Programming Languages / C#
Article
Posted 4 Sep 2009

47.3K views
8 bookmarked

# 2D Circle Packing Algorithm Ported to C#

Rate me:
4 Sep 2009CPOL2 min read
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.):

C#
```public class Circle
{
public Vector2 mCenter;

/// <summary>
///
/// </summary>
/// <param name="iCenter"></param>
public Circle(Vector2 iCenter, float Radius)
{
mCenter = iCenter;
}
/// <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`).

C#
```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,
{
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 +
(float)(this.mPackingCenter.Y +
float nRadius = (float)(pMinRadius + Rnd.NextDouble() *
}
}
/// <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;

// 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();
{
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!

Written By
Software Developer (Senior)
Spain
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

## Comments and Discussions

 First Prev Next
 How to add circles to the panel in form prasanna muthuramalingam30-Sep-20 0:27 prasanna muthuramalingam 30-Sep-20 0:27
 Distance between circles ricardmag4-Sep-14 5:32 ricardmag 4-Sep-14 5:32
 Why it with your code does not give the same result? The distance between the circles is not smaller than the picture attached. Thank you. best regards Print Screen: http://s29.postimg.org/ytklgkyfb/print.png
 My vote of 2 KubuS13-Nov-09 1:37 KubuS 13-Nov-09 1:37
 Re: My vote of 2 Inaki Ayucar16-Nov-09 5:21 Inaki Ayucar 16-Nov-09 5:21
 Re: My vote of 2 Tim M. Angus10-Sep-13 23:18 Tim M. Angus 10-Sep-13 23:18
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Mar-23 22:17 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.