maspack.geometry

Class SpatialHashTable<T>

java.lang.Object

maspack.geometry.SpatialHashTable<T>

public class SpatialHashTable<T>
extends java.lang.Object

Spatial Hash Table for speeding up 3D spatial nearest neighbour searches.

3D space is partitioned into an orthogonal, equally spaced grid. Each grid point is the centre of a "cell", which is essentially a List<T>. To search for elements T near a point P, the cell containing P, AND the cells that neighbour the cell containing P must be searched. These cells can be easily found by calling getCellsNear or getCellsIntersecting, which returns an Iterator<List<T>>, where each List<T> represents the elements in a single cell.

Grid spacing is defined upon construction, and construction is performed by calling setup().

Example usage:

 List<T> myElements;
 ...
 SpatialHashTable<T> table = new SpatialHashTable<>(spacing);
 
 List<Point3d> positions = new ArrayList<Point3d>();
 for (T el : myElements) {
    positions.add(el.getPos());
 }
 
 table.setup(positions,elements); // construct map 
 
 Point3d mySearchPoint = new Point3d(0., 1., 2.);
 
 Iterator<List<T>> it = table.getCellsNear (searchPoint);
 while (it.hasNext()) {
    List<T> cell = it.next();
    for (T el : cell) {
       el.doSomething();
    }
 }
 

Author:

andrew ho

Constructor Summary

Constructors

Constructor and Description
SpatialHashTable(double gridSpacing)

Method Summary

Modifier and Type	Method and Description
java.util.List<T>	getElsNear(Point3d pos) Return an iterator which iterates through 27 cells.
void	setup(java.util.List<? extends Point3d> positions, java.util.List<? extends T> elements) Replace the current map with a new one generated from positions and elements.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SpatialHashTable

public SpatialHashTable(double gridSpacing)

Method Detail

setup

public void setup(java.util.List<? extends Point3d> positions,
                  java.util.List<? extends T> elements)

Replace the current map with a new one generated from positions and elements.

Parameters:

positions - List of positions that determine the position of each element in elements

elements - List of elements which will populate this SpatialHashTable

getElsNear

public java.util.List<T> getElsNear(Point3d pos)

Return an iterator which iterates through 27 cells. Iterates through the 27 cells which include and are adjacent to the cell containing pos.

Parameters:

pos - A position in the centre bin.

Returns:

Iterator for 27 bins.