18477247352

Committed 13 Oct 2025 08:18PM UTC coverage: 72.391% (+0.4%) from 71.943%

Build # 18477247352

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #140 from paulmthompson/kdtree

Jules PR

Run Details

164 of 287 new or added lines in 3 files covered. (57.14%)

350 existing lines in 9 files now uncovered.

51889 of 71679 relevant lines covered (72.39%)

63071.54 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

83.33

/src/SpatialIndex/KdTree.hpp

#ifndef __kdtree_HPP
#define __kdtree_HPP

//
// Kd-Tree implementation.
//
// Copyright: Christoph Dalitz, 2018-2023
//            Jens Wilberg, 2018
// Version:   1.3
// License:   BSD style license
//            (see the file LICENSE for details)
//

#include <cstdlib>
#include <queue>
#include <vector>

#include "CoreGeometry/points.hpp"

namespace Kdtree {

template<typename T>
using CoordPoint = Point2D<T>;
typedef std::vector<double> WeightVector;

// for passing points to the constructor of kdtree
template<typename T>
struct KdNode {
  CoordPoint<T> point;
  void* data;
  int index;
  KdNode(const CoordPoint<T>& p, void* d = NULL, int i = -1) {
    point = p;
    data = d;
    index = i;
  }
  KdNode() { data = NULL; }
};
template<typename T>
using KdNodeVector = std::vector<KdNode<T>>;

// base function object for search predicate in knn search
// returns true when the given KdNode is an admissible neighbor
// To define an own search predicate, derive from this class
// and overwrite the call operator operator()
template<typename T>
struct KdNodePredicate {
  virtual ~KdNodePredicate() {}
  virtual bool operator()(const KdNode<T>&) const { return true; }
};

//--------------------------------------------------------
// private helper classes used internally by KdTree
//
// the internal node structure used by kdtree
template<typename T>
class kdtree_node;
// base class for different distance computations
template<typename T>
class DistanceMeasure;
// helper class for priority queue in k nearest neighbor search
class nn4heap {
 public:
  size_t dataindex;  // index of actual kdnode in *allnodes*
  double distance;   // distance of this neighbor from *point*
  nn4heap(size_t i, double d) {
    dataindex = i;
    distance = d;
  }
};
class compare_nn4heap {
 public:
  bool operator()(const nn4heap& n, const nn4heap& m) {
    return (n.distance < m.distance);
  }
};
  typedef std::priority_queue<nn4heap, std::vector<nn4heap>, compare_nn4heap> SearchQueue;
//--------------------------------------------------------

// kdtree class
template<typename T>
class KdTree {
 private:
  // recursive build of tree
  kdtree_node<T>* build_tree(size_t depth, size_t a, size_t b);
  // helper variable for keeping track of subtree bounding box
  CoordPoint<T> lobound, upbound;
  // helper variable to check the distance method
  int distance_type;
  bool neighbor_search(const CoordPoint<T>& point, kdtree_node<T>* node, size_t k, SearchQueue* neighborheap);
  void range_search(const CoordPoint<T>& point, kdtree_node<T>* node, double r, std::vector<size_t>* range_result);
  bool bounds_overlap_ball(const CoordPoint<T>& point, double dist,
                           kdtree_node<T>* node);
  bool ball_within_bounds(const CoordPoint<T>& point, double dist,
                          kdtree_node<T>* node);
  // class implementing the distance computation
  DistanceMeasure<T>* distance;
  // search predicate in knn searches
  KdNodePredicate<T>* searchpredicate;

 public:
  KdNodeVector<T> allnodes;
  size_t dimension;
  kdtree_node<T>* root;
  // distance_type can be 0 (max), 1 (city block), or 2 (euklid [squared])
  KdTree(const KdNodeVector<T>* nodes, int distance_type = 2);
  ~KdTree();
  void set_distance(int distance_type, const WeightVector* weights = NULL);
  void k_nearest_neighbors(const CoordPoint<T>& point, size_t k,
                           KdNodeVector<T>* result, KdNodePredicate<T>* pred = NULL);
  void range_nearest_neighbors(const CoordPoint<T>& point, double r,
                               KdNodeVector<T>* result);
};

}  // end namespace Kdtree

#endif

1	#ifndef __kdtree_HPP
2	#define __kdtree_HPP
3
4	//
5	// Kd-Tree implementation.
6	//
7	// Copyright: Christoph Dalitz, 2018-2023
8	// Jens Wilberg, 2018
9	// Version: 1.3
10	// License: BSD style license
11	// (see the file LICENSE for details)
12	//
13
14	#include <cstdlib>
15	#include <queue>
16	#include <vector>
17
18	#include "CoreGeometry/points.hpp"
19
20	namespace Kdtree {
21
22	template<typename T>
23	using CoordPoint = Point2D<T>;
24	typedef std::vector<double> WeightVector;
25
26	// for passing points to the constructor of kdtree
27	template<typename T>
28	struct KdNode {
29	CoordPoint<T> point;
30	void* data;
31	int index;
32	KdNode(const CoordPoint<T>& p, void* d = NULL, int i = -1) {	6✔
33	point = p;	6✔
34	data = d;	6✔
35	index = i;	6✔
36	}	6✔
37	KdNode() { data = NULL; }	1✔
38	};
39	template<typename T>
40	using KdNodeVector = std::vector<KdNode<T>>;
41
42	// base function object for search predicate in knn search
43	// returns true when the given KdNode is an admissible neighbor
44	// To define an own search predicate, derive from this class
45	// and overwrite the call operator operator()
46	template<typename T>
47	struct KdNodePredicate {
48	virtual ~KdNodePredicate() {}
49	virtual bool operator()(const KdNode<T>&) const { return true; }
50	};
51
52	//--------------------------------------------------------
53	// private helper classes used internally by KdTree
54	//
55	// the internal node structure used by kdtree
56	template<typename T>
57	class kdtree_node;
58	// base class for different distance computations
59	template<typename T>
60	class DistanceMeasure;
61	// helper class for priority queue in k nearest neighbor search
62	class nn4heap {
63	public:
64	size_t dataindex; // index of actual kdnode in allnodes
65	double distance; // distance of this neighbor from point
66	nn4heap(size_t i, double d) {	2✔
67	dataindex = i;	2✔
68	distance = d;	2✔
69	}	2✔
70	};
71	class compare_nn4heap {
72	public:
NEW 73	bool operator()(const nn4heap& n, const nn4heap& m) {	×
NEW 74	return (n.distance < m.distance);	×
75	}
76	};
77	typedef std::priority_queue<nn4heap, std::vector<nn4heap>, compare_nn4heap> SearchQueue;
78	//--------------------------------------------------------
79
80	// kdtree class
81	template<typename T>
82	class KdTree {
83	private:
84	// recursive build of tree
85	kdtree_node<T>* build_tree(size_t depth, size_t a, size_t b);
86	// helper variable for keeping track of subtree bounding box
87	CoordPoint<T> lobound, upbound;
88	// helper variable to check the distance method
89	int distance_type;
90	bool neighbor_search(const CoordPoint<T>& point, kdtree_node<T>* node, size_t k, SearchQueue* neighborheap);
91	void range_search(const CoordPoint<T>& point, kdtree_node<T>* node, double r, std::vector<size_t>* range_result);
92	bool bounds_overlap_ball(const CoordPoint<T>& point, double dist,
93	kdtree_node<T>* node);
94	bool ball_within_bounds(const CoordPoint<T>& point, double dist,
95	kdtree_node<T>* node);
96	// class implementing the distance computation
97	DistanceMeasure<T>* distance;
98	// search predicate in knn searches
99	KdNodePredicate<T>* searchpredicate;
100
101	public:
102	KdNodeVector<T> allnodes;
103	size_t dimension;
104	kdtree_node<T>* root;
105	// distance_type can be 0 (max), 1 (city block), or 2 (euklid [squared])
106	KdTree(const KdNodeVector<T>* nodes, int distance_type = 2);
107	~KdTree();
108	void set_distance(int distance_type, const WeightVector* weights = NULL);
109	void k_nearest_neighbors(const CoordPoint<T>& point, size_t k,
110	KdNodeVector<T>* result, KdNodePredicate<T>* pred = NULL);
111	void range_nearest_neighbors(const CoordPoint<T>& point, double r,
112	KdNodeVector<T>* result);
113	};
114
115	} // end namespace Kdtree
116
117	#endif

paulmthompson / WhiskerToolbox / 18477247352

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous