C++ Kd-Tree library
This is a standalone C++ version of the kd-tree implementation in the Gamera framework that has been extended by a range search and has been relicensed by the original author under a BSD style license. It is written in plain C++98 and does not depend on any third party libraries. The interface was first described in:
- C. Dalitz: Kd-Trees for Document Layout Analysis. In C. Dalitz (Ed.): "Document Image Analysis with the Gamera Framework." Schriftenreihe des Fachbereichs Elektrotechnik und Informatik, Hochschule Niederrhein, vol. 8, pp. 39-52, Shaker Verlag (2009)
About
A kd-tree is a data structure that allows for nearest neighbor queries in expected O(log(n)) time. The creation time of a kd-tree is O(n log(n)). This library offers four additional features not commonly found in kd-tree implementations:
- kNN search with optional additional search condition (search predicate)
- support for Euclidean, Manhatten, and Maximum distance and their weighted extensions (Euclidean is the default distance)
- range query
- nodes can store a pointer to arbitrary data as void*
Download
A copy of the source code of the library together with a demo program can be found on Github. Here is the latest file release:
- kdtree-1.3.tgz (version 1.3 from 2024/01/01)
Authors and license
The code is copyrighted by Christoph Dalitz and Jens Wilberg, Institute for Pattern Recognition, Niederrhein University of Applied Sciences, Krefeld, Germany. It can be freely used under the terms a two-clause BSD-style license. Please cite the Technical report listed at the top of this page as a reference when building upon this code.