public interface ISpatialDataStructure {

   
   public void add(Entity entity);

   public void remove(Entity entity);
   
   public void collide();
   
   public void update(float dt);
   
   public void draw(Graphics graphics);
   
}

$ java org.game.CollisionTest 
Exception in thread "main" java.lang.NoClassDefFoundError: org/newdawn/slick/BasicGame

ISpatialDataStructure dataStructure = new LooseGrid(200, 200, 100, 100);

package org.game.collision.datastructures;

import java.util.ArrayList;


public class LooseGrid implements ISpatialDataStructure {

   float cellWidth = 0;
   float cellHeight = 0;
   
   private class Cell {
      
      
      Rectangle bounds = new Rectangle(0, 0, 0, 0);
      
      ArrayList<Entity> objects = new ArrayList<Entity>();
      
      
      public Cell(int i, int j) {
         
         float xOffset = sizeX / 2 * cellWidth;
         float yOffset = sizeY / 2 * cellHeight;
         
         bounds.setBounds( -xOffset + i * cellWidth, -yOffset + j * cellWidth, cellWidth, cellHeight);
      }
      
      public void add(Entity entity) {
         objects.add(entity);
      }
      
      public void remove(Entity entity) {
         objects.remove(entity);
      }
      
      public void draw(Graphics graphics) {
         
         if(debug) {
            graphics.setColor(Color.yellow);
            graphics.draw(bounds);
         }
         
         for (Entity entity : objects) {
            entity.draw(graphics);
         }
         
      }
      
      public int getNumObjects() {
         return objects.size();
      }
      
      
      
      public void collide(ArrayList<Collision> collisions) {
         
         for (Entity entity : objects) {
            float xWorldOffset = sizeX / 2 * cellWidth;
            float yWorldOffset = sizeY / 2 * cellHeight;

            int x = (int)((xWorldOffset + entity.getPositionX()) / cellWidth);
            int y = (int)((yWorldOffset + entity.getPositionY()) / cellHeight);   
                  

            for(int i = -1; i <= 1; i++ ) {
               
               int xOffset = x + i;
               
               if(xOffset < 0 || xOffset >= sizeX) break;

               for(int j = -1; j <= 1; j++ ) {
                  int yOffset = y + j;

                  
                  if(yOffset < 0 || yOffset >= sizeY) break;
                  
                     ArrayList<Entity> cellObjects = cells[xOffset][yOffset].objects;
                     
                     for (Entity foreign : cellObjects) {
                        
                        if(entity == foreign) continue;
                        if(entity.intersects(foreign)) {
                           
                           collisions.add(new Collision(entity, foreign));
                        }
                     }

               }         
            }
         }
         
      }
      
      public boolean intersects(Entity entity) {
         return bounds.intersects(entity.getShape());
      }
      
   }

   
   boolean debug = false;
   
   Cell[][] cells = null;

   private int sizeX = 0;
   private int sizeY = 0;
   
   ArrayList<Entity> objects = new ArrayList<Entity>();
   
   public LooseGrid(int sizeX, int sizeY, float cellWidth, float cellHeight, ICollisionStrategy collisionStrategy) {

      this.sizeX = sizeX;
      this.sizeY = sizeY;
      
      cells = new Cell[sizeX][sizeY];
      
      this.cellWidth = cellWidth;
      this.cellHeight = cellHeight;
      
      for(int i = 0; i < cells.length; i++) {
         for(int j = 0; j < cells[i].length; j++) {
            cells[i][j] = new Cell(i, j);
         }
      }   
   }
   
   
   @Override
   public void add(org.game.Entity entity) {
      
      this.objects.add(entity);
      addToCells(entity);
      
   }

   @Override
   public void collide(ArrayList<Collision> collisions) {

      for(int i = 0; i < cells.length; i++) {
         for(int j = 0; j < cells[i].length; j++) {
            if(cells[i][j].getNumObjects() > 0) {
               cells[i][j].collide(collisions);               
            }
         }
      }
      
   }

   @Override
   public void draw(Graphics graphics) {
      
      graphics.setColor(Color.blue);
      graphics.drawRect(-(sizeX/2) * cellWidth, -(sizeY/2) * cellHeight, sizeX*cellWidth, sizeY*cellWidth);
      
      for(int i = 0; i < cells.length; i++) {
         for(int j = 0; j < cells[i].length; j++) {
            if(cells[i][j].getNumObjects() > 0) {
               cells[i][j].draw(graphics);               
            }
         }
      }
      
      
   }

   @Override
   public String getInfo() {
      return "Loose grid data structure by Olli-Pekka";
   }

   @Override
   public boolean isDebugRenderMode() {
      return debug;
   }

   @Override
   public void remove(org.game.Entity entity) {
      objects.remove(entity);
      removeFromCells(entity);
   }

   @Override
   public void setDebugRenderMode(boolean debug) {
      this.debug = debug;
      
   }

   @Override
   public void update(float dt) {
      for (Entity entity : objects) {
         removeFromCell(entity);
         entity.update(dt);   
         addToCell(entity);
      }
      
   }

   @Override
   public float getHeight() {
      return sizeY * cellHeight;
   }

   @Override
   public float getWidth() {
      return sizeX * cellWidth;
   }
   

   
   private void addToCell(Entity entity) {

      float xOffset = sizeX / 2 * cellWidth;
      float yOffset = sizeY / 2 * cellHeight;

      int x = (int)((xOffset + entity.getPositionX()) / cellWidth);
      int y = (int)((yOffset + entity.getPositionY()) / cellHeight);
      
      cells[x][y].add(entity);
         
   
      
   }
   
   
   private void removeFromCell(Entity entity) {
      
      float xOffset = sizeX / 2 * cellWidth;
      float yOffset = sizeY / 2 * cellHeight;

      int x = (int)((xOffset + entity.getPositionX()) / cellWidth);
      int y = (int)((yOffset + entity.getPositionY()) / cellHeight);
      
      cells[x][y].remove(entity);
         
   }
   
   
   
}

public void clear();

package org.game;
import org.game.collision.Collision;

import org.game.collision.datastructures.*;

import org.game.collision.strategies.*;

import org.game.collision.strategies.SweepAndPruneStrategy.SortingAlgorithm;

import java.util.Random;
import java.util.ArrayList;

public class CollisionTest2{
   public static void test(ISpatialDataStructure dataStructure, int entityCount){      
      Entity[] entities = new Entity[entityCount];
      ArrayList<Collision> collisions = new ArrayList<Collision>();
      Random random = new Random();

      float maxWidth = dataStructure.getWidth();
      float maxHeight = dataStructure.getHeight();


      //run 20x50 test updates
      int runs = 20;
      int updatesPerRun = 50;

      long[] times = new long[runs];
      long mean = 0;
      for(int i = 0; i < runs; i++){
         dataStructure.clear();
         //create the entities
         for(int j = 0; j < entityCount; j++) {

            float radius = 10 + random.nextFloat() * 90f; 

            float x = (-dataStructure.getWidth() + radius) / 2 + random.nextFloat() * (dataStructure.getWidth() - 2*radius);

            float y = (-dataStructure.getHeight() + radius) / 2 + random.nextFloat() * (dataStructure.getHeight() - 2*radius);

            x = Math.max(x,-maxWidth/2);

            x = Math.min(x,maxWidth/2);

            y = Math.max(x,-maxHeight/2);

            y = Math.min(x,maxHeight/2);

         

            float velX = random.nextFloat() * 10;

            float velY = random.nextFloat() * 10;

         

            Entity entity = new Entity(dataStructure, x, y, velX, velY, radius);

            entities[j] = entity;

            dataStructure.add(entity);
         }
         //do a run
         long startTime = System.nanoTime();         
         for(int j = 0; j < updatesPerRun; j++){
            dataStructure.update(10);
            dataStructure.collide(collisions);
            collisions.clear();
         }
         times[i] = System.nanoTime()-startTime;
         mean += times[i];
         if((i & 1) == 0){
            System.out.print(".");
            System.out.flush();
         }
      }
      System.out.println("\n"+dataStructure.getInfo());
      mean /= runs;
      long variance = 0;
      for(int i = 0; i < runs; i++)
         variance += (mean-times[i])*(mean-times[i]);
      variance /= runs;
      double standardDeviation = Math.sqrt(variance);
      System.out.println(entityCount+" entities takes "+(mean/1000000)+"ms +/- "+(standardDeviation/1000000));
   }

   public static void main(String[] args){
      int width = 20000;
      int height = 20000;
      //ISpatialDataStructure dataStructure = new ReferenceDataStructure(width, height,new BruteforceStrategy());

      ISpatialDataStructure dataStructure = new ReferenceDataStructure(width, height, new SweepAndPruneStrategy(SortingAlgorithm.InsertionSort));

      //ISpatialDataStructure dataStructure = new RegularQuadtree(width, height, 7, new SweepAndPruneStrategy(SortingAlgorithm.Quicksort));

      test(dataStructure,1000);
   }
}