Problem

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)
{
if (radius <= 0)
{
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);
if (Vector2.Distance(point, circleCenter) <= radius)
{
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.

Solution

The code:

```
private static IEnumerable<Vector2> GetPointsInCircle(Vector2 circleCenter, float radius,
Vector2 gridCenter, Vector2 gridStep)
{
if (radius <= 0)
{
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:
float radius2 = radius * 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:
localRadius *= localRadius;
// Step 3. Local radius of the circle segment:
localRadius = (float)Math.Sqrt(radius2 - localRadius);
// 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);
}
}
}
```

Comments:

- 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. - I’ve used integer loop variables to avoid accumulation of errors.
- This code has been successfully tested in comparison with the brute force method.
- 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.