[SciPy-Dev] Periodic Boundary Conditions and kd-trees

[Patrick Varilly]

Hi,

I am writing to ask for some guidance / advice with modifying SciPy's
kd-tree code.  I'm writing a Python code with SciPy that deals with a set
of points in 3D.  For each one of them, I need to list which other points
are within a distance r.  The trouble is that the points are in a periodic
box, so "distance between x and y" means "distance between x and closest
image of y".  Currently, I'm using code that does a dumb O(N^2) brute force
search, and was about to code up a cell list to replace it (cell lists are
commonly used for this in molecular dynamics codes).  However, KD-trees
seem like a much more generally useful structure for this, and SciPy
already implements kd-trees for open boundary conditions.  Since periodic
boundary conditions (PBCs) are quite common in most molecular simulation
and analysis codes, having PBC-aware kd-trees would be useful to a large
number of users.

I am thinking of modifying scipy.spatial.kdtree to adapt it to periodic
boundary conditions, and would like to ask if anyone else has done this or
something similar to it already.  If not, is there any advice that can be
had on potential problems that can come up that I should know about before
embarking on this modification?  My goal would be to contribute this change
back to SciPy, so any advice on what the most SciPythonic way of exposing
PBCs in the kd-tree interface would also be welcome.

Thanks,

Patrick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20120301/f84ab69e/attachment.html>