Блог

Я хотел бы иметь общую реализацию KDTree на C , которая может содержать любой вид позиционируемого объекта. Такие объекты имеют 2D-позицию.

К сожалению. У позиционных классов могут быть разные способы получения позиции.

• Методы получения 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  ;
    }
};
 

Каким-то образом я хотел бы иметь универсальный геттер в позиции T element .

Одним из возможных решений является определение позиционируемого интерфейса:

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

Недостатком этого метода является то, что позиционируемый элемент должен знать библиотеку KDTree

Каковы альтернативы?

Проверьте обоснование дизайна boost geometry для решения этой проблемы. Методология сводится к следующим шагам:

1. Объявите шаблон класса, который извлекает информацию о местоположении из типа, например

    template <class Geometry>
   struct Position;
    

2. Чтобы сделать ваше kd-дерево пригодным для использования с новым типом, скажем MyAwesome2dPoint , специализируйте этот шаблон для него. В специализации вы можете использовать метод типа для получения позиции:

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

3. Используйте эту систему типов в своем дереве kd, т.Е. Вместо прямого доступа к позициям, пройдите через Position класс:

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

4. Для дополнительной оценки создайте концепцию, чтобы избежать странных ошибок компиляции при использовании типа, который не был настроен для работы с вашей библиотекой:

    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 constamp; g)
   {
   }
    

Никакого наследования, никаких виртуалов, никаких модификаций существующих типов. Просто создайте слой, который может быть специализирован для всех (даже для типов C), и все готово. Концепции спасут вам жизнь при еще большем абстрагировании, например, геометрия boost обобщается на N размеры, различные системы координат и многое другое.