12,248,681 members (57,387 online)
Technical Blog
alternative version

25.3K views
4 bookmarked
Posted

# 2D Circle Packing algorithm ported to C#

, 4 Sep 2009 CPOL
 Rate this:
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.&#160; Packing of different circles into a 2D space, trying to minimize the unused space, is a typical g

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;

/// <summary>

///

/// </summary>

/// <param name="iCenter"></param>

{

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).

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 +

}

}

/// <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!

## Share

 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

## You may also be interested in...

 First Prev Next
 Distance between circles ricardmag4-Sep-14 6:32 ricardmag 4-Sep-14 6:32
 My vote of 2 KubuS13-Nov-09 2:37 KubuS 13-Nov-09 2:37
 Re: My vote of 2 Inaki Ayucar16-Nov-09 6:21 Inaki Ayucar 16-Nov-09 6:21
 Re: My vote of 2 Tim M. Angus11-Sep-13 0:18 Tim M. Angus 11-Sep-13 0:18
 Last Visit: 31-Dec-99 19:00     Last Update: 3-May-16 7:06 Refresh 1