我正在开发一个瓷砖映射游戏。
我需要访问圆盘中具有给定半径并以给定点为中心的图块。
访问正方形中的图块很容易，我们只需要使用两个循环：
for(int i=xmin; i<xmax; ++i)
for(int j=ymin; j<ymax; ++j)
// the tile map[i][j] is in the square
但是您如何访问给定圆盘（整圈）中的图块？
编辑：
我的意思是，我可以处理边界矩形中的每个图块（限制磁盘），并通过使用确定该矩形中的图块是否在磁盘中(x-x0)²+(y-y0)²<R²，但是使用该算法，我们将探索无用的图块。
当使用大半径时，要处理的瓦片很多，并且会很慢，因为(x-x0)²+(y-y0)²<R²多次计算很重
我想要一种比这个更高效的算法。
EDIT2：
我不需要完美的磁盘
我们可以通过线性扫描x，计算 的范围y。然后我们只需要扫描圆圈中的图块，就像这张画得很糟糕的图片一样。（圣诞颜色？）
如果我们有一个带半径r和 x 位置的圆x，我们可以计算出 的最大长度y：
y = sqrt(r * r - x * x);
因此，遍历图块的代码如下所示：
int center_x = (xmin + xmax) / 2;
int center_y = (ymin + ymax) / 2;
for(int x = xmin; x <= xmax; x++) {
int ydist = sqrt(r * r - (center_x - x) * (center_x - x));
for(int y = center_y - ydist; y <= center_y + ydist; y++) {
// these are the tiles in the disc
}
}
这是一些Python代码：
from Tkinter import *
from math import *
tk = Tk()
g = Canvas(tk, width=500, height=500)
g.pack()
x0 = 25 # x center
y0 = 25 # y center
r = 17 # radius
t = 10 # tile side length
for x in range(x0 - r, x0 + r + 1):
ydist = int(round(sqrt(r**2 - (x0 - x)**2), 1))
for y in range(y0 - ydist, y0 + ydist + 1):
g.create_rectangle(x * t, y * t, x * t + t, y * t + t
, fill='#'
+ '0123456789ABCDEF'[15 - int(15 * sqrt((x0 - x)**2 + (y0 - y)**2) / r)]
+ '0123456789ABCDEF'[int(15 * sqrt((x0 - x)**2 + (y0 - y)**2) / r)]
+ '0')
g.create_oval((x0 - r) * t, (y0 - r) * t, (x0 + r) * t + t, (y0 + r) * t + t, outline="red", width=2)
mainloop()
结果磁盘：
最后并不完美，但我希望它对你来说足够好（或者你可以修改它）。
您可以在您的平铺矩阵中使用Bresenham 的圆算法（第 3.3 节，扫描转换圆） （它仅使用整数算术，非常准确并处理整个圆的第四部分以产生整个圆周）来检测那些形成圆周，然后从上到下（或从左到右）跟踪它们之间的线：
以下是圆算法的伪实现：
static void circle(int x0, int y0, int x1, int y1) {
// Bresenham's Circle Algorithm
int x, y, d, deltaE, deltaSE;
int radius, center_x, center_y;
bool change_x = false;
bool change_y = false;
if( x0 > x1 ) {
// swap x values
x = x0;
x0 = x1;
x1 = x;
change_x = true;
}
if( y0 > y1 ) {
// swap y values
y = y0;
y0 = y1;
y1 = y;
change_y = true;
}
int dx = x1 - x0;
int dy = y1 - y0;
radius = dx > dy ? (dy >> 1) : (dx >> 1);
center_x = change_x ? x0 - radius : x0 + radius;
center_y = change_y ? y0 - radius : y0 + radius;
x = 0;
y = radius;
d = 1 - radius;
deltaE = 3;
// -2 * radius + 5
deltaSE = -(radius << 1) + 5;
while(y > x) {
if(d < 0) {
d += deltaE;
deltaE += 2;
deltaSE += 2;
x++;
} else {
d += deltaSE;
deltaE += 2;
deltaSE += 4;
x++;
y--;
}
checkTiles(x, y, center_x, center_y);
}
}
void checkTiles(int x, int y, int center_x, int center_y) {
// here, you iterate tiles up-to-down from ( x + center_x, -y + center_y) to (x + center_x, y + center_y)
// in one straigh line using a for loop
for (int j = -y + center_y; j < y + center_y; ++j)
checkTileAt(x + center_x, j);
// Iterate tiles up-to-down from ( y + center_x, -x + center_y) to ( y + center_x, x + center_y)
for (int j = -x + center_y; j < x + center_y; ++j)
checkTileAt(y + center_x, j);
// Iterate tiles up-to-down from (-x + center_x, -y + center_y) to (-x + center_x, y + center_y)
for (int j = -y + center_y; j < y + center_y; ++j)
checkTileAt(-x + center_x, j);
// here, you iterate tiles up-to-down from (-y + center_x, -x + center_y) to (-y + center_x, x + center_y)
for (int j = -x + center_y; j < x + center_y; ++j)
checkTileAt(-y + center_x, j);
}
使用这种技术，您应该只处理所需的图块（并且只处理四分之一圆之后），不会检查任何不必要的图块。除此之外，它仅使用整数运算，这使它非常快（推论和解释可以在提供的书籍链接中找到），并且生成的圆周被证明是真实圆周的最佳近似值。
排除广场外的瓷砖不会更快。我只会使用一个正方形，但忽略圆外的瓷砖。（例如通过检查瓷砖离圆心有多远）
for(int i=xmin; i<xmax; ++i):
for(int j=ymin; j<ymax; ++j):
if map[i][j] not in the circle:
break
// the tile map[i][j] is in the square
对性能开销的粗略估计：
Area Square = 2*r*2*r
Area Circle = pi*r*r
Area Square / Area Circle = 4/pi = 1.27
这意味着仅使用正方形而不是圆形1.27 times slower（假设使用圆形没有其自身的低效率）
此外，因为您可能会对图块执行一些操作（使得涉及圆中图块的迭代要慢得多），这意味着使用圆形布局而不是方形布局，性能增益将下降到几乎为 0。
使用边界八边形。它是切掉角的边界正方形。您需要这些测试来确定一个点（瓷砖的任何角落）是否处于该形状。将其放入 2D 循环中。
abs(x) < R
abs(y) < R
abs(x)+abs(y) < sqrt(2)*R
当然，预先计算 sqrt(2)*R。
显然，这与圆形不同，但与正方形相比，它可以很好地减少浪费的空间量。
如果不需要在循环中进行某种测试，就很难生成一个仅完美地越过瓷砖中心或瓷砖角的循环。编写此类循环的任何希望都来自使用 Bresenham 的算法。