Spatial grid of objects

I'm using this class so that objects can find other objects that are near them. Each object has a position and radius. Objects are added to the Grid. If they move then they call update with their new position. An object can call retrieve to find which objects are around it. How can I optimize it, specifically the retrieve function?

```
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Arrays;

public class Grid {

private Map> objects = new HashMap<>();
private Set retrievedObjects = new HashSet<>();
float size;
int divisions;

public Grid(float size, int divisions) {
this.size = size;
this.divisions = divisions;
}

public void update(Obj obj) {
if (!obj.grids.equals(getGridsObjIsIn(obj.position, obj.radius))) {
remove(obj);
insert(obj);
}
}

public void insert(Obj obj) {
obj.grids = getGridsObjIsIn(obj.position, obj.radius);

for (Integer grid : obj.grids) {
if (objects.containsKey(grid)) {
objects.get(grid).add(obj);
} else {
objects.put(grid, new HashSet(Arrays.asList(obj)));
}
}
}

public void remove(Obj obj) {
for (Integer grid : obj.grids) {
objects.get(grid).remove(obj);
}
obj.grids.clear();
}

public Set retrieve(Vector2 pos, float radius) {
retrievedObjects.clear();
Set grids = getGridsObjIsIn(pos, radius);

for (Integer grid : grids) {
if (objects.containsKey(grid)) {
retrievedObjects.addAll(objects.get(grid));
}
}

return retrievedObjects;
}

private Set getGridsObjIsIn(Vector2 pos, float radius) {
Set grids = new HashSet<>();

int[] min = positionToGrid(pos.x - radius, pos.y - radius);
int[] max = positionToGrid(pos.x + radius, pos.y + radius);

Comments

It is of course better to write self-documenting code that does not require comments. However, sometimes we can't quite meet that goal.

float size;
    int divisions;

What are these? My first thought is that they are the size of a grid square in pixels or some other unit and the number of grid squares in a row or column. I don't know what the unit is for the size. And my length/width hypothesis gets confused when I see code like

grids.add(x + y * divisions * divisions);

Why divisions * divisions? If it were just divisions, I'd think that this was just a Cartesian plane. Then y would represent a row, and x would be the place in the row. So basically converting the two-dimensional grid into one-dimension. So a value of divisions - 1 would be next to divisions in the single dimension but would represent the last element of the y = 0 row and the first element of the y = 1 row in two dimensions.

As is, this means something different, and I'm not sure what. Comments could help clarify this, not just for me as a reviewer but for you in six months when you've forgotten why you did things this way. You don't need to comment every line, but if you feel clever for the way you did something, comment that. Because the next person who edits the code (which may be you) won't be nearly as clever as you are at that moment.

What's an Obj?

You don't include the code for Obj, so I'm not really sure what it is. A less generic name might help.

Fields vs. local variables

private Set retrievedObjects = new HashSet<>();

Why is this an object field? It's used in exactly one method, cannot be retrieved outside that method, and is reset in the method. If you replaced it with a local variable, nothing else about this code would change.

The one difference is that if you call retrieve a second time, the values in the set might change. That seems rather confusing. You could be iterating over the set, trigger a retrieve, and your iterator is now pointing to an invalid location. That seems more problematic than keeping up to date is helpful. Particularly as retrieve takes different parameters. So the set may change because the parameters are different rather than because what the set represents has changed.

Sparse

This grid is sparsely populated. You use a Map to hold it, so you only need to remember the locations where it is populated. This saves a lot of memory at the cost of some speed. If you find yourself with plenty of memory and constrained by time, consider switching to a different data structure, e.g. a two dimensional array.

Another question is if the Map helps you at all. You could simply iterate over the list of objects instead. That might be faster, as you only need to know if the objects conflict. You actually check each possible conflict and then merge the results. So if an object is in a hundred squares and another is in fifty, you might do fifty merges. Consider

for (Obj o : allObjects) {
    if (distance(o, obj) < o.radius + obj.radius) {
        retrievedObjects.add(o);
    }
}

That checks more objects but may do fewer merges.

A side effect of this is that the radius would become an actual radius. I would expect a radius to be part of the definition of a circle, but in the current code, it defines a square. If you really want a square, you can still simplify things. Consider

int objMinX = Math.max(0, obj.x - obj.radius);
    int objMinY = Math.max(0, obv.y - obj.radius);
    int objMaxX = Math.min(divisions - 1, obj.x + obj.radius);
    int objMaxY = Math.min(divisions - 1, obv.y + obj.radius);
    for (Obj o : allObjects) {
        if (hasOverlap(objMinX, objMaxX, o.x - o.radius, o.x + o.radius)
                && hasOverlap(objMinY, objMaxY, o.y - o.radius, o.y + o.radius)) {
            retrievedObjects.add(o);
        }
    }

and later

public static boolean hasOverlap(int minA, int maxA, int minB, int MaxB) {
    return maxA >= minB && minA <= maxB;
}

Another option would be to switch from Map to NavigableMap>. Then you could do the query more like a two dimensional array.

The important thing is to test these to see which performs best for you. This is not a case of a one size fits all solution. The best solution is going to be dependent on the exact characteristics of your data. How sparsely filled is your grid? How many objects are there? Two large objects in a grid would suggest that iterating over all objects is best. A grid where every square is covered but with small objects might suggest a different solution.

StackExchange Code Review Q#160973, answer score: 2