A library for lazy tree structures.
Trees are usually used for fast searches, like for example the search of the nearest neighbour.
Building such a tree structure can be expensive. Depending on the number of searches, it might be more efficient to not build the structure at all.
It’s also possible that searches might only occur in a certain sub-area of the tree. Other areas would not have to be built in that case.
LazyTrees are only built / evaluated as little as possible. If no searches occur, or never use the entire search space, a lot of time can be saved. They also have basically no initial build time, which can result in a more responsive program.
The trees can be built with any point type which implementes the following functions:
static size_t dimensions(); //returning the number of dimensions (2D Point => return 2)
const double& operator[](size_t) const; //overloading the random access operator. [0] => x-coordinate, [1] => y-coordinate ... [dimensions() - 1]Usage example
class Point2D
{
public:
double x, y;
Point2D() :
x(0),
y(0)
{}
Point2D(double x, double y) :
x(x),
y(y)
{}
bool operator ==(const Point2D &b) const
{
return x == b.x && y == b.y;
}
static size_t dimensions()
{
return 2;
}
const double& operator[](size_t idx) const
{
if(idx == 0) return x;
else if(idx == 1) return y;
else throw std::out_of_range ("Point2D can only be accessed with index 0 or 1");
}
};
...
auto pts = std::vector<Point2D>{
Point2D(0.0, 1.0),
Point2D(0.0, 2.0),
Point2D(0.0, 3.0),
Point2D(0.0, 4.0),
Point2D(0.0, 5.0),
Point2D(15.0, 6.0),
Point2D(0.0, 7.0),
};
LazyKdTree<Point2D> tree(std::move(pts));
REQUIRE(tree.nearest(Point2D(0.3, 0.7)) == Point2D(0.0, 1.0));
REQUIRE(tree.nearest(Point2D(-100.0, -100.0)) == Point2D(0.0, 1.0));