org.simtk.geometry3d
Class Hash3D<V>

java.lang.Object
  java.util.AbstractMap<K,V>
      java.util.HashMap<Vector3D,V>
          org.simtk.geometry3d.Hash3D<V>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.util.Map<Vector3D,V>

public class Hash3D<V>
extends java.util.HashMap<Vector3D,V>

Container class to speed up finding objects that are near one another in 3D Cartesian space.

This data structure and algorithm can be used to answer the question "Find all pairs of objects withing 50 meters of one another" in linear time and space complexity, O(n), where n is the number of objects. The naive method takes O(n²) time. Linear time complexity can be achieved under the following circumstances:

1) There is an upper bound on the density of objects in the volume. (Collections of objects with arbitrarily high densities may tend to have O(n²) asymptotic *size* complexity for the *answer* to the question "How many pairs with distance less than X, and thus cannot have linear time complexity for producing that answer.)

2) Each object is located at a single distinct point in space. This works well for atoms and other spherically symmetric objects in Cartesian space.

This implementation does NOT require that the objects in the volume satisfy any minimum density criterion, unlike some neighbor list methods in molecular simulation.

Only one object should be placed at each unique position. If another one is placed at the same location, the one that was there earlier will be gone. There may also be a problem with having the same object at multiple positions.

TODO - modify data structure to remove these restrictions.

Set the size parameter in the constructor a bit lower than the distances you intend to query.

A size parameter, s, much larger than the test distance will tend to slow the method by a factor of O(s³).

A size parameter, s, much smaller than the test distance will tend to slow the method by a factor of O((1/s)³ * ln(1/s)). This effect will kick in more slowly than the "s too big" effect.

See Also:

Serialized Form

Constructor Summary

Hash3D(double r)

Method Summary

void	clear()
java.lang.Object	clone()
V	getClosest(Vector3D position, double radius) Return the closest object to a particular position If no object is within the specified radius, return null.
java.util.Collection<Vector3D>	neighborKeys(Vector3D position, double radius) Find positions of all objects within a specified radius of a specified point.
java.util.Collection<V>	neighborValues(Vector3D position, double radius) Find all objects within a specified radius of a specified point This method has constant asymptotic time complexity.
V	put(Vector3D position, V object) Inserts an object into the data structure at a particular position.
java.lang.Object	remove(Vector3D vec) Remove the object at a particular position

Methods inherited from class java.util.HashMap

containsKey, containsValue, entrySet, get, isEmpty, keySet, putAll, remove, size, values

Methods inherited from class java.util.AbstractMap

equals, hashCode, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

equals, hashCode

Constructor Detail

Hash3D

public Hash3D(double r)

Method Detail

put

public V put(Vector3D position,
             V object)

Inserts an object into the data structure at a particular position. This method is the primary means of populating a Hash3D object.

Specified by:

put in interface java.util.Map<Vector3D,V>

Overrides:

put in class java.util.HashMap<Vector3D,V>

Parameters:

position -

object -

Returns:

previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key, if the implementation supports null values.

remove

public java.lang.Object remove(Vector3D vec)

Remove the object at a particular position

Parameters:

vec - the position of the object to remove

clear

public void clear()

Specified by:

clear in interface java.util.Map<Vector3D,V>

Overrides:

clear in class java.util.HashMap<Vector3D,V>

clone

public java.lang.Object clone()

Overrides:

clone in class java.util.HashMap<Vector3D,V>

getClosest

public V getClosest(Vector3D position,
                    double radius)

Return the closest object to a particular position If no object is within the specified radius, return null. This method has constant asymptotic time complexity.

Parameters:

position -

radius -

Returns:

the closest object to the specified point, or null if there are no objects within radius of the point.

neighborValues

public java.util.Collection<V> neighborValues(Vector3D position,
                                              double radius)

Find all objects within a specified radius of a specified point This method has constant asymptotic time complexity.

Parameters:

position -

radius -

Returns:

a collection of all objects within the specified radius of the specified point. If no objects are found, an empty collection is returned.

neighborKeys

public java.util.Collection<Vector3D> neighborKeys(Vector3D position,
                                                   double radius)

Find positions of all objects within a specified radius of a specified point. This method has constant asymptotic time complexity.

Parameters:

position -

radius -

Returns:

collection of all positions at which objects are found within the specified radius of the specified point. Returns an empty collection if no objects are found.