## K3Match: A package for fast matching of points in 3D space

K3Match uses an implementation of three dimensional binary trees to efficiently find matches between points in 3D space. Two lists of points are compared and match indices as well as distances are given. K3Match can find either the nearest neighbour or all matches within a given search distance in 3D Cartesian space or on the surface of the 2D unit sphere in standard spherical or celestial coordinates.

## Installing

To install K3Match, including the Python wrappers, download the appropriate package for your operating system. Binary packages are available for most Linux distributions. Users of OSX or Microsoft Windows should choose the source package instead.

For installations from source code, K3Match uses a standard Python distutils installer. Execute the following command in the extracted source code directory to build and install the software.`sudo python setup.py install`

Note that building K3Match needs Numpy version 1.0 or higher as well as a recent version of Python.

For instructions to build K3Match without Python support please see the included INSTALL file.

## Usage

All functions are accessible from C and Python. The Python functions use standard Numpy arrays for all input and returned values. The following functions are available in version 1.1.

`(idx_a, idx_b, d) = k3match.cartesian(x_a, y_a, z_a, x_b, y_b, z_b, ds)`

Find all matches in Cartesian coordinates between two sets of points `(x_a, y_a, z_a)`

and `(x_b, y_b, z_b)`

within a given distance `ds`

. Ordering of the arrays is not important since binary tree will be built automatically for the longest array.

`(idx_a, idx_b, d) = k3match.spherical(theta_a, phi_a, theta_b, phi_b, ds)`

Find all matches on the unit sphere between two sets of points `(theta_a, phi_a)`

and `(theta_b, phi_b)`

within a given angular distance `ds`

. Ordering of the arrays is not important since binary tree will be built automatically for the longest array.

`(idx_a, idx_b, d) = k3match.celestial(ra_a, dec_a, ra_b, dec_b, ds)`

Find all matches on the celestial sphere between two sets of points `(ra_a, dec_a)`

and `(ra_b, dec_b)`

within a given angular distance `ds`

. Ordering of the arrays is not important since binary tree will be built automatically for the longest array.

`(idx, d) = k3match.nearest_cartesian(x_c, y_c, z_c, x_s, y_s, z_s)`

Find nearest neighbour in Cartesian coordinates between two sets of points `(x_c, y_c, z_c)`

and `(x_s, y_s, z_s)`

. Array `c`

is used for building the catalog and `idx`

refers to this array.