insert_recursive()

template<uint32_t K>

void scl::kd_tree< K >::insert_recursive ( Node *& node, std::shared_ptr< std::vector< item > > points, int depth )

inlineprivate

Recursive function to insert a point into the kd_tree.

Parameters

[in]	node	recursive node.
[in]	points	Inserted points in k d.
[in]	depth	recursive depth.

Calculate current dimension (cd).

Sort points in cd.

Get Center iterator.

Base case: If node is null, create a new node.

Split points to left and right.

Insert in left and right.

Definition at line 241 of file KDTree.h.

    {
        if (points->size() == 0) return;
 
        int cd = depth % K;
 
        std::multimap<float, uint32_t> sorted;
        if (points->size() <= 512)
        {
            for (int i = 0; i < points->size(); i++)
            {
                sorted.emplace((*points)[i][cd], i);
            }
        }
        else
        {
            for (int i = 0; i < 512; i++)
            {
                uint32_t index = static_cast<uint32_t>((points->size() - 1) * std::rand() / static_cast<float>(RAND_MAX));
                sorted.emplace((*points)[index][cd], index);
            }
        }
 
        auto centerit = sorted.begin();
        for (int i = 0; i < std::floor(sorted.size() * 0.5); i++) ++centerit;
 
        if (node == nullptr)
        {
            node = new Node((*points)[centerit->second]);
            ++m_Size;
        }
        else
        {
            SPICES_CORE_ERROR("Cannot insert a KDTree Node which is not empty.");
        }
 
        std::shared_ptr<std::vector<item>> leftPoints  = std::make_shared<std::vector<item>>();
        std::shared_ptr<std::vector<item>> rightPoints = std::make_shared<std::vector<item>>();
 
        for (int i = 0; i < points->size(); i++)
        {
            if (i == centerit->second) continue;
            else if ((*points)[i][cd] <= centerit->first)
            {
                leftPoints->push_back((*points)[i]);
            }
            else
            {
                rightPoints->push_back((*points)[i]);
            }
        }
 
        insert_recursive(node->m_Left,  leftPoints,  depth + 1);
        insert_recursive(node->m_Right, rightPoints, depth + 1);
    }