Algorithm to access the tiles in a matrix (game map) that are in a disc

Question

I am developping a tile mapped game.
I need to access the tiles that are in a disc, with a given radius and centered on a given point.

Accessing the tiles that are in a square is easy, we only need to use two loops :

for(int i=xmin; i<xmax; ++i)
   for(int j=ymin; j<ymax; ++j)     
       // the tile map[i][j] is in the square

But how do you access the tiles that are in a given disc (full circle) ?

EDIT:
I mean, I could process each tile in a bounding rectangle (bounding the disc), and determine whether or not a tile in that rectangle is in the disk, by using (x-x0)²+(y-y0)²<R², but with that algorithm, we would explore useless tiles.
When using a large radius, there are many tiles to process, and it will be slow because calculating (x-x0)²+(y-y0)²<R² many times is heavy
What I want is an algorithm more efficient than this one.

EDIT2:
I don't need a perfect disk

Answer 1

We can do a linear scan through x, calculating the range of y. Then we only have to scan through the tiles that are in the circle, like in this badly drawn picture. (Christmas colors?)

If we have a circle with radius r and an x-position x, we can figure out the maximum length of y:

y = sqrt(r * r - x * x);

So the code for iterating through the tiles would look like:

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
    }
}

Here's some Python code:

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()

And the resulting disk:

Not perfect at the ends, but I hope it works well enough for you (or you can modify it).

Answer 2

You can use the Bresenham's circle Algorithm (section 3.3, Scan Converting Circles) (it uses integer arithmetic only, is very accurate and process fourth part of the whole circle to produce the entire circumference) in your tile matrix to detect those tiles that forms the circumference, then trace lines between them from up-to-down (or left-to-right):

The following is a pseudo implementation of the circle algorithm:

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

With this technique you should process only the required tiles (and after processing only a quarter of the circle), none unnecessary tiles would be checked. Beside that, it uses integer arithmetic only, wich makes it really fast (the deduction and explanation can be found in the provided book link) and the generated circumference is proven to be the best approximation for the real one.