patvarilly / periodic_kdtree Goto Github PK
View Code? Open in Web Editor NEWSciPy-based kd-tree with periodic boundary conditions
SciPy-based kd-tree with periodic boundary conditions
SciPy-based kd-tree with periodic boundary conditions Copyright 2012 Patrick Varilly. Released under the scipy license Rationale --------- When running and/or analyzing molecular simulations, finding the closest neighbors of a particles is a very common operation. Usually, Verlet lists and/or cell lists are used for this, but these usually work well when the maximum neighbor distance is fixed and not too large. kd-trees are the general answer to the problem of finding nearest neighbors, and SciPy implements kd-trees quite well. However, molecular simulations are usually run in periodic boxes, not open boxes, so the act of finding "close" neighbors must take the periodic boundary conditions into account. This module implements two classes, PeriodicKDTree and PeriodicCKDTree, that work as drop-in replacements for scipy.spatial.KDTree and scipy.spatial.cKDTree, respectively (the latter of these is a Cython-optimized version of a kd-tree but with more limited functionality). For the moment, only the query and query_ball_point methods are implemented. These should see you through most situations in analyzing molecular simulations. Installation ------------ The uwham package relies on NumPy and SciPy to do its work. Make sure these are installed (for Mac OS X users, see note below). Then run the following command inside the uwham directory: python setup.py install --user The query_ball_point method in PeriodicCKDTree relies on the extension to cKDTree I recently wrote for SciPy. See scipy/scipy#262 Basic usage ----------- from periodic_kdtree import PeriodicCKDTree import numpy as np # Boundaries (0 or negative means open boundaries in that dimension) bounds = np.array([30.0, 30.0, -1]) # xy periodic, open along z # Points n = 10000 data = 30.0 * np.random.randn(n, 3) # Build kd-tree T = PeriodicCKDTree(bounds, data) # Find 4 closest neighbors to a random point # (d[j], i[j]) = distance and index of jth closest point d, i = T.query([45.0, 10.0, 10.0], k=4) # Find neighbors within a fixed distance of a point neighbors = T.query_ball_point([45.0, 10.0, 10.0], r=3.0) Tests and benchmarks -------------------- See test_periodic_kdtree.py, benchmark.py and nonperiodic_benchmark.py (based off of Anne M. Archibald's benchmarks) Simple queries seem to be substantially slower for now, but ball lookups aren't that unacceptably slower. Sample periodic benchmarks (time in seconds) ++++++++++++++++++++++++++++++++++++++++++++ dimension 3, 10000 points PeriodicKDTree constructed: 0.0793428 PeriodicCKDTree constructed: 0.00343394 PeriodicKDTree 1000 lookups: 14.8779 PeriodicCKDTree 1000 lookups: 1.73712 flat PeriodicCKDTree 1000 lookups: 14.2604 PeriodicKDTree 1000 ball lookups: 39.7997 PeriodicCKDTree 1000 ball lookups: 0.222894 flat PeriodicCKDTree 1000 ball lookups: 1.23763 Ball lookups agree? True Sample nonperiodic benchmarks +++++++++++++++++++++++++++++ dimension 3, 10000 points KDTree constructed: 0.0820239 cKDTree constructed: 0.00158691 KDTree 1000 lookups: 0.561787 cKDTree 1000 lookups: 0.00447702 flat cKDTree 1000 lookups: 0.335597 KDTree 1000 ball lookups: 5.60061 cKDTree 1000 ball lookups: 0.0196991 flat cKDTree 1000 ball lookups: 0.336687 Ball lookups agree? True Installation in OS X -------------------- In Mac OS X, the usual automatic downloading of dependencies during a python setup.py install isn't able to successfully install NumPy and SciPy (in my machine, it's the lack of a Fortran compiler, but the SciPy docs point to other potential problems). So you have to download and install NumPy and SciPy manually. The good news: binaries are easily available The bad news: they only work with the version of Python from http://www.python.org, not the version that ships with OS X! So you have to download and install three things: 1. Python 2.7.2 from http://www.python.org/download 2. Latest version of NumPy from http://numpy.org 3. Latest version of SciPy from http://scipy.org This is far less painful than it sounds. In my own case, the disk images that I ended up downloading were: 1. python-2.7.2-macosx10.6.dmg 2. numpy-1.6.1-py2.7-python.org-macosx10.6.dmg 3. scipy-0.10.0-py2.7-python.org-macosx10.6.dmg CAREFUL: for some of these packages, the "link to the latest version" that SourceForge suggests may be incorrect! Do look at the full list of downloads available and pick the one that is most appropriate to your own setup Once you've installed python2.7, numpy and scipy, you can run the command python setup.py install --user
I was hesitant, whether or not I should post this; but I feel obligated to at least suggest caution before using this module.
The following is an interpolation of a slice from the middle of a cube of gas from a periodic astrophysical simulation. I used cKDTree and PeriodicCKDTree to interpolate a slice of my irregularly spaced 3D data onto a regular grid. To be clear, these modules were not used in the simulation, just for data analysis.
As can be seen below, the PeriodicCKD module cannot be used as a drop-in replacement for scipy.spatial.cKDTree; it introduces spurious behaviour around the boundaries.
Hi there,
When trying to run your sample codes, I got the following error after command "neighbors = T.query_ball_point([45.0, 10.0, 10.0], r=3.0)".
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Traceback (most recent call last):
File "", line 1, in
File "/usr/local/lib/python2.7/dist-packages/periodic_kdtree-1.0-py2.7.egg/periodic_kdtree.py", line 376, in query_ball_point
return self.__query_ball_point(x, r, p, eps)
File "/usr/local/lib/python2.7/dist-packages/periodic_kdtree-1.0-py2.7.egg/periodic_kdtree.py", line 336, in __query_ball_point
results.extend(super(PeriodicCKDTree, self).query_ball_point(
AttributeError: 'super' object has no attribute 'query_ball_point'
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The command "d, i = T.query([45.0, 10.0, 10.0], k=4)" runs fine. Any sense what's going on here?
It would be very useful to me to have a periodic implementation of sparse_distance_matrix for ckdtree. Do you think is it hard to implement?
Do you have any suggestion on how to proceed?
I think there are scenarios when _gen_relevant_images
misses generation of some needed image. See picture below for a scenario with 2D periodic boundary conditions. The query particle is located at the center of the red circle on the left. The query search radius is r
.
According to periodic_kdtree.py L90-91:
self.max_distance_upper_bound = np.min(
np.where(self.bounds > 0, 0.5 * self.bounds, np.inf))
from the picture, self.max_distance_upper_bound == d
.
Now if we set distance_upper_bound == r
with r
that of the picture, then the capping of this quantity at periodic_kdtree.py L105-106
distance_upper_bound = np.min([distance_upper_bound,
self.max_distance_upper_bound])
will result in distance_upper_bound == d
In the picture, the query particle is located at the center of the red circle on the left. The shaded red area indicates that we will need to add an image, the red-dashed circle. If we go to _gen_relevant_images() and start checking along the X-axis (i=0
) we have that abs(real_x[i]) > d
so condition at line 35 is not met. We also have abs(bounds[i] - real_x[i]) > d
so condition at line 39 is not met either. We end up adding no image.
Hi there,
I tried using your code on my own data and encountered several issues. It appears to boil down to an axis out of bounds issue.
Running your sample code (using python 2.7.3 on linux) returns the following error:
"""
d, i = T.query([45.0, 10.0, 10.0], k=4)
File "/usr/local/lib/python2.7/dist-packages/periodic_kdtree.py", line 306, in query
hits = self.__query(x, k=k, eps=eps, p=p, distance_upper_bound=distance_upper_bound)
File "/usr/local/lib/python2.7/dist-packages/periodic_kdtree.py", line 217, in __query
self.max_distance_upper_bound)
File "/usr/lib/python2.7/dist-packages/numpy/core/fromnumeric.py", line 1894, in amin
return _wrapit(a, 'min', axis, out)
File "/usr/lib/python2.7/dist-packages/numpy/core/fromnumeric.py", line 37, in _wrapit
result = getattr(asarray(obj),method)(_args, *_kwds)
ValueError: axis(=15) out of bounds
"""
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.