KD-TREE package for searching for nearest neighbors in N points in in M-dimensions in N log(N) time.

kdtree-jk

# KDTREE-JK is a package for building efficent KD-Trees in Common Lisp

A KD-Tree is a data structure for searching N-dimensional space in
log(N) time by partitioning a data set iteratively across dimensions.

In KDTREE-JK, data are stored in block arrays instead of linked
structures, for minimal (usually zero) consing and allocation
overheads.  This is in contrast to a canonical KD-Tree implementation
that uses linked lists, which wastes memory on boxing.

Balancing is done in-place with Wirth's median partition method, so it
should be fast and memory efficient.  Insertion of one object and
searching is O(log(N)), and re-partitioning is O(N[log(N)]^2)

By default, all floats are double precision, but this can be
changed in kdtree-jk-structs.lisp in the line
````
  (deftype kd-float ()
    'double-float)
````

## Documentation

See `doc/reference.txt`

See doc/reference-latlon.txt for documentation to a second package,
    KDTREE-JK/LATLON, to search in longitude,latitude coordinates
    by converting to 3d points on a unit sphere.

kdtree-jk is written in pure Common Lisp, with no dependencies.

Submit bug reports at https://github.com/jetmonk/kdtree-jk/issues

Extension for KDTREE-JK to search in latitude and longitude by converting 2D latitude and longitude into 3D x,y,z.

kdtree-jk/latlon

Tests for KDTREE-JK comparing results to brute force search.

kdtree-jk

Upstream URL

Author

License

kdtree-jk

License:

Authors:

Dependencies:

kdtree-jk/latlon

License:

Authors:

Dependencies:

kdtree-jk/tests

License:

Authors:

Dependencies:

Dependencies (0)

Dependents (0)