KD Tree¶
This module defines KDTree
class for dealing with atomic coordinate
sets and handling periodic boundary conditions.

class
KDTree
(coords, **kwargs)[source]¶ An interface to Thomas Hamelryck’s C KDTree module that can handle periodic boundary conditions. Both point and pair search are performed using the single
search()
method and results are retrieved usinggetIndices()
andgetDistances()
.Periodic Boundary Conditions
Point search
A point search around a center, indicated with a question mark (
?
) below, involves making images of the point in cells sharing a wall or an edge with the unitcell that contains the system. The search is performed for all images of the center (27 in 3dimensional space) and unique indices with the minimum distance from them to the center are returned._____________________________  1 2 3  ?  ?  ?  ___________________________  4o h h 5 6 ? and H interact in periodic image 4  ?H h o ?  ?  but not in the original unitcell (5) ___________________________  7 8 9  ?  ?  ?  ___________________________
There are two requirements for this approach to work: (i) the center must be in the original unitcell, and (ii) the system must be in the original unitcell with parts in its immediate periodic images.
Pair search
A pair search involves making 26 (or 8 in 2d) replicas of the system coordinates. A KDTree is built for the system (
O
andH
) and all its replicas (o
andh
). After pair search is performed, unique pairs of indices and minimum distance between them are returned._____________________________ o h h 1o h h 2o h h 3 h h o h h o h h o  ___________________________ o h h 4O H H 5o h h 6 h h o H H O h h o  ___________________________ o h h 7o h h 8o h h 9 h h o h h o h h o  ___________________________
Only requirement for this approach to work is that the system must be in the original unitcell with parts in its immediate periodic images.
See also
wrapAtoms()
can be used for wrapping atoms into the single periodic image of the system.Parameters:  coords (
numpy.ndarray
,Atomic
,Frame
) – coordinate array with shape(N, 3)
, where N is number of atoms  unitcell (
numpy.ndarray
) – orthorhombic unitcell dimension array with shape(3,)
 bucketsize (int) – number of points per tree node, default is 10

getIndices
()[source]¶ Returns array of indices for points or pairs, depending on the type of the most recent search.

search
(radius, center=None)[source]¶ Search pairs within radius of each other or points within radius of center.
Parameters:  radius (float) – distance (Å)
 center (
numpy.ndarray
) – a point in Cartesian coordinate system
 coords (