7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – vnp Nov 21 '14 at 20:11
  • \$\begingroup\$ 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. \$\endgroup\$ – svick Nov 22 '14 at 19:15
  • \$\begingroup\$ Also, Distance() is likely copmputing square root (a relatively expensive operation) unnecessarily. Does your Vector2 have something like DistanceSquared()? \$\endgroup\$ – svick Nov 22 '14 at 19:18
  • \$\begingroup\$ It does! I'll swap to that, good point! \$\endgroup\$ – Nick Udell Nov 26 '14 at 9:09
2
\$\begingroup\$

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:

  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.
  2. I've used integer loop variables to avoid accumulation of errors.
  3. This code has been successfully tested in comparison with the brute force method.
  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.
\$\endgroup\$
  • \$\begingroup\$ Thanks! This looks helpful, I particularly like your way of calculating the points, although I can't use integer arithmetic, as my grid does not always have an integral centre or integral step. Sorry it wasn't in the test, I only included that one test from my suite as an example of usage, didn't mean for it to be representative. \$\endgroup\$ – Nick Udell Nov 22 '14 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.