Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

2D Circle Packing algorithm ported to C#

, 4 Sep 2009
Rate this:
Please Sign up or sign in to vote.
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 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:

image

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!

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Inaki Ayucar
Software Developer (Senior)
Spain 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

 
QuestionDistance between circles Pinmemberricardmag4-Sep-14 5:32 
GeneralMy vote of 2 PinmemberKubuS13-Nov-09 1:37 
GeneralRe: My vote of 2 PinmemberInaki Ayucar16-Nov-09 5:21 
GeneralRe: My vote of 2 PinmemberTim M. Angus10-Sep-13 23:18 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140916.1 | Last Updated 4 Sep 2009
Article Copyright 2009 by Inaki Ayucar
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid