diff options
| -rw-r--r-- | CMakeLists.txt | 14 | ||||
| -rw-r--r-- | KDTree.h | 169 | ||||
| -rw-r--r-- | README.md | 20 | ||||
| -rw-r--r-- | kdtest.cpp | 64 |
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); +} |