Package org.openscience.cdk.graph.rebond
Class Bspt
- java.lang.Object
-
- org.openscience.cdk.graph.rebond.Bspt
-
public final class Bspt extends Object
BSP-Tree stands for 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. When this happens, the search must proceed down both branches. Planar and crystalline 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.
Three enumerators are provided
- enumNear(Bspt.Tuple center, double distance)
returns all the points contained in of all the boxes which are within distance from the center. - enumSphere(Bspt.Tuple center, double distance)
returns all the points which are contained within the sphere (inclusive) defined by center + distance - enumHemiSphere(Bspt.Tuple center, double distance)
same as sphere, but only the points which are greater along the x dimension
- Author:
- Miguel Howard
- Source code:
- main
- Belongs to CDK module:
- standard
- Keywords:
- rebonding, Binary Space Partitioning Tree, join-the-dots
- Created on:
- 2003-05
- enumNear(Bspt.Tuple center, double distance)
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static interface
Bspt.Tuple
-
Constructor Summary
Constructors Constructor Description Bspt(int dimMax)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addTuple(Bspt.Tuple tuple)
protected void
dump()
protected Enumeration
enumeration()
protected org.openscience.cdk.graph.rebond.Bspt.EnumerateSphere
enumHemiSphere(Bspt.Tuple center, double distance)
protected Enumeration
enumNear(Bspt.Tuple center, double distance)
protected org.openscience.cdk.graph.rebond.Bspt.EnumerateSphere
enumSphere(Bspt.Tuple center, double distance)
String
toString()
-
-
-
Method Detail
-
addTuple
public void addTuple(Bspt.Tuple tuple)
-
dump
protected void dump()
-
enumeration
protected Enumeration enumeration()
-
enumNear
protected Enumeration enumNear(Bspt.Tuple center, double distance)
-
enumSphere
protected org.openscience.cdk.graph.rebond.Bspt.EnumerateSphere enumSphere(Bspt.Tuple center, double distance)
-
enumHemiSphere
protected org.openscience.cdk.graph.rebond.Bspt.EnumerateSphere enumHemiSphere(Bspt.Tuple center, double distance)
-
-