Итеративная реализация дерева Kd ( C )

ProgramBox

Итеративная реализация дерева Kd ( C )

Post author:admin
Запись опубликована:18 апреля, 2023
Post category:Вопросы по программированию

#c #algorithm #data-structures #kdtree

#c #алгоритм #структуры данных #kdtree

Вопрос:

Здравствуйте, у кого-нибудь есть итеративная реализация Kd-дерева на C . Я пытался, но это не удается, когда количество узлов нечетно. Вот мой код на данный момент. Я имею в виду http://ldots.org/kdtree/#buildingAkDTree подробности на сайте.

 #include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <iomanip>


struct Point {
    double pt[2];
    int id;
};

typedef std::vector<Point> TPointVector;

struct KdNode {
    double point[2];
    int id;
    double desc;
    bool leaf;

    KdNode *left;
    KdNode *right;
    KdNode *parent;
    KdNode(KdNode *parent_):parent(parent_),leaf(false){}
    KdNode(KdNode *parent_,TPointVector::iterator itr, int depth, TPointVector amp;pv);
    KdNode(KdNode *t, TPointVector amp;pv);

};

KdNode::KdNode(KdNode *parent_,TPointVector::iterator itr, int depth, TPointVector amp;pv) {
    parent = parent_ ;
    left   = 0;
    right  = 0;
    desc   = itr->pt[depth % 2 ];
    leaf   = false;
}

KdNode::KdNode(KdNode *t, TPointVector amp;pv) {
    id       = pv[0].id;
    point[0] = pv[0].pt[0];
    point[1] = pv[0].pt[1];
    left     = 0;
    right    = 0;
    parent   = t;
    leaf     = true;
}

KdNode *pRoot = 0;


struct ComparePoints {
    int cord;
    ComparePoints(int  cord_) : cord(cord_ % 2) { };
    bool operator()(const Pointamp; lhs, const Pointamp; rhs) const {
        return lhs.pt[cord] < rhs.pt[cord];
    }
};
void buildLeftTree(std::stack<TPointVector > amp;stackL) {
    KdNode *pCurrent = pRoot;
    KdNode **pNode  = amp;(pCurrent->left);
    int depth      = 0; 
    bool changeDirection = false;
    while (! stackL.empty()) {
        TPointVector pv = stackL.top(); 
        stackL.pop();
        if ( pv.size() != 1 ) { 
            std::sort(pv.begin(), pv.end(), ComparePoints(  depth));

            *pNode = new KdNode(pCurrent, pv.begin()   pv.size()/2, depth, pv);

            TPointVector lvp,rvp;
            std::size_t median = pv.size() / 2;
            std::copy(pv.begin(), pv.begin()   median, std::back_inserter(lvp));
            std::copy(pv.begin()   median, pv.end(), std::back_inserter(rvp));

            stackL.push(rvp); 
            stackL.push(lvp);

            if ( changeDirection ) {
                pCurrent = pCurrent->right;
                changeDirection = false;
            } else {
                pCurrent = pCurrent->left;
            }           
            pNode = amp;(pCurrent->left);

        } else {
            KdNode **pNodeLeft   = amp;(pCurrent->left);
            *pNodeLeft  = new KdNode(pCurrent, pv);
            pv = stackL.top();
            stackL.pop();

            KdNode **pNodeRight   = amp;(pCurrent->right);
            *pNodeRight  = new KdNode(pCurrent,pv);

            pCurrent = pCurrent->parent;
            pNode  = amp;(pCurrent->right);
            changeDirection = true;
            depth--;
        }           
    }
}

void buildRightTree(std::stack<TPointVector > amp;stackR) {
    KdNode *pCurrent = pRoot;
    KdNode **pNode  = amp;(pCurrent->right);
    int depth      = 0; 
    bool changeDirection = true;
    while (! stackR.empty()) {
        TPointVector pv = stackR.top(); 
        stackR.pop();

        if ( pv.size() != 1 ) { 
            std::sort(pv.begin(), pv.end(), ComparePoints(  depth));
            *pNode = new KdNode(pCurrent, pv.begin()   pv.size()/2, depth, pv);

            TPointVector lvp,rvp;
            std::size_t median = pv.size() / 2;
            std::copy(pv.begin(), pv.begin()   median, std::back_inserter(lvp));
            std::copy(pv.begin()   median, pv.end(), std::back_inserter(rvp));

            stackR.push(rvp); 
            stackR.push(lvp);       

            if ( changeDirection ) {
                pCurrent = pCurrent->right;
                changeDirection = false;
            } else {
                pCurrent = pCurrent->left;
            }       
            pNode = amp;(pCurrent->left);

        } else {
            KdNode **pNodeLeft   = amp;(pCurrent->left);
            *pNodeLeft  = new KdNode(pCurrent, pv);
            pv = stackR.top();
            stackR.pop();

            KdNode **pNodeRight   = amp;(pCurrent->right);
            *pNodeRight  = new KdNode(pCurrent,pv);

            pCurrent = pCurrent->parent;
            pNode  = amp;(pCurrent->right);
            depth--;
            changeDirection = true;
        }           
    }
}


void constructKD(TPointVector amp;pv) {
    int depth = 0;
    std::sort(pv.begin(), pv.end(), ComparePoints(depth));

    pRoot        = new KdNode(0);
    pRoot->desc  = ( pv.begin()   pv.size()/2)->pt[0];
    pRoot->left  = 0;
    pRoot->right = 0;

    TPointVector lvp, rvp;
    std::copy(pv.begin(), pv.begin()   pv.size()/2, std::back_inserter(lvp));
    std::copy(pv.begin()   pv.size()/2, pv.end(), std::back_inserter(rvp));

    std::stack<TPointVector > stackL, stackR;
    stackL.push(lvp);
    stackR.push(rvp);

    buildLeftTree(stackL);
    buildRightTree(stackR);

}
void readPoints(const char* fileName, TPointVectoramp; points) {
    std::ifstream input(fileName);

    if ( input.peek() != EOF ) {
        while(!input.eof()) {
            int id = 0;
            double x_cord, y_cord;
            input >> id >> x_cord >> y_cord;

            Point t ;
            t.pt[0] = x_cord;
            t.pt[1] = y_cord;
            t.id    = id;

            points.push_back(t);
        }
        input.close();
    }   
}
void _printLevelWise(KdNode *node, std::queue<KdNode *> Q) {
    int depth = 0;
    while ( ! Q.empty()) {
        KdNode *qNode = Q.front();Q.pop();
        if ( qNode->leaf ) {
            std::cout << "[" << qNode->id << "]" << std::setprecision (25) << "(" << qNode->point[0] << "," << qNode->point[1] << ")" << std::endl;
        } else {
            std::cout << std::setprecision (25) << qNode->desc << std::endl;
        }       
        if (qNode->left != 0)
            Q.push(qNode->left);
        if (qNode->right != 0)
            Q.push(qNode->right);
    }
}
void PrintLevelWise(KdNode *node) {
    std::queue<KdNode *> Q;
    Q.push(node);
    _printLevelWise(node, Q);
}
int main ( int argc, char **argv ) {
    if ( argc <= 1 ) {
        return 0;
    }
    TPointVector points;
    readPoints(argv[1], points);
    for ( TPointVector::iterator itr = points.begin(); itr != points.end();   itr) {
        std::cout << "(" << itr->pt[0] << "," << itr->pt[1] << ")" << std::endl;
    }
    if ( points.size() == 0 )
        return 0;
    constructKD(points);
    PrintLevelWise(pRoot);
    std::cout << "Construction of KD Tree Done " << std::endl;
}

Пример ввода, для которого это не удается :

Пример ввода, для которого это работает :

1. Как это «сбой», когда оно нечетное? Ошибка Seg?

2. Обновите вопрос, извините, что не указал деталей.

3. Для заинтересованных сторон «сбой» — это пропуск одного из прочитанных узлов, т. Е. в дереве оказывается только N-1 узел для N записей (когда N нечетно).

Ответ №1:

Ваш else in buildLeftTree и buildRightTree не обрабатывает случай, когда в правом поддереве нечетное число узлов. В вашем примере из 5 пунктов else случай в buildRightTree заканчивается тремя точками на stackR , первая используется для left узла, две вторые он молча присваивает right узлу, как если бы это был единственный узел.

Это связано с вашим выбором медианы, который использует критерии, отличные от тех, которые указаны на сайте, на который вы ссылаетесь.

 std::size_t median = pv.size() / 2; // degenerates in cases where size() is odd

Предполагается, что ваши критерии выбора основаны на медианном значении x или y и используют подсписки на основе этих критериев (которые не предполагают какого-либо заданного размера).

1. Я внесу это изменение и проведу повторное тестирование, но у меня есть другой вопрос, почему не доступна итеративная реализация KD-дерева. Доступна ли простая версия реализации KD-дерева (рекурсивная может подойти)

Ответ №2:

В else из buildLeftTree и buildRightTree .

Добавить

 if (pv.size() > 1)
{
    pNode = amp;(pCurrent->right);
    continue;
}

между top и pop функцией стека. Все будет в порядке.

У меня есть еще один вопрос, когда количество точек равно миллиону, построение дерева будет очень медленным, как улучшить производительность?