org.jmol.bspt
Class Bspt

java.lang.Object
  extended by org.jmol.bspt.Bspt

public final class Bspt
extends Object

a Binary Space Partitioning Tree

The tree partitions n-dimensional space (in our case 3) into little boxes, facilitating searches for things which are *nearby*.

For some useful background info, search the web for "bsp tree faq". Our application is somewhat simpler because we are storing points instead of polygons.

We are working with three dimensions. For the purposes of the Bspt code these dimensions are stored as 0, 1, or 2. Each node of the tree splits along the next dimension, wrapping around to 0.

    mySplitDimension = (parentSplitDimension + 1) % 3;
  
A split value is stored in the node. Values which are <= splitValue are stored down the left branch. Values which are >= splitValue are stored down the right branch. If searchValue == splitValue then the search must proceed down both branches.

Planar and crystaline substructures can generate values which are == along one dimension.

To get a good picture in your head, first think about it in one dimension, points on a number line. The tree just partitions the points. Now think about 2 dimensions. The first node of the tree splits the plane into two rectangles along the x dimension. The second level of the tree splits the subplanes (independently) along the y dimension into smaller rectangles. The third level splits along the x dimension. In three dimensions, we are doing the same thing, only working with 3-d boxes.

Author:
Miguel, miguel@jmol.org

Field Summary
(package private)  int dimMax
           
(package private)  Element eleRoot
           
(package private) static int leafCountMax
           
(package private) static int MAX_TREE_DEPTH
           
(package private)  int treeDepth
           
 
Constructor Summary
Bspt(int dimMax)
          Create a bspt with the specified number of dimensions.
 
Method Summary
 void addTuple(Point3f tuple)
          Iterate through all of your data points, calling addTuple
 CubeIterator allocateCubeIterator()
           
 void dump()
           
 void stats()
          prints some simple stats to stdout
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

leafCountMax

static final int leafCountMax
See Also:
Constant Field Values

MAX_TREE_DEPTH

static final int MAX_TREE_DEPTH
See Also:
Constant Field Values

treeDepth

int treeDepth

dimMax

int dimMax

eleRoot

Element eleRoot
Constructor Detail

Bspt

public Bspt(int dimMax)
Create a bspt with the specified number of dimensions. For a 3-dimensional tree (x,y,z) call new Bspt(3).

Parameters:
dimMax -
Method Detail

addTuple

public void addTuple(Point3f tuple)
Iterate through all of your data points, calling addTuple

Parameters:
tuple -

stats

public void stats()
prints some simple stats to stdout


dump

public void dump()

toString

public String toString()
Overrides:
toString in class Object

allocateCubeIterator

public CubeIterator allocateCubeIterator()