org.gicentre.utils.geom
Class HashGrid<E extends Locatable>

java.lang.Object
  extended by org.gicentre.utils.geom.HashGrid<E>
Type Parameters:
E - Type of locatable objects stored in the hash grid.
All Implemented Interfaces:
java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>

public class HashGrid<E extends Locatable>
extends java.lang.Object
implements java.util.Set<E>

Class to allow the division of a set of 2d spatial objects into a coarser grid for efficient spatial indexing. The collection is a set, so will contain a unique set of objects. Efficient retrieval is achieved by using the get() method that will return only those items that are within a fixed distance of a given location. That fixed distance is determined by the radius of the hash grid. The radius should be set to the maximum search distance that an application is likely to need when performing a spatial query. Generally, the smaller the radius the quicker the retrieval.

Version:
3.3, 30th July, 2012.
Author:
Jo Wood, giCentre, City University London.

Constructor Summary
HashGrid(float maxX, float maxY, float radius)
          Creates a hash grid capable of storing items located within a rectangle between (0,0) and (maxX,maxY) with a grid resolution determined by the radius.
HashGrid(float minX, float minY, float maxX, float maxY, float radius)
          Creates a hash grid capable of storing items located within a rectangle between (minX,minY) and (maxX,maxY) with a grid resolution determined by the radius.
 
Method Summary
 boolean add(E obj)
          Adds a locatable object to the grid.
 boolean add(E obj, Locatable loc)
          Adds a locatable object to the grid.
 boolean addAll(java.util.Collection<? extends E> collection)
          Adds a collection of locatable objects to the hash grid.
 void clear()
          Clears out the contents of the grid.
 boolean contains(E obj, processing.core.PVector location)
          Reports whether the hash grid contains the given locatable object within the radius of the given location.
 boolean contains(java.lang.Object obj)
          Reports whether the hash grid contains the given object.
 boolean containsAll(java.util.Collection<?> collection)
          Reports whether the hash grid contains all of the objects contained in the given collection.
 boolean equals(java.lang.Object obj)
          Reports whether this collection is equal to the given object.
 java.util.Set<E> get(processing.core.PVector location)
          Returns a collection of the locatable objects that are within the radius of the given location.
 java.util.Set<E> getAll()
          Returns a set of all objects stored in the hash grid.
 processing.core.PVector getGridCoord(processing.core.PVector location)
          Provides the hqshgrid coordinates of the given location.
 int hashCode()
          Reports the hash code of the entire collection.
 boolean isEmpty()
          Reports whether or not this hash grid contains any elements.
 java.util.Iterator<E> iterator()
          Provides an iterator to iterate through all the items stored in this hash grid.
 boolean remove(java.lang.Object obj)
          Removes the given object from the hash grid.
 boolean removeAll(java.util.Collection<?> collection)
          Removes the objects in the given collection from the hash grid.
 boolean retainAll(java.util.Collection<?> collection)
          Would strip all items from the hash grid apart from those contained in the given collection but is currently not supported by the hash grid.
 int size()
          Reports the number of unique items stored in this hash grid.
 java.lang.Object[] toArray()
          Provides an array representation of the items in this hash grid.
<T> T[]
toArray(T[] a)
          Provides an array representation of the items in this hash grid.
 void update(E obj)
          Updates the positions of the given item in the hash grid so that its gridded location reflects its new location.
 void updateAll()
          Updates the positions of all items in the hash grid so that their gridded location reflects the location stored inside the Locatable objects.
 void updateAll(float newRadius)
          Updates the positions of all items in the hash grid so that their gridded location reflects the location stored inside the Locatable objects.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

HashGrid

public HashGrid(float maxX,
                float maxY,
                float radius)
Creates a hash grid capable of storing items located within a rectangle between (0,0) and (maxX,maxY) with a grid resolution determined by the radius.

Parameters:
maxX - Largest x coordinate of locatable objects.
maxY - Largest y coordinate of locatable objects.
radius - Size of 1 grid cell in the same units as the preceding min and max parameters. If 0 or negative the HashGrid defaults to a radius of one tenth of the width of the grid. For optimum performance, the radius should be set to the maximum search distance of any spatial object detection. If it is set to be less than this, some adjacent neighbours may be missed when searching. If greater than this, searching will return more neighbours than necessary and impede performance for dense collections of locatable objects.

HashGrid

public HashGrid(float minX,
                float minY,
                float maxX,
                float maxY,
                float radius)
Creates a hash grid capable of storing items located within a rectangle between (minX,minY) and (maxX,maxY) with a grid resolution determined by the radius.

Parameters:
minX - Smallest x coordinate of locatable objects.
minY - Smallest y coordinate of locatable objects.
maxX - Largest x coordinate of locatable objects.
maxY - Largest y coordinate of locatable objects.
radius - Size of 1 grid cell in the same units as the preceding min and max parameters. If 0 or negative the HashGrid defaults to a radius of one tenth of the width of the grid. For optimum performance, the radius should be set to the maximum search distance of any spatial object detection. If it is set to be less than this, some adjacent neighbours may be missed when searching. If greater than this, searching will return more neighbours than necessary and impede performance for dense collections of locatable objects.
Method Detail

get

public java.util.Set<E> get(processing.core.PVector location)
Returns a collection of the locatable objects that are within the radius of the given location. radius is that defined in the constructor or by the most recent call to updateAll(radius).

Parameters:
location - Location to query.
Returns:
Collection of the locatable objects that are within the radius of the given coordinates. If no objects found, an empty collection is returned.

contains

public boolean contains(E obj,
                        processing.core.PVector location)
Reports whether the hash grid contains the given locatable object within the radius of the given location.

Parameters:
obj - Object to search for.
location - Location to query.
Returns:
True if the hash grid contains the given object within the radius of the given location.

getAll

public java.util.Set<E> getAll()
Returns a set of all objects stored in the hash grid. There is no guarantee of the order of items returned within this set.

Returns:
Set of unique objects stored by the hash grid.

updateAll

public void updateAll()
Updates the positions of all items in the hash grid so that their gridded location reflects the location stored inside the Locatable objects. This method is useful if all or many of the objects have changed location since being added to the hash grid. If only one object has changed consider calling update(E obj).


updateAll

public void updateAll(float newRadius)
Updates the positions of all items in the hash grid so that their gridded location reflects the location stored inside the Locatable objects. This version also sets a new grid resolution implied by the newRadius value. This should represent the maximum search distance used when calling get(PVector).

Parameters:
newRadius - New grid cell radius corresponding to maximum search distance. No change to the radius is made if the value is 0 or negative.

update

public void update(E obj)
Updates the positions of the given item in the hash grid so that its gridded location reflects its new location. This method is useful if a Locatable object has changed its position, but most of the other objects in the hash grid have not.

Parameters:
obj - Locatable object to be updated.

add

public boolean add(E obj)
Adds a locatable object to the grid. Note that the object being added must implement the Locatable interface, otherwise a ClassCastException will be thrown.

Specified by:
add in interface java.util.Collection<E extends Locatable>
Specified by:
add in interface java.util.Set<E extends Locatable>
Parameters:
obj - Locatable object to add to the hash grid.
Returns:
True if the collection has changed as a result of the object being added.

add

public boolean add(E obj,
                   Locatable loc)
Adds a locatable object to the grid. Unlike add(E) this allows a locatable object to be added at a location other than it's 'natural' one. Note that the object being added must implement the Locatable interface, otherwise a ClassCastException will be thrown.

Parameters:
obj - Locatable object to add to the hash grid.
loc - Location of the object to add to the grid.
Returns:
True if the collection has changed as a result of the object being added.

addAll

public boolean addAll(java.util.Collection<? extends E> collection)
Adds a collection of locatable objects to the hash grid.

Specified by:
addAll in interface java.util.Collection<E extends Locatable>
Specified by:
addAll in interface java.util.Set<E extends Locatable>
Parameters:
collection - Collection of objects to add to the collection.
Returns:
Reports whether collection has been changed by the operation.

clear

public void clear()
Clears out the contents of the grid.

Specified by:
clear in interface java.util.Collection<E extends Locatable>
Specified by:
clear in interface java.util.Set<E extends Locatable>

contains

public boolean contains(java.lang.Object obj)
Reports whether the hash grid contains the given object. While this will return results as expected, for more efficient query consider using contains(obj,location) instead to limit search to within the search radius.

Specified by:
contains in interface java.util.Collection<E extends Locatable>
Specified by:
contains in interface java.util.Set<E extends Locatable>
Parameters:
obj - Object to search for.
Returns:
True if collection contains the given object.

containsAll

public boolean containsAll(java.util.Collection<?> collection)
Reports whether the hash grid contains all of the objects contained in the given collection. Note that this operation ignores the grid cells of the objects. To limit a search to a particular spatial region call get(location) and search the returned collection.

Specified by:
containsAll in interface java.util.Collection<E extends Locatable>
Specified by:
containsAll in interface java.util.Set<E extends Locatable>
Parameters:
collection - Collection of objects to search for.
Returns:
True if the hash grid contains all of the items in the given collection.

equals

public boolean equals(java.lang.Object obj)
Reports whether this collection is equal to the given object. If the given object is another HashGrid the comparison is performed on the Sets contained in the hash grids. In other words, it is independent of the spatial locations of the objects stored in the hash grid. The only other type of object that could possibly return true would be a Set.

Specified by:
equals in interface java.util.Collection<E extends Locatable>
Specified by:
equals in interface java.util.Set<E extends Locatable>
Overrides:
equals in class java.lang.Object
Parameters:
obj - Object to compare with this hash grid.
Returns:
True if the given object contains a set that is equal to the set stored in this hash grid.

hashCode

public int hashCode()
Reports the hash code of the entire collection.

Specified by:
hashCode in interface java.util.Collection<E extends Locatable>
Specified by:
hashCode in interface java.util.Set<E extends Locatable>
Overrides:
hashCode in class java.lang.Object
Returns:
Hash code of the set of objects stored in this hash grid.

isEmpty

public boolean isEmpty()
Reports whether or not this hash grid contains any elements.

Specified by:
isEmpty in interface java.util.Collection<E extends Locatable>
Specified by:
isEmpty in interface java.util.Set<E extends Locatable>
Returns:
True if this hash grid is empty.

iterator

public java.util.Iterator<E> iterator()
Provides an iterator to iterate through all the items stored in this hash grid. Note that this will not guarantee iterating in any spatial order. To perform a spatial iteration, make calls to get(location) in some spatial order and then iterate though the resulting collections.

Specified by:
iterator in interface java.lang.Iterable<E extends Locatable>
Specified by:
iterator in interface java.util.Collection<E extends Locatable>
Specified by:
iterator in interface java.util.Set<E extends Locatable>
Returns:
Iterator for the objects stored in this hash grid.

remove

public boolean remove(java.lang.Object obj)
Removes the given object from the hash grid.

Specified by:
remove in interface java.util.Collection<E extends Locatable>
Specified by:
remove in interface java.util.Set<E extends Locatable>
Parameters:
obj - Object to remove.

removeAll

public boolean removeAll(java.util.Collection<?> collection)
Removes the objects in the given collection from the hash grid.

Specified by:
removeAll in interface java.util.Collection<E extends Locatable>
Specified by:
removeAll in interface java.util.Set<E extends Locatable>
Parameters:
collection - Collection of objects to remove.

retainAll

public boolean retainAll(java.util.Collection<?> collection)
Would strip all items from the hash grid apart from those contained in the given collection but is currently not supported by the hash grid. To limit the operation to certain grid cells, call get(location) and perform the retainsAll() on the returned collection.

Specified by:
retainAll in interface java.util.Collection<E extends Locatable>
Specified by:
retainAll in interface java.util.Set<E extends Locatable>

size

public int size()
Reports the number of unique items stored in this hash grid.

Specified by:
size in interface java.util.Collection<E extends Locatable>
Specified by:
size in interface java.util.Set<E extends Locatable>

toArray

public java.lang.Object[] toArray()
Provides an array representation of the items in this hash grid. Note that this does not guarantee any form of spatial ordering of items.

Specified by:
toArray in interface java.util.Collection<E extends Locatable>
Specified by:
toArray in interface java.util.Set<E extends Locatable>
Returns:
Array of objects.

toArray

public <T> T[] toArray(T[] a)
Provides an array representation of the items in this hash grid. Note that this does not double count any items that may have been repeated in more than one grid cell and does not guarantee any form of spatial ordering of items. The runtime type of the returned array is that of the given array. If the collection fits in the given array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the given array and the size of this collection. If this collection fits in the given array with room to spare (i.e. the array has more elements than this collection), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of this collection only if the caller knows that this collection does not contain any null elements.)

Specified by:
toArray in interface java.util.Collection<E extends Locatable>
Specified by:
toArray in interface java.util.Set<E extends Locatable>
Returns:
Array of objects.

getGridCoord

public processing.core.PVector getGridCoord(processing.core.PVector location)
Provides the hqshgrid coordinates of the given location. This is not normally needed when using a hashgrid, but is provided for debugging purposes.

Parameters:
location - The location to query.
Returns:
Hash grid coordinates in (column, row) order in which the given location sits.


giCentre Utilities V.3.3, API documentation generated 6th April, 2013