在没有重复索引的情况下循环遍历圆形数组

Question

我需要遍历一个小半径圆弧形的数组（比如一个像素一个像素地画一个圆），但是我试过的所有算法都会检查数组的重复索引（它有相同的 x 和 y几次）。我的半径为 3，圆圈形式为 28 个元素（未填充），但算法迭代 360 次。我可以在做某事之前检查 x 或 y 是否改变，但它很蹩脚。

我现在的代码：

for (int radius = 1; radius < 6; radius++)
{
    for (double i = 0; i < 360; i += 1)
    {
        double angle = i * System.Math.PI / 180;
        int x = (int)(radius * System.Math.Cos(angle)) + centerX;
        int y = (int)(radius * System.Math.Sin(angle)) + centerY;

        // do something
        // if (array[x, y]) ....
    }
}

PS: 我不能使用中点圆，因为我需要从 2 开始增加半径直到 6，而不是每个索引都得到，因为他的圆不是真实的（根据三角学）

编辑：我真正需要的是从中心开始逐边扫描整个圆。

360步（获取所有坐标）：

Full scan

for (int radius = 2; radius <= 7; radius++)
{
    for (double i = 0; i <= 360; i += 1)
    {
        double angle = i * System.Math.PI / 180;
        int x = (int)(radius * System.Math.Cos(angle));
        int y = (int)(radius * System.Math.Sin(angle));
        print(x, y, "X");
    }
}

使用中点圆或其他算法跳过步骤（缺少坐标）：

Midpoint Circle Algorithm

for (int radius = 2; radius <= 7; radius++)
{
    int x = radius;
    int y = 0;
    int err = 0;
    while (x >= y)
    {
        print(x, y, "X");
        print(y, x, "X");
        print(-y, x, "X");
        print(-y, x, "X");
        print(-x, y, "X");
        print(-x, -y, "X");
        print(-y, -x, "X");
        print(y, -x, "X");
        print(x, -y, "X");

        y += 1;
        err += 1 + 2 * y;
        if (2 * (err - x) + 1 > 0)
        {
            x -= 1;
            err += 1 - 2 * x;
        }
    }
}

Answer 1

这里有两种算法思想：一种是光栅化一个圆。 OP 代码在这方面提供了几个改进机会：(a) 无需对整个 360 度圆进行采样，意识到圆在两个轴上是对称的。 (x,y) 可以在其他三个象限中反映为 (-x,y)、(-x,-y) 和 (x,-y)。 (b) 循环上的步骤应与曲率有关。一个简单的启发式方法是使用半径作为步长。所以...

let step = MIN(radius, 90)
for (double i=0; i<90; i += step) {
   add (x,y) to results
   reflect into quadrants 2,3,4 and add to results
}

通过这几项改进，您可能不再关心生成的重复样本。如果你仍然这样做，那么第二个想法，独立于圆圈，是如何散列一对整数。这里有一篇很好的文章：Mapping two integers to one, in a unique and deterministic way.

简而言之，我们从保证映射唯一的 x,y 对计算一个 int，然后检查是否有重复...

cantor(x, y) = 1/2(x + y)(x + y + 1) + y

这仅适用于 x,y 的正值，这正是您所需要的，因为我们只在第一象限中计算（然后反映）。对于每一对，检查它们是否是唯一的

let s = an empty set
int step = MIN(radius, 90)
for (double i=0; i<90; i += step) {
    generate (x,y)
    let c = cantor(x,y)
    if (not(s contains c)) {
        add (x,y) to results
        reflect into quadrants 2,3,4 and add to results
        add c to s
    }
}

Answer 2

知道了！

它不漂亮，但对我有用。

int maxRadius = 7;

for (int radius = 1; radius <= maxRadius; radius++)
{
    x = position.X - radius;
    y = position.Y - radius;
    x2 = position.X + radius;
    y2 = position.Y + radius;
    for (int i = 0; i <= radius * 2; i++)
    {
        if (InCircle(position.X, position.Y, x + i, y, maxRadius)) // Top X
            myArray[position, x + i, y];    // check array

        if (InCircle(position.X, position.Y, x + i, y2, maxRadius)) // Bottom X
            myArray[position, x + i, y2];    // check array

        if (i > 0 && i < radius * 2)
        {
            if (InCircle(position.X, position.Y, x, y + i, maxRadius)) // Left Y
                myArray[position, x, y + i];    // check array  

            if (InCircle(position.X, position.Y, x2, y + i, maxRadius)) // Right Y
                myArray[position, x2, y + i];    // check array   
        }
    }
}


public static bool InCircle(int originX, int originY, int x, int y, int radius)
{
    int dx = Math.Abs(x - originX);
    if (dx > radius) return false;
    int dy = Math.Abs(y - originY);
    if (dy > radius) return false;
    if (dx + dy <= radius) return true;
    return (dx * dx + dy * dy <= radius * radius);
}

在没有重复索引的情况下循环遍历圆形数组

Loop through a array in circle shape without repeat indexes

algorithm

geometry

trigonometry

pseudocode