生成钻石周长上的所有点

Question

给定一系列这样的钻石：

如何生成每颗钻石的黑色方块列表？假设红色方块位于 {0, 0} 并且黑色方块的坐标是相对于它给出的。给定钻石的示例：

0 = {0, 0}
1 = {-1, 0}, {0, -1}, {0, 1}, {1, 0}
2 = {-2, 0}, {-1, -1}, {-1, 1}, {0, -2}, {0, 2}, {1, -1}, {1, 1}, {2, 0}
3 = {-3, 0}, {-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {0, -3}, {0, 3}, {1, -2}, {1, 2}, {2, -1}, {2, 1}, {3, 0}

观察（给定 n 是从原点到角的距离）：

每个坐标对的总和总是n或-n。
除 0 外，列表的大小始终为 4n。
|x| + |y| = n是钻石的笛卡尔方程

通过最后的观察，我在 C 中发现了以下解决方案。但是它在 O(n^2) 时间内进行比较和两次调用 abs()。没有适合更大钻石的更快解决方案吗？

void diamond_points(int n) {
    for (int x = -n; x <= n; ++x) {
        for (int y = -n; y <= n; ++y) {
            if (abs(x) + abs(y) == n) {
                printf("{%d, %d}, ", x, y);
            }
        }
    }
}

Answer 1

有，O(N)

for(int x = -n; x <= n; x++) {
    int y = n - abs(x);
    printf("{%d, %d}, ", x, y);
    if(y > 0) {
        printf("{%d, %d}, ", x, -y);
    }
}

生成钻石周长上的所有点

Generate all points on the perimeter of a diamond

language-agnostic

geometry

coordinates