从中心遍历一个圆的像素

Question

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

算法必须从圆心开始
它必须访问所有通常会访问的点（无孔）
它必须恰好访问圆中的每个点一次

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

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

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

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

Answer 1

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

    /// <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);

Answer 2

您已经提到了 Bresenhams 的圆算法。这是一个很好的起点：您可以从中心像素开始，然后绘制越来越大的 Bresenham 圆。

问题是 Bresenham 圆算法会在一种莫尔效应中丢失对角线附近的像素。在另一个问题中，我有。以该算法为基础，在循环中绘制圆圈的策略有效。

由于Bresenham算法只能将像素放置在离散的整数坐标上，因此访问像素的顺序不会严格按照距离递增的顺序。但距离始终在您正在绘制的当前圆的一个像素以内。

下面是一个实现。那是在 C 中，但它只使用标量，因此适应 C# 应该不难。 setPixel 是迭代时对每个像素所做的操作。

void xLinePos(int x1, int x2, int y)
{
    x1++;
    while (x1 <= x2) setPixel(x1++, y);
}

void yLinePos(int x, int y1, int y2)
{
    y1++;
    while (y1 <= y2) setPixel(x, y1++);
}

void xLineNeg(int x1, int x2, int y)
{
    x1--;
    while (x1 >= x2) setPixel(x1--, y);
}

void yLineNeg(int x, int y1, int y2)
{
    y1--;
    while (y1 >= y2) setPixel(x, y1--);
}

void circle2(int xc, int yc, int inner, int outer)
{
    int xo = outer;
    int xi = inner;
    int y = 0;
    int erro = 1 - xo;
    int erri = 1 - xi;

    int patch = 0;

    while (xo >= y) {         
        if (xi < y) {
            xi = y;
            patch = 1;
        }

        xLinePos(xc + xi, xc + xo, yc + y);
        yLineNeg(xc + y,  yc - xi, yc - xo);
        xLineNeg(xc - xi, xc - xo, yc - y);
        yLinePos(xc - y,  yc + xi, yc + xo);

        if (y) {
            yLinePos(xc + y,  yc + xi, yc + xo);
            xLinePos(xc + xi, xc + xo, yc - y);
            yLineNeg(xc - y,  yc - xi, yc - xo);
            xLineNeg(xc - xi, xc - xo, yc + y);
        }

        y++;

        if (erro < 0) {
            erro += 2 * y + 1;
        } else {
            xo--;
            erro += 2 * (y - xo + 1);
        }

        if (y > inner) {
            xi = y;
        } else {
            if (erri < 0) {
                erri += 2 * y + 1;
            } else {
                xi--;
                erri += 2 * (y - xi + 1);
            }
        }
    }

    if (patch) {
        y--;
        setPixel(xc + y, yc + y);
        setPixel(xc + y, yc - y);
        setPixel(xc - y, yc - y);
        setPixel(xc - y, yc + y);
    }
}

/*
 *      Scan pixels in circle in order of increasing distance
 *      from centre
 */
void scan(int xc, int yc, int r)
{
    int i;

    setPixel(xc, yc);
    for (i = 0; i < r; i++) {
        circle2(xc, yc, i, i + 1);
    }
}

此代码通过跳过交替八分圆上的重合像素来处理不访问两个八分圆中的像素的问题。（编辑：原始代码中仍然存在错误，但现在已通过“patch”变量修复。）

还有改进的地方：内圈基本上就是上次迭代的外圈，所以计算两次没有意义；你可以保留前一个圆的外点数组。

xLinePos函数也有点太复杂了。在该函数中绘制的像素永远不会超过两个，通常只有一个。

如果搜索顺序的粗略困扰您，您可以运行在程序开头使用一次更精确的算法，计算所有圆的遍历顺序，直到合理的最大半径。然后，您可以保留该数据并将其用于迭代所有半径较小的圆。

Answer 3

我找到了满足我的性能需求的解决方案。很简单，就是一个偏移量数组。

    static Point[] circleOffsets;
    static int[] radiusToMaxIndex;

    static void InitCircle(int radius)
    {
        List<Point> results = new List<Point>((radius * 2) * (radius * 2));

        for (int y = -radius; y <= radius; y++)
            for (int x = -radius; x <= radius; x++)
                results.Add(new Point(x, y));

        circleOffsets = results.OrderBy(p =>
        {
            int dx = p.X;
            int dy = p.Y;
            return dx * dx + dy * dy;
        })
        .TakeWhile(p =>
        {
            int dx = p.X;
            int dy = p.Y;
            var r = dx * dx + dy * dy;
            return r < radius * radius;
        })
        .ToArray();

        radiusToMaxIndex = new int[radius];
        for (int r = 0; r < radius; r++)
            radiusToMaxIndex[r] = FindLastIndexWithinDistance(circleOffsets, r);
    }

    static int FindLastIndexWithinDistance(Point[] offsets, int maxR)
    {
        int lastIndex = 0;

        for (int i = 0; i < offsets.Length; i++)
        {
            var p = offsets[i];
            int dx = p.X;
            int dy = p.Y;
            int r = dx * dx + dy * dy;

            if (r > maxR * maxR)
            {
                return lastIndex + 1;
            }
            lastIndex = i;
        }

        return 0;
    }

使用此代码，您只需从 radiusToMaxIndex 获取停止位置的索引，然后循环遍历 circleOffsets 并访问这些像素。这样会占用大量内存，但您始终可以将偏移量的数据类型从 Point 更改为以 Bytes 作为成员的自定义类型。

这个解决方案非常快，足以满足我的需求。它显然有使用一些内存的缺点，但说实话，实例化一个 System.Windows.Form 比这使用更多的内存...

从中心遍历一个圆的像素

Traverse Pixels in a circle from the center

.net

c#

algorithm

geometry