An answer to this question on Stack Overflow.

Question

I have a function that calculates spatial hash as follows:

int generateHash(int x, int y, int bucketWidth, int bucketsPerSide)
{
    return static_cast<int>(floor(x / bucketWidth) + floor(y / bucketWidth) * bucketsPerSide);
}

I have a bounding box defined as x,y,width,height and I'd like to retrieve all hashes for it. How can I do it? The problem seems trivial but I spent all day trying to figure it out and I just can't find a solution. It makes me feel hopeless.

Please note that the box can be so large that it will have more than 4 hashes (corners) assigned to it. I need to generate all hashes including the ones inside.

The dumb solution would be to start from x and y and increment both by 1 in a nested loop and add to std::set to ensure that each hash appear only once but this is extremely inefficient. I know there must be some better way to do it. I tried incrementing by bucketWidth but then it doesn't generate hashes for the rightmost side in some cases.

The closest I got is this:

std::vector<int> getOccupiedBucketIds(const cv::Rect& rect)
{
    std::vector<int> occupiedBucketIds;
    auto xIncrement = rect.width < bucketWidth  ? rect.width : bucketWidth ;
    auto yIncrement = rect.height < bucketWidth ? rect.height : bucketWidth ;
    for (auto x = rect.x; x <= rect.x + rect.width; x += xIncrement)
    {
        for (auto y = rect.y; y <= rect.y + rect.width; y += yIncrement)
        {
            occupiedBucketIds.push_back(generateHash(x, y, bucketWidth , cellsPerSide));
        }
    }
    return occupiedBucketIds;
}

This however leaves the following case unsolved when rect.width%bucketWidth > 0:

Answer

You want something like this:

std::vector<hash_t> hashes;
for(double yi=y+bucket_width/2;yi<ymax;yi+=bucket_width)
for(double xi=x+bucket_width/2;xi<xmax;xi+=bucket_width)
  hashes.push_back(generateHash(xi,yi,bucket_width,buckets_per_side));

You're not getting the rightmost edge because you are using floating-point mathematics. That is, when you are calculating numbers close to the edges of cells they may be slightly smaller, or slightly larger, than you would expect.

The solution is to instead calculate the locations of the centers of cells, which are far away from the edges.