0
\$\begingroup\$

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<int> VectI;

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

usage:

void foo(const VectI& 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?

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't understand what this code is doing at all. Why are you translating some coordinates over by one unit? Why are you setting some coordinates to -radius? Why is this function recursive? Why is a function named getSomething() causing mutation? \$\endgroup\$ – 200_success Aug 11 '16 at 16:53
  • \$\begingroup\$ @200_success are these serious question or merely pointing out that the code is hard to read? one unit because x is a point on a integer grid. -radius because this is the biggest difference a coordinate of a point on the surface of the sphere can have from its center coordinate. Recursive because each call should return a new point, but it iterates through points an a cube which not all are inside the sphere. Why get... does mutation is actually a good question. \$\endgroup\$ – formerlyknownas_463035818 Aug 11 '16 at 19:25
  • \$\begingroup\$ These are serious questions. I am skeptical that this code does what you say… or I am misunderstanding the task altogether. \$\endgroup\$ – 200_success Aug 11 '16 at 20:26
6
\$\begingroup\$

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 <vector>

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.

\$\endgroup\$
4
\$\begingroup\$

No need for done

You don't actually need the done variable. Consider

    for (size_t position = 0; position < x.size(); position++) {
        x[position]++;

        if (x[position] <= radius) {
            int sum = 0;
            for (auto element : x) {
                sum += element * element;
            }

            if (sum > radius * radius) {
                return getNextInNSphere(x, radius);
            }

            return true;
        }

        x[position] = -radius;
    }

    return false;

This will return the same result in a more readable form. Note that I haven't changed any of the operations, just how they are presented.

This makes clear that pos is a position.

Now we can easily see that we are looping through each member of x and incrementing each element in it. If the element is within the radius, we either return true or we call this method recursively. Otherwise, we set the element to -radius and continue. If every member is greater than radius, it will set them all to -radius and return false.

Other than the outer for loop, there is only one statement per line.

I prefer the range-based for loop when I'm only using the values and not changing them nor doing something with the index variable.

Note that if we make it through the outer for loop without returning, this is the same as the case when done was false in the original code. So we return false. If we make it past the inner if statement, that's the case when done was true but we didn't recurse. So we return true. If the inner if triggers, that was and is the recursive case. So this has the same behavior as previously.

Sphere vs. Cube

Switching from a cube to a sphere would only save you checking less than half the points. Consider the two dimensional version. The circle contains more than three quarters of the points in the enclosing square. This is because the area of the circle is \$\pi r^2\$ while the area of the square is \$(2r^2) = 4r^2\$. That means that \$\frac{\pi}{4}\$ of the points in the square are inside the circle. It's possible that the math to calculate the points at the border of the sphere is less difficult to calculate than the iterative version, but it's not definite.

Don't keep passing the same value

Note that if you made a class to handle this (e.g. @Edward's suggestion of an iterator), you could stop passing around the radius and construct the square of the radius only once. And of course an iterator wouldn't return a Boolean value when what you really want is a side effect. And you wouldn't have to initialize it to a specific value to get the right answer.

\$\endgroup\$

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.