c# - 从中心遍历一个圆的像素

Question

我需要一种算法，例如 Bresenham 的圆算法，但要进行一些修改。 该算法必须访问半径内的所有像素(因此本质上是一个填充)。

• 算法必须从圆心开始
• 它必须访问所有通常会访问的点(没有漏洞)
• 它必须恰好访问圆中的每个点一次

我想出的一种技术是先通过圆的矩形确定圆内的所有像素坐标，然后用 Math.Sqrt 检查它是否在圆内。 然后它会按距离对像素进行排序，然后访问每个像素。

这正是我想要的，除了要快。

所以我的问题是: 有没有一种快速的方法可以做到这一点而无需获取、排序然后访问每个像素？

为了澄清，我实际上并不想在图像上绘图，我只想按描述的顺序遍历它们。

Answer 1

首先，我们可以利用事实，即圆可以分成 8 个八分圆。所以我们只需要填充单个八分圆并使用简单的 +- 坐标变化来获得完整的圆。所以如果我们试图只填充一个八分圆，我们只需要担心从中心开始的两个方向:左和左上。此外，巧妙地使用优先级队列(.NET 没有，因此您需要在其他地方找到它)和 HashMap 等数据结构可以显着提高性能。

    /// <summary>
    /// Make sure it is structure.
    /// </summary>
    public struct Point
    {
        public int X { get; set; }
        public int Y { get; set; }

        public int DistanceSqrt()
        {
            return X * X + Y * Y;
        }
    }

    /// <summary>
    /// Points ordered by distance from center that are on "border" of the circle.
    /// </summary>
    public static PriorityQueue<Point> _pointsToAdd = new PriorityQueue<Point>();
    /// <summary>
    /// Set of pixels that were already added, so we don't visit single pixel twice. Could be replaced with 2D array of bools.
    /// </summary>
    public static HashSet<Point> _addedPoints = new HashSet<Point>();

    public static List<Point> FillCircle(int radius)
    {
        List<Point> points = new List<Point>();

        _pointsToAdd.Enqueue(new Point { X = 1, Y = 0 }, 1);
        _pointsToAdd.Enqueue(new Point { X = 1, Y = 1 }, 2);
        points.Add(new Point {X = 0, Y = 0});

        while(true)
        {
            var point = _pointsToAdd.Dequeue();
            _addedPoints.Remove(point);

            if (point.X >= radius)
                break;

            points.Add(new Point() { X = -point.X, Y = point.Y });
            points.Add(new Point() { X = point.Y, Y = point.X });
            points.Add(new Point() { X = -point.Y, Y = -point.X });
            points.Add(new Point() { X = point.X, Y = -point.Y });

            // if the pixel is on border of octant, then add it only to even half of octants
            bool isBorder = point.Y == 0 || point.X == point.Y;
            if(!isBorder)
            {
                points.Add(new Point() {X = point.X, Y = point.Y});
                points.Add(new Point() {X = -point.X, Y = -point.Y});
                points.Add(new Point() {X = -point.Y, Y = point.X});
                points.Add(new Point() {X = point.Y, Y = -point.X});
            }

            Point pointToLeft = new Point() {X = point.X + 1, Y = point.Y};
            Point pointToLeftTop = new Point() {X = point.X + 1, Y = point.Y + 1};

            if(_addedPoints.Add(pointToLeft))
            {
                // if it is first time adding this point
                _pointsToAdd.Enqueue(pointToLeft, pointToLeft.DistanceSqrt());
            }

            if(_addedPoints.Add(pointToLeftTop))
            {
                // if it is first time adding this point
                _pointsToAdd.Enqueue(pointToLeftTop, pointToLeftTop.DistanceSqrt());
            }
        }

        return points;
    }

我会把扩展到完整列表留给你。还要确保八分圆的边界不会导致点数加倍。

好吧，我受不了了，自己做了。另外，为了确保它具有您想要的属性，我做了简单的测试:

        var points = FillCircle(50);

        bool hasDuplicates = points.Count != points.Distinct().Count();
        bool isInOrder = points.Zip(points.Skip(1), (p1, p2) => p1.DistanceSqrt() <= p2.DistanceSqrt()).All(x => x);