Find all integer coordinates in a given radius

Question

For a two-dimensional coordinate system, how can I find all points with integer coordinates in the radius of a given point? I want the points to be x-coordinates and y-coordinates.

Finding points in the square around a given point is easy and can be done as follows:

for(int x = -radius + point.x; x < radius + point.x; ++x) for(int y = -radius + point.y; y < radius + point.y; ++y) { points.insert(point(x, y)); } 

But how can I find points in a circle around a given point? This algorithm is related to performance, but not related to accuracy. Therefore, it does not matter whether a point with a radius of 1 is added or not. In other words, I don't need floating point precision.

Answer 1

The simplest solution: take a square and filter it:

 Point point(100, 100); for(int x = -radius; x <= radius; ++x) for(int y = -radius; y <= radius; ++y) if(x*x + y*y <= radius* radius) { points.insert(Point(x + point.x, y + point.y)); } 

Answer 2

One way is the outer loop on x from -R to + R and the inner loop on y in accordance with the y values ​​of the circle for this value of x (from -sqrt (r ^ 2 - x ^ 2) to sqrt (r ^ 2 - x ^ 2) if the center is 0,0), if the center is in X, Y - just add X or Y to all the loop ranges in the same way as in your example

Answer 3

You can make a small modification of the circle circumference algorithm to get a filled circle.

First create the coordinates:

 data = new int[radius]; int f = 1 - radius, ddF_x = 1; int ddF_y = -2 * radius; int x = 0, y = radius; while (x < y) { if (f >= 0) { y--; ddF_y += 2; f += ddF_y; } x++; ddF_x += 2; f += ddF_x; data[radius - y] = x; data[radius - x] = y; } 

Then go to all the internal points:

 int x0 = center.X; int y0 = center.Y - Radius; int y1 = center.Y + Radius - 1; for (int y = 0; y < data.Length; y++) { for (int x = -data[y]; x < data[y]; x++) { doSomething(x + x0, y + y0); doSomething(x + x0, y1 - y); } } 

This saves some operating point, which will not be in the circle, but due to a little pre-processing. It definitely will not help for small circles, but for large ones, well, to be honest, I don’t know. You would have to compare it.

Answer 4

The following code simply analyzes the border in a quarter circle to determine the inner area. He does not need to calculate the distance for external points, as well as for internal points. (editing: but finally all points of the filled circle are added)

In some mini-Java tests for small radius (<10), it has the same speed than a simple full-square analysis approach. For a radius of 20-40, it is about 2 times faster, and it reaches acceleration about 4 times for a radius> 50. For some much larger radius (> 200), the acceleration decreases again, since for any approach it takes a dominant time to create and add points > 100 KB - regardless of how they are defined.

 // add the full length vertical center line once for (int y = -radius + point.y; y <= radius + point.y; ++y) points.insert(Point(point.x, y)); int sqRadius = radius * radius; // add the shorter vertical lines to the left and to the right int h = radius; for (int dx = 1; dx <= radius; ++dx) { // decrease h while (dx*dx + h*h > sqRadius && h > 0) h--; for (int y = -h + point.y; y <= h + point.y; ++y) { points.insert(Point(point.x + dx, y)); points.insert(Point(point.x - dx, y)); } }