>>>> To solve the "rebonding" problem I built a prototype of a binary
>>>> partitioning tree to hold the points. This is an effecient data
>>>> structure which provides access to points which are "near" other
> If someone could point me to this (in the CDK CVS tree?), I'd
> appreciate it. This sounds like it could help out Open Babel too.
It is not checked-in to the CDK source yet. I've attached the source code.
It is pretty small and is a single .java file.
It does not have any comments in it yet ... so let me know if you have
Most BSP tree applications deal with complex objects. In the case of
molecules, we are only dealing with points. That makes it relatively
straightforward (as BSP trees go.)
There is an older BSP tree FAQ floating around on the web which is
probably a good read. It is a bit too complicated because it deals with
storing triangles. But it is pretty good background material. Search the
web for "bsp tree faq".
Within jmol, the time for "rebonding" hemoglobin.pdb (4500 atoms) dropped
from 6.5 seconds to 200 ms. That included the time to build the tree from
I'll be glad to answer any questions you may have about the implementation.
> In Open Babel, this happens in
> OBMol::ConnectTheDots(). The basic algorithm looks for atom pairs close
> "enough" to each other. The criteria comes from the van der Waal radii
> of the two atoms, plus a 0.4 Angstrom "slop" factor. Atoms too close
> together are ignored, and a pass is made to ensure atoms don't have
> more bonds than their normal valences.
Thanks for the reference.
> Assigning bond orders is done via Roger Sayle's "Cruft to Content"
> algorithm: http://www.daylight.com/meetings/mug01/Sayle/m4xbondage.html
Good deal. I'll check this out.