2D 圆填充算法移植到 C#

昨天，一位朋友问我是否知道任何 C# 实现的圆形填充算法。事实上，我不知道，但搜索了一下，我找到了 这个算法，以及 这个 Java Applet 实现。

将不同大小的圆形填充到二维空间中，并尽量减少未使用的空间，是一个典型的几何问题。人类可以很快地解决它，但很难找到数学上的解决方案。最常见的实现方式是使用数值算法，在每次迭代中逐渐逼近解决方案。

上述算法就是这种情况。它没有实现可用空间的限制，但很好地将圆形重新排列在中心点周围。 像这些数值算法的“流动”特性特别适合用于某种图形界面，因为你可以改变适应（或重新排序）的速度，从而获得非常漂亮的动画效果，或者你甚至可以与你的圆形进行交互，例如移动一些圆形会使算法做出反应并调整其他圆形（你可以尝试上面的 Applet）。

因此，有了所有这些材料，将其移植到 C# 很容易。结果如下：

一个非常简单的 Circle 类的代码（请注意，我正在使用 XNA 框架进行数学运算 – Vector2 等）。

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();
        }     
    }

以及重要的类。CirclePacker

这个类保存一个圆形列表，这些圆形将围绕一个“PackingCenter”点重新排列，圆形之间有“MinSeparation”。你只需要迭代地调用 OnFrameMove 方法，传递一个“iterationCounter”参数，该参数将控制适应速度的阻尼（值越大，适应速度越慢）。 始终将此参数重置为 1 以重置速度（切勿将此参数设置为 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);
        }
    }

待办事项

可以实现一个可变速度系统，并且能够交互地改变 PackingCenter 点也会很好。 还需要实现可用空间的限制，如果圆形不合适，则按比例改变圆形半径。

祝好！