Hash grids

A hash grid provides a way of storing objects that have some spatial location so that they can be retrieved efficiently. It is commonly used for collision detection between a large set of objects occupying a limited space. The hash grid will store objects in a standard collection, but can be used to retrieve a subset of those objects that are close to a given location.

Using hash grids in Processing

To use the HashGrid class in your own sketches, you will then need to import it into your sketch with the line

import org.gicentre.utils.geom.*;

For full details of the methods available see the HashGrid API reference. See also, the HashGridExample sketch supplied in the examples folder of the gicentre utilities library.

To create a hash grid, you need to define the minimum and maximum spatial extents of the collection of objects that will be placed inside it. This is typically the width and height of the sketch, although it can be any range if you are going to scale the objects before drawing them. You also need to specify the search radius of the grid. This should correspond the largest distance away from any given location within which you will need to retrieve objects. For collision detection, this will usually correspond to the maximum size of the objects that you are testing.

For example:

hashGrid = new HashGrid(width,height,10);

will create a hash grid capable of storing objects that range from (0,0) to (width,height) in their location and will retrieve objects that are up to 10 pixels away from any given location.

You can add any type of object to a HashGrid using the add() method on the condition that the object being added implements the Locatable interface. This ensures that the object is able to report its location as a Processing PVector.

To retrieve all the objects in the HashGrid that are within the radius of a given location, simply call its get() method, suppling the location to query as a PVector. For example,

Set neighbours = hashGrid.get(new PVector(100,100));

will provide a Java Set containing all the neighbours that are within radius pixels of the location (100,100). This can then be iterated over in your sketch as any normal collection.

If you wish to change the location of the objects that are stored in a hash grid, the HashGrid object needs to be informed of this change so it can reallocate the object internally if necessary. If you only need to change few object locations, call update(obj) where obj is the object that has changed location. If you need to update the locations of a larger number of objects, call updateAll(), which can optionally take a new radius value if you wish to change the maximum search distance. The hashGridExample sketch in the examples folder of gicentreUtils shows this in action.

The following example shows how a hash grid can be used to highlight all the points that are close to the current mouse position. Using a hash grid is much faster than a normal collection because only a small subset of points need to be searched for when retrieving those that are close to the mouse pointer. Dragging the mouse removes points from the hash grid.

Hashgrid used for rapid detection of mouse proximity — **Hashgrid** used for rapid detection of mouse proximity

import org.gicentre.utils.geom.*; 
import java.util.Set;

// Sketch to place points in a hash grid and respond to mouse movement. 
// Version 1.3, 4th November, 2013. 
// Author Jo Wood. 

HashGrid<Dot> hashGrid; 
static final float RADIUS = 50;  // Search radius for hash grid 

// Creates 8000 dot objects and places them in a hash grid. 
void setup() 
{ 
  size(800, 400);
  noFill(); 
  hashGrid = new HashGrid<Dot>(width, height, RADIUS); 

  for (int i=0; i<8000; i++) 
  { 
    hashGrid.add(new Dot(random(width), random(height)));
  }
} 

// Highlights the dots that are near the mouse and removes them
// if the mouse button is pressed.
void draw() 
{ 
  background(255); 
  stroke(0); 
  strokeWeight(2); 

  for (Dot d : hashGrid) 
  { 
    point(d.getLocation().x, d.getLocation().y);
  } 

  Set<Dot> dotsNearMouse = hashGrid.get(new PVector(mouseX, mouseY)); 
  if (mousePressed) 
  { 
    hashGrid.removeAll(dotsNearMouse);
  } 
  else 
  { 
    strokeWeight(6); 
    stroke(120, 20, 20, 200); 

    for (Dot d : dotsNearMouse)
    { 
      point(d.getLocation().x, d.getLocation().y);
    }
  }
} 


// Class for storing a point value. It must implement the Locatable 
// interface since objects of this type will be added to the hash grid. 
class Dot implements Locatable 
{ 
  PVector d; 

  Dot(float x, float y) 
  { 
    d = new PVector(x, y);
  }   

  PVector getLocation() 
  { 
    return d;
  }
}