# Get all points on a uniform discrete grid inside a circle's radius

I have a 2-dimensional grid defined by a known point gridCenter and distance between points gridStep and need to find all points on this grid that are inside or on the radius of a circle defined by center and radius.

My solution is to use a brute-force approach like so:

public static IEnumerable<Vector2> GetPointsInCircle(Vector2 circleCenter, float radius, Vector2 gridCenter, Vector2 gridStep)
{
{
throw new ArgumentOutOfRangeException("radius", "Argument must not be negative.");
}

if (gridStep.x <= 0 || gridStep.y <= 0)
{
throw new ArgumentOutOfRangeException("gridStep", "Argument must not contain negative components.");
}

var minimumPoint = GetClosestGridPoint(new Vector2(circleCenter.x - radius, circleCenter.y - radius), gridCenter, gridStep);
var maximumPoint = GetClosestGridPoint(new Vector2(circleCenter.x + radius, circleCenter.y + radius), gridCenter, gridStep);

for (var x = minimumPoint.x; x <= maximumPoint.x; x += gridStep.x)
{
for (var y = minimumPoint.y; y <= maximumPoint.y; y += gridStep.y)
{
var point = new Vector2(x, y);

{
yield return point;
}
}
}
}

private static Vector2 GetClosestGridPoint(Vector2 point, Vector2 gridCenter, Vector2 gridStep)
{
var leftGridPoint = gridCenter.x + Mathf.Floor((point.x - gridCenter.x) / gridStep.x) * gridStep.x;
var rightGridPoint = leftGridPoint + gridStep.y;
var closestHorizontalGridPoint = (point.x - leftGridPoint) > (rightGridPoint - point.x) ? rightGridPoint : leftGridPoint;

var bottomGridPoint = gridCenter.y + Mathf.Floor((point.y - gridCenter.y) / gridStep.y) * gridStep.y;
var topGridPoint = bottomGridPoint + gridStep.y;
var closestVerticalGridPoint = (point.y - bottomGridPoint) > (topGridPoint - point.y) ? bottomGridPoint : topGridPoint;

return new Vector2(closestHorizontalGridPoint, closestVerticalGridPoint);
}


And usage (and unit test) are as follows:

[Test]
public void GetPointsInCircleTest()
{
var results = AdaptiveSpatialGrid2D<int>.GetPointsInCircle(new Vector2(0.1f, 0.1f),
1,
new Vector2(0, 0),
new Vector2(1, 1));

var expected = new List<Vector2>()
{
new Vector2(0,0),
new Vector2(0,1),
new Vector2(1,0) //(1,1) is outside of circle radius and invalid
};

CollectionAssert.AreEquivalent(expected, results);
}


This method will be executed frequently (probably once a second) inside of a game and needs to be as light-weight as possible. Typically the grid will have few points inside of the circle at any time (in the region of fifty).

Are there any optimizations I can make to improve execution speed?

Additionally, the code currently resides inside my grid's class as a static method, but I wonder if it would be better placed somewhere more generic, as really it applies to any 2D grid, not just my implementation.

General comments on the code are also welcome.

• It is a classical flood fill problem (see en.wikipedia.org/wiki/Flood_fill). For circles, it can be optimized even further with the help of Bresenham algorithm (en.wikipedia.org/wiki/Midpoint_circle_algorithm). – vnp Nov 21 '14 at 20:11
• The circle is approximately 79 % of the square you're iterating. And each iteration of your loop is likely going to be pretty fast, so any improved version would also have to have very fast iterations. – svick Nov 22 '14 at 19:15
• Also, Distance() is likely copmputing square root (a relatively expensive operation) unnecessarily. Does your Vector2 have something like DistanceSquared()? – svick Nov 22 '14 at 19:18
• It does! I'll swap to that, good point! – Nick Udell Nov 26 '14 at 9:09

The code:

private static IEnumerable<Vector2> GetPointsInCircle(Vector2 circleCenter, float radius,
Vector2 gridCenter, Vector2 gridStep)
{
{
throw new ArgumentOutOfRangeException("radius", "Argument must be positive.");
}
if (gridStep.x <= 0 || gridStep.y <= 0)
{
throw new ArgumentOutOfRangeException("gridStep", "Argument must contain positive components only.");
}

// Loop bounds for X dimension:
int i1 = (int)Math.Ceiling((circleCenter.x - gridCenter.x - radius) / gridStep.x);
int i2 = (int)Math.Floor((circleCenter.x - gridCenter.x + radius) / gridStep.x);

// Constant square of the radius:

for (int i = i1; i <= i2; i++)
{
// X-coordinate for the points of the i-th circle segment:
float x = gridCenter.x + i * gridStep.x;

// Local radius of the circle segment (half-length of chord) calulated in 3 steps.
// Step 1. Offset of the (x, *) from the (circleCenter.x, *):
float localRadius = circleCenter.x - x;
// Step 2. Square of it:
// Step 3. Local radius of the circle segment:

// Loop bounds for Y dimension:
int j1 = (int)Math.Ceiling((circleCenter.y - gridCenter.y - localRadius) / gridStep.y);
int j2 = (int)Math.Floor((circleCenter.y - gridCenter.y + localRadius) / gridStep.y);

for (int j = j1; j <= j2; j++)
{
yield return new Vector2(x, gridCenter.y + j * gridStep.y);
}
}
}


1. If step values in the gridStep aren't supposed to be close to each other, this method could be rewritten to select a dimension with the largest step's value for the outer loop.
4. This method is ~20% faster on my machine. Efficiency of the method depends on the number of grid points inside a circle. More points - more efficiency.