Generic KDTree in C++

user_2612235 0
Viewed 241

I would like to have a generic KDTree implementation in C++ that can hold any kind of positionable object. Such objects have a 2D position.

Unfortunately. Positionable classes could have different ways of getting the position.

  • Getters getX() and getY()
  • std::pair<double, double>
  • sf::Vector2f
  • ...

What would be the proper way to wrap such classes into my KDTree?

My Tree is composed of nodes such as:

template <typename T>
struct Node {
    int id;
    T element;
    Node *left, *right;
    Node(T element) : element(element), left(NULL), right(NULL)
    {
        static int id = 0;
        this->id = id++;
    }
};

Somehow I would like to have a generic getter to the position of T element.

One possible solution is to define a positionable interface:

struct KDTreeElement {
    virtual getX() = 0;
    virtual getY() = 0;
}

The con of this method is that the positionable element must know the KDTree library

What are the alternatives?

oop c++
1 Answers

Check the design rationale of boost geometry for a solution to this problem. The methodology boils down to these steps:

  1. Declare a class template that extracts position information from a type, e.g.

    template <class Geometry>
struct Position;

  2. To make your kd Tree usable with a new type, say MyAwesome2dPoint, specialize this template for it. In the specialization you can use the type's method of getting the position:

    template <>
struct Position<MyAwesome2dPoint>
{
    static float getX(MyAwesome2dPoint const& p) { return p.x; }
    static float getY(MyAwesome2dPoint const& p) { return p.y; } 
}

  3. Use this type system in your kd tree, i.e. instead of directly accessing positions, go through the Position class:

    class KdTree 
{
    template <class PointType>
    auto contains(PointType const& g)
    {
        // Geometric properties are accessed through the traits system.
        return contains_impl(
            Position<PointType>::getX(g), 
            Position<PointType>::getY(g));
    }
}

  4. For extra credit, create a concept to avoid the weird compilation errors when using a type that hasn't been configured to work with your library:

    template <class G>
concept Positionable = requires (G g) { 
    Position<G>::getX() + Position<G>::getY(); 
}; 

// So now you can explicitly operate on such types
template <Positionable G>
auto contains(G const& g)
{
}

No inheritance, no virtuals, no modifications to existing types. Just create a layer that can be specialized for everyone (even C types) and you're good to go. Concepts will save your life when abstracting even further, e.g. boost geometry generalizes to N dimensions, different coordinate systems and more.

user_25676830
Related