aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--CMakeLists.txt14
-rw-r--r--KDTree.h169
-rw-r--r--README.md20
-rw-r--r--kdtest.cpp64
4 files changed, 267 insertions, 0 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt
new file mode 100644
index 0000000..357a254
--- /dev/null
+++ b/CMakeLists.txt
@@ -0,0 +1,14 @@
+cmake_minimum_required(VERSION 3.1)
+project(kdlookup)
+
+# -Wall -O2 -march=native
+set(CMAKE_CXX_FLAGS "-std=c++17 -g")
+
+add_executable( main main.cpp )
+
+list( APPEND CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake_modules )
+
+add_library( kdtree SHARED IMPORTED )
+set_target_properties( kdtree PROPERTIES IMPORTED_LOCATION /usr/local/lib/libkdtree.so )
+
+TARGET_LINK_LIBRARIES(main kdtree) \ No newline at end of file
diff --git a/KDTree.h b/KDTree.h
new file mode 100644
index 0000000..d2488e7
--- /dev/null
+++ b/KDTree.h
@@ -0,0 +1,169 @@
+/*
+ A simple C++ wrapper for John Tsiombikas's kd-tree library.
+
+ KDTree<PointT, LabelT, Dims> kdtree;
+ PointT:
+ - must contain a constructor to recieve points via a double buffer [double*]
+ - must have a .data() method that produces a double buffer
+
+ LabelT:
+ - modifiable
+
+ Dims:
+ - Number of dimensions in PointT
+
+ Search methods return ResultSet similar to an iterator with more contraints
+*/
+
+#pragma once
+
+#include <memory>
+
+namespace ldrs {
+
+ #include <kdtree.h>
+
+ template <typename _PointT, typename _LabelT, int _Dims>
+ class KDTree {
+
+ public:
+
+ struct Pair {
+ _PointT point;
+ _LabelT label;
+
+ typedef std::shared_ptr<Pair> Ptr;
+ typedef std::shared_ptr<Pair const> ConstPtr;
+ };
+
+ private:
+
+ struct kdtree * _tree;
+ size_t _size;
+
+ static void _delete_node_callback(void * node) {
+ delete reinterpret_cast<_LabelT*>(node);
+ }
+
+ static Pair toPair(struct kdres const * res) {
+ double pos[_Dims];
+ void * data = kd_res_item(const_cast<struct kdres *>(res), pos);
+
+ Pair pl {
+ _PointT(reinterpret_cast<double *>(pos)),
+ *reinterpret_cast<_LabelT *>(data)
+ };
+
+ return pl;
+ }
+
+ public:
+
+ typedef std::shared_ptr<KDTree> Ptr;
+ typedef std::shared_ptr<KDTree const> ConstPtr;
+
+ class ResultSet {
+ struct kdres * _res;
+ public:
+ ResultSet(struct kdres * res)
+ : _res(res)
+ {}
+
+ ~ResultSet() {
+ if(_res)
+ kd_res_free(_res);
+ }
+
+ inline bool next() { return kd_res_next(_res) != 0; }
+
+ inline bool end() const { return kd_res_end(_res) != 0; }
+
+ inline void rewind() { kd_res_rewind(_res); }
+
+ inline int size() const { return kd_res_size(_res); }
+
+ ResultSet(const ResultSet &) = delete;
+ ResultSet& operator=(const ResultSet &) = delete;
+ ResultSet(ResultSet && rs) {
+ _res = rs._res;
+ rs._res = nullptr;
+ }
+
+ ResultSet& operator=(ResultSet && rs) {
+ _res = rs._res;
+ rs._res = nullptr;
+ return *this;
+ }
+
+ ResultSet& operator++() {
+ next();
+ return *this;
+ }
+
+ _PointT point() const {
+ double pos[_Dims];
+ kd_res_item(_res, pos);
+ return _PointT(pos);
+ }
+
+ _LabelT& label() const {
+ return *reinterpret_cast<_LabelT*>(kd_res_item_data(_res));
+ }
+
+ Pair pair() const {
+ return KDTree::toPair(_res);
+ }
+ };
+
+ KDTree()
+ : _tree(kd_create(_Dims))
+ , _size(0)
+ {
+ kd_data_destructor(_tree, &_delete_node_callback);
+ }
+
+ ~KDTree() {
+ kd_free(_tree);
+ }
+
+ size_t size() const {
+ return _size;
+ }
+
+ void clear() {
+ _size = 0;
+ kd_clear(_tree);
+ }
+
+ int insert(_PointT const & pt, _LabelT const & label) {
+ _size++;
+
+ return kd_insert(
+ _tree,
+ pt.data(),
+ reinterpret_cast<void *>(new _LabelT(label))
+ );
+ }
+
+ ResultSet nearestRange(_PointT const & pt, double range) const {
+ kdres * res = kd_nearest_range(_tree, pt.data(), range);
+ return ResultSet(res);
+ }
+
+ ResultSet nearestPoint(_PointT const & pt) const {
+ kdres * res = kd_nearest(_tree, pt.data());
+ return ResultSet(res);
+ }
+
+ Pair nearestExistentPoint(_PointT const & pt) const {
+ kdres * res = kd_nearest(_tree, pt.data());
+
+ Pair pl = KDTree::toPair(res);
+
+ kd_res_free(res);
+
+ return pl;
+ }
+
+ };
+}; \ No newline at end of file
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..0536e80
--- /dev/null
+++ b/README.md
@@ -0,0 +1,20 @@
+KDTree Wrapper
+==============
+
+A simple C++ wrapper for John Tsiombikas's kd-tree library.
+
+```
+KDTree<PointT, LabelT, Dims> kdtree;
+```
+
+PointT:
+- must contain a constructor to recieve points via a double buffer [double*]
+- must have a .data() method that produces a double buffer
+
+LabelT:
+- modifiable
+
+Dims:
+- Number of dimensions in PointT
+
+Search methods return `ResultSet` which acts similar to an iterator with more contraints \ No newline at end of file
diff --git a/kdtest.cpp b/kdtest.cpp
new file mode 100644
index 0000000..147b16c
--- /dev/null
+++ b/kdtest.cpp
@@ -0,0 +1,64 @@
+/*
+ Test of the KDTree library
+ https://github.com/jtsiomb/kdtree
+*/
+
+#include <kdtree.h>
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <math.h>
+
+struct xyl_point {
+ double x;
+ double y;
+ uint32_t label;
+};
+
+int kd_insert_xyl(struct kdtree *tree, struct xyl_point const * pt) {
+ return kd_insert(tree, (double *) pt, (void *) (&pt->label));
+}
+
+double l2_norm(struct xyl_point * const x1, struct xyl_point * const x2) {
+ return sqrt(
+ (x1->x - x2->x) * (x1->x - x2->x) +
+ (x1->y - x2->y) * (x1->y - x2->y)
+ );
+}
+
+int main() {
+ struct xyl_point points[5] = {
+ {0, 0, 0},
+ {0, 1, 1},
+ {1, 0, 2},
+ {1, 1, 3}
+ };
+
+ struct kdtree *ptree = kd_create(2);
+
+ for(size_t i = 0; i < sizeof(points); i++) {
+ assert(0 == kd_insert_xyl(ptree, points + i));
+ }
+
+ {
+ struct xyl_point target = {0.75, 0.80, 0};
+ struct xyl_point found;
+ double dist;
+ struct kdres * presults = kd_nearest(ptree, (double*) &target);
+
+ while(!kd_res_end(presults)) {
+ found.label = *(uint32_t*) kd_res_item(presults, (double *) &found);
+
+ dist = l2_norm(&found, &target);
+
+ printf("found [(%.3f, %.3f), %u] a distance of %.3f\n", found.x, found.y, found.label, dist);
+
+ kd_res_next(presults);
+ }
+
+ kd_res_free( presults );
+ }
+
+ kd_free(ptree);
+}