kd_tree.hpp

Go to the documentation of this file.

/* Copyright (c) 2026 Otto Link. Distributed under the terms of the GNU General
   Public License. The full license is in the file LICENSE, distributed with
   this software. */
 
#pragma once
#include <cstddef>
#include <vector>
 
#include <glm/glm.hpp>
 
#include <nanoflann.hpp>
 
namespace hmap
{
 
struct NanoflannPointCloudAdaptor
{
  const std::vector<float> &x;
 
  const std::vector<float> &y;
 
  NanoflannPointCloudAdaptor(const std::vector<float> &x_,
                             const std::vector<float> &y_);
 
  inline size_t kdtree_get_point_count() const;
 
  inline float kdtree_get_pt(const size_t idx, int dim) const;
 
  template <class BBOX> bool kdtree_get_bbox(BBOX &) const
  {
    return false;
  }
};
 
using KDTree = nanoflann::KDTreeSingleIndexAdaptor<
    nanoflann::L2_Simple_Adaptor<float, NanoflannPointCloudAdaptor>,
    NanoflannPointCloudAdaptor,
    2>;
 
struct KDTreeContext
{
  const std::vector<float> &x;
 
  const std::vector<float> &y;
 
  NanoflannPointCloudAdaptor adaptor;
 
  KDTree index;
 
  KDTreeContext(const std::vector<float> &x_, const std::vector<float> &y_);
 
  glm::vec2 compte_neighbor_distance_range(size_t k_neighbors) const;
 
  void neighbor_search(float                x_query,
                       float                y_query,
                       size_t               k_neighbors,
                       std::vector<size_t> &indices,
                       std::vector<float>  &distances) const;
 
  std::vector<nanoflann::ResultItem<unsigned int, float>> radius_search(
      float x_query,
      float y_query,
      float radius) const;
};
 
} // namespace hmap