KDTree WrapperHEADmain

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);
+}