Get all points within given radius for a given vector I have a vector of ints that represents a point on a N-dimensional grid. I need to find all grid points that are within a given radius. I wrote the following, but it is rather inefficient, because it iterates through all points in a cube and checks the radius for each point:

typedef std::vector&lt;int&gt; VectI;

bool getNextInNSphere(VectI&amp; x,int radius){
    int pos = 0;
    bool done = false;
    while (!done &amp;&amp; pos &lt; x.size()){
        x[pos]++;
        if (x[pos]&gt;radius){ x[pos] = -radius; pos++; }
        else              { done = true; }
    }
    if (done){
        int sqsum = 0;
        for (size_t i=0;i&lt;x.size();i++){ sqsum += x[i]*x[i]; }
        if (sqsum &gt; radius*radius){ return getNextInNSphere(x,radius); }
    }
    return done;
}


usage:

void foo(const VectI&amp; x,int radius){
    VectI d = VectI(x.size(),-radius);
    while (getNextInNSphere(d,radius)){
        // x+d is inside a sphere of given radius around x
    }
}


Any ideas how to get this more efficient and/or in a nicer way?
Here are some things that may help you improve your code.

Use the appropriate #includes

In order to compile and link, this code requires at least following line:

#include &lt;vector&gt;


This too, should be part of the interface.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people.  Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code.  This affects not only code reviews, but also maintenance of the code in the future, by you or by others.  One good way to address that is by the use of comments.  The test code was helpful, but would have been slightly more so if a representative main had been include for a whole program.

Take advantage of symmetry

Given the simple case of 2D space, the "sphere" of course becomes a circle.  For a given radius \$r\$, we know that the coordinate \$(r,0)\$ is, by definition, the outer bound of the "sphere".  Also, no calculation is needed to determmine that the points \$(0, r), (-r, 0),\$ and \$(0, -r)\$ are also on the perimeter.  This principle can easily be expanded for any N-dimensional space.  

Additionally, now that we know that \$(r,0)\$ and \$(-r, 0)\$ are among the desired points, it is clear that every point between them must also be inside the "sphere."  In general, one can iterate each dimension from \$r\$ to \$0\$, to follow the perimeter of the sphere (as with a modification of Bresenham's algorithm) and then simply include all points between there and the origin.

Precompute if practical

If you happen to know in advance a maximum size \$x\$ that will be used and the dimensionality \$d\$ of the space in which you'll work, you may be able to precompute the point clouds from 1 to \$x\$.  Since the point clouds are nested, (that is, the cloud for \$x=3\$ completely contains that of \$x=2\$, etc.) the points could be stored in a vector and for each integer  \$x\$, the program could store the matching index \$i\$ into the vector.  If the vector is sorted by increasing distance from the origin, then all points within a particular radius \$x\$ would be stored in indices \$[0 ... i]\$.

Consider writing an iterator

The code functions very much like an iterator but isn't quite.  Consider refactoring it so that it's an actual iterator and you may find that it's somewhat easier to use.

Reconsider the interface

Right now, the code doesn't actually return all points within the sphere.  Rather it returns the set of points, centered at the origin that are within the given radius.  It seems to me that it would be nicer to do the x+d calculation for the caller.