C++ 中的通用 KDTree

Question

我想要一个通用的 C++ KDTree 实现，它可以容纳任何类型的 positionable 对象。此类对象具有二维位置。

不幸的是。 Positionable 类可以有不同的方式获得位置。

Getters getX() 和 getY()
std::pair<双, 双>
sf::Vector2f
...

将这样的类包装到我的 KDTree 中的正确方法是什么？

我的树由以下节点组成：

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++;
    }
};

不知怎么的，我想要一个通用的 getter 到 T element 的位置。

一个可能的解决方案是定义一个可定位的接口：

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

此方法的缺点是可定位元素必须知道 KDTree 库

有哪些替代方案？

Answer 1

检查 boost geometry 的设计原理以解决此问题。该方法归结为以下步骤：

声明一个从类型中提取位置信息的class模板，例如
```
template <class Geometry>
struct Position;
```

要使您的 kd 树可用于新类型，例如 MyAwesome2dPoint，请为此模板专门化。在专业化中，您可以使用类型的方法获取位置：

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

在您的 kd 树中使用此类型系统，即不是直接访问位置，而是通过 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));
    }
}

为了加分，创建一个概念以避免在使用尚未配置为与您的库一起使用的类型时出现奇怪的编译错误：

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)
{
}

没有继承，没有虚拟，没有对现有类型的修改。只需创建一个可以专用于每个人（甚至是 C 类型）的层，你就可以开始了。当进一步抽象时，概念将挽救您的生命，例如提升几何体概括为 N 维度、不同的坐标系等。

C++ 中的通用 KDTree

Generic KDTree in C++

c++

oop