insert_recursive_async()

template<uint32_t K>

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

inlineprivate

Recursive function to insert a point into the kd_tree async.

Parameters

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

Return if there is no point needs to insert.

Calculate current dimension (cd).

Sort points in cd.

Get Center iterator.

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

Insert in left.

Insert in right.

Definition at line 320 of file KDTree.h.

    {
        constexpr int nPointsWithoutSplitTask = 30000;
 
        if (points->size() <= nPointsWithoutSplitTask)
        {
            const auto in = std::chrono::high_resolution_clock::now();
            insert_recursive(node, points, depth);
            const auto out = std::chrono::high_resolution_clock::now();
            std::cout << "    Cost: " << std::chrono::duration_cast<std::chrono::milliseconds>(out - in).count() << "    " << points->size() << std::endl;
            return;
        }
 
        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() / 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.");
        }
 
        threadPool->SubmitPoolTask([this, cd, points, node, threadPool, depth](float centerVal, uint32_t centerIndex) {
            std::shared_ptr<std::vector<item>> leftPoints = std::make_shared<std::vector<item>>();
            for (int i = 0; i < points->size(); i++)
            {
                if (i == centerIndex) continue;
                else if ((*points)[i][cd] <= centerVal)
                {
                    leftPoints->push_back((*points)[i]);
                }
            }
            insert_recursive_async(node->m_Left, leftPoints, threadPool, depth + 1);
        }, centerit->first, centerit->second);
        
        threadPool->SubmitPoolTask([this, cd, points, node, threadPool, depth](float centerVal, uint32_t centerIndex) {
            std::shared_ptr<std::vector<item>> rightPoints = std::make_shared<std::vector<item>>();
            for (int i = 0; i < points->size(); i++)
            {
                if (i == centerIndex) continue;
                else if ((*points)[i][cd] > centerVal)
                {
                    rightPoints->push_back((*points)[i]);
                }
            }
            insert_recursive_async(node->m_Right, rightPoints, threadPool, depth + 1);
        }, centerit->first, centerit->second);
    }