org.gicentre.utils.geom

## Class HashGrid<E extends Locatable>

- java.lang.Object
- - 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.4, 5th February, 2016.
  Author:
    Jo Wood, giCentre, City University London.

- - ### Constructor Summary

    Constructors
    Constructor and Description
    `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

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `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`

    - ### Methods inherited from interface java.util.Set

      `spliterator`

    - ### Methods inherited from interface java.util.Collection

      `parallelStream, removeIf, stream`

    - ### Methods inherited from interface java.lang.Iterable

      `forEach`

- - ### 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 `Set`s 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.