Introduction

To find all integer grid points inside a circle, you do not need a complicated geometry algorithm. The standard approach is to scan the bounding square and keep only the points whose squared distance from the center is less than or equal to the squared radius.

This works for graphics, grid simulations, search areas in games, and any problem where coordinates must stay on integer lattice points.

Use Squared Distance Instead of sqrt

For a center point (cx, cy) and radius r, an integer point (x, y) is inside or on the circle if:

(x - cx)^2 + (y - cy)^2 <= r^2

The square root is unnecessary. Comparing squared values is faster and avoids floating-point noise from repeated sqrt calls.

If the center is an integer point and the radius is an integer, the search range is:

• 'x from cx - r to cx + r'
• 'y from cy - r to cy + r'

That square contains every possible lattice point that could lie in the circle.

A Simple Python Implementation

1def integer_points_in_radius(cx, cy, r):
2    points = []
3    r2 = r * r
4
5    for x in range(cx - r, cx + r + 1):
6        for y in range(cy - r, cy + r + 1):
7            dx = x - cx
8            dy = y - cy
9            if dx * dx + dy * dy <= r2:
10                points.append((x, y))
11
12    return points
13
14
15points = integer_points_in_radius(0, 0, 2)
16print(sorted(points))

[(-2, 0), (-1, -1), (-1, 0), (-1, 1), (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), (1, -1), (1, 0), (1, 1), (2, 0)]

This is the clearest approach for most practical uses.

Time Complexity and a Small Optimization

The algorithm checks every point in the bounding square, so the work is proportional to (2r + 1)^2, which is O(r^2).

That is usually fine because the number of returned points is also proportional to the area of the circle. In other words, if you truly need every integer point, you cannot avoid work that grows with the area.

A common optimization is to iterate over x and compute the maximum allowed y offset for that x. That avoids checking corner points that are obviously outside the circle:

1import math
2
3def integer_points_in_radius_fast(cx, cy, r):
4    points = []
5    r2 = r * r
6
7    for x in range(cx - r, cx + r + 1):
8        dx = x - cx
9        max_dy = int(math.isqrt(r2 - dx * dx))
10        for y in range(cy - max_dy, cy + max_dy + 1):
11            points.append((x, y))
12
13    return points

This still has output-size complexity, but it skips unnecessary distance checks.

Non-Integer Centers

If the center is not an integer, the same idea still works. You just compute the integer bounds with floor and ceiling and test the squared distance against the real-valued center.

The only change is that dx and dy become floating-point values:

• 'dx = x - cx'
• 'dy = y - cy'

The inclusion test remains the same.

Common Pitfalls

• Using sqrt in every iteration when a squared-distance comparison is enough.
• Forgetting to include boundary points that lie exactly on the circle.
• Iterating over an area larger than the bounding square, which wastes time.
• Assuming a faster asymptotic algorithm exists even when you need to output every matching point.

Summary

• Scan the bounding square and keep points whose squared distance is at most r^2.
• Comparing squared distances avoids unnecessary square roots.
• The straightforward algorithm runs in O(r^2), which is appropriate when you need every point.
• A per-column optimization can reduce wasted checks while preserving correctness.
• The same method works for integer or non-integer centers.