I'm trying to implement the broad phase of my collision detection algorithm. My game is an arcade game with lot of moving entities in an open space with relatively equivalent sizes.

Regarding the above specifications, i decided to use an uniform grid for space partitioning. The problem i have right know is how to efficiently choose in which cells an entity should be added. ATM i'm doing something like this:

for (int x = 0; x < gridSize; x++) {
    for (int y = 0; y < gridSize; y++) {
        GridCell cell = grid[x][y];
        cell.clear(); //remove the previously added entities
        for (int i = 0; i < entities.size(); i++) {
            Entity e = entities.get(i);
            if (cell.isEntityOverlap(e)) {
                cell.add(e);
            }
        }
   }
}

The isEntityOverlap is a simple method i added my GridCell class.

public boolean isEntityOverlap(Shape s) {
    return cellArea.intersects(s);
}

Where cellArea is a Rectangle.

cellArea = new Rectangle(x, y, CollisionGrid.CELL_SIZE, CollisionGrid.CELL_SIZE);

It works but it's damn slow. What would be a fast way to know all the cells an entity overlaps?

Note: by "it works" i mean, the entities are contained in the good cells over the time after movements etc.