KD Tree

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

class KDTree(coords, **kwargs)

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 using getIndices() and getDistances().

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 3-dimensional space) and unique indices with the minimum distance from them to the center are returned.

 _____________________________
|        1|        2|        3|
|       ? |       ? |      ?  |
|_________|_________|_________|
|        4|o  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 2-d) replicas of the system coordinates. A KDTree is built for the system (O and H) and all its replicas (o and h). After pair search is performed, unique pairs of indices and minimum distance between them are returned.

  _____________________________
 |o  h h  1|o  h h  2|o  h h  3|
h| h  o   h| h  o   h| h  o    |
 |_________|_________|_________|
 |o  h h  4|O  H H  5|o  h h  6|
h| h  o   H| H  O   h| h  o    |
 |_________|_________|_________|
 |o  h h  7|o  h h  8|o  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

getCount()

Returns number of points or pairs.

getDistances()

Returns array of distances.

getIndices()

Returns array of indices for points or pairs, depending on the type of the most recent search.

search(radius, center=None)

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