关于root_alpha函数的描述原文为:
Description: Return the balance criterion value and balance criterion value of the ikd-Tree.
我参考代码来看应该是
balance criterion value 和 delete criterion value

嗨，
我在测试最新版本ikdtree的时候遇到一个问题，当我在类中定义ikdtree的时候，程序总是Segmentation fault (core dumped)。你能修复一下这个问题吗？
谢谢！

can this kd-tree use 2d point as point type?

Hi,

under what license is this code distributed and can you add the license to the repository?

Thanks,

I did some tests and read the code. It seems that ikd-tree does not collect those points deleted in the downsample process. Can I get the missing points from "Downsample_Storage" ?

(I really need those points, because I need to do object tracking with them.)

PCL kdtree provides index to mark origin map points and all points are managered out of kdtree,
but ikd-tree does not have index.

Now I define an embedded index uint32_t value in "PointType" to solve this problem, but it's not perfect because it's growing and will overflow soon.

I run ikd-tree with a running sliding window of point cloud. pointclouds are queued in time_stamp sequential. each point are added to ikdtree and then delete later. But as I was checking kdtree points with these code:
if(0)
//If you need to see map point, change to "if(1)"
{
PointVector ().swap(ikdtree.PCL_Storage);
ikdtree.flatten(ikdtree.Root_Node, ikdtree.PCL_Storage, NOT_RECORD);
featsFromMap->clear();
featsFromMap->points = ikdtree.PCL_Storage;
}
then publish these point clouds.
I found there are always points not deleted, i.e. they remain in the kdtree even though deleted.

Another question, what if i add_Points with downsample_flag=True. Then delete original point later. Will ikdtree delete this cuboid? what behavior will ikdtree generate?

就是一般维护一个局部map，需要先降采样再构成，比如用pcl voxelgrid来进行体素降采样。ikdtree是否在构建的过程已经完成了降采样，在添加点云时没必要进行额外的降采样操作？期待回答，谢谢！

Hi,
Nice work!
I found you didn't initialize the variable of "Rebuild_Ptr" in your code. When I run your demo, everything seems ok, but when
I use your code into my own project with ROS it always leads to problem crash, I solved this problem after I set the initial value of "Rebuild_Ptr" to nullptr. I can't sure is this a bug or I just somehow make my program right. So Can you help me to see if this problem will cause the program to crash?
Best wish.

When I build the codes with cmake (build type release), a segmentation fault occured, which will disappear when the "release" flag is removed. I tried to locate the codes where the segmentation fault occured but failed. Here is the only modification of the codes:

void KD_TREE::stop_thread(){

    pthread_mutex_lock(&termination_flag_mutex_lock);
    termination_flag = true;
    pthread_mutex_unlock(&termination_flag_mutex_lock);
    printf("0\n");
    if (rebuild_thread) pthread_join(rebuild_thread, NULL);
    printf("1\n");
    pthread_mutex_destroy(&termination_flag_mutex_lock);
    pthread_mutex_destroy(&rebuild_logger_mutex_lock);
    pthread_mutex_destroy(&rebuild_ptr_mutex_lock);
    pthread_mutex_destroy(&points_deleted_rebuild_mutex_lock);
    pthread_mutex_destroy(&working_flag_mutex);
    pthread_mutex_destroy(&search_flag_mutex);     
}

And my CMakeLists.txt:

cmake_minimum_required(VERSION 3.0.2)
project(ikdtree)

add_compile_options(-std=c++17)
set(CMAKE_BUILD_TYPE "Release") // if I remove this line, the segmentation fault will disappear

include_directories(
  include
)

add_executable(ikdtree_demo
  src/ikd_Tree_demo.cpp
  src/ikd_Tree.cpp
)
target_link_libraries(ikdtree_demo pthread)

The output is as follows:

Multi thread started 
0
Rebuild thread terminated normally
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
[1]    150531 segmentation fault (core dumped)

It seems that the segmentation fault occured in pthread_join(), which makes me confused. Could you please help me to solve the problem?

你好呀，十分感谢分享工作！
关于ikdtree 点云插入效率的问题我有个疑问，希望能得到解答：
我在测试的时候发现，在插入点不多的情况下（如300个点）的确效率还可以，时间在2-3ms内；但是当如果插入的是一个瓦片地图（如30000个点）的话，我发现插入效率还不如pcl中的kdtree，我是否可以认为ikdtree目前的版本是比较适合高频少点的插入方式，而不是低频多点的插入方式呢？

Right now the header file is "using namespace std". This is considered bad practice, but easy to fix.

Additionally <unistd.h> is used to put the current thread to sleep.
This is not platform independent and can easily be replaced by C++ std library functionality.

Hello, Thanks for your excellent work!
In my test, when search point is around (0,0,0), k_nearest = 5 , the return nearest_points are all (0,0,0). I think it is a bug, so just report and wish you can give some hints to fix as I don't familiar with the code.

你好，非常感谢分享工作！
我有一些疑问，还请解惑：
1.一般在里程计的scan2map过程，是需要找到当前帧附近邻域内(比如50米)的历史的关键帧，也就是目前代码中的localmap(我认为)，如果里程计一直是单向在跑，我认为ikd-tree一直增量的更新这个树，确实没问题，但是一旦调头了，那ikd-tree不是已经把历史的一些点给删除了吗，所以这里会不会存在问题呢？换句话说就是ikd-tree能否保留历史关键帧上的点呢？
2.在测试的时候我发现ikd-tree的size()一直在增大，是不是我忽略了什么细节？
3.对这个ikdtree非常感兴趣，可否加个微信什么的方便私底下询问，我的是16621710962。万分感谢了

should be
if(q.size()< k_nearest || (dist_left_node < q.top().dist && dist_right_node < q.top().dist))

            if (int(Rebuild_PCL_Storage.size()) > 0){
                BuildTree(&new_root_node, 0, Rebuild_PCL_Storage.size()-1, Rebuild_PCL_Storage);
                // Rebuild has been done. Updates the blocked operations into the new tree
                pthread_mutex_lock(&working_flag_mutex);
                pthread_mutex_lock(&rebuild_logger_mutex_lock);
                int tmp_counter = 0;
                while (!Rebuild_Logger.empty()){
                    Operation = Rebuild_Logger.front();
                    max_queue_size = max(max_queue_size, Rebuild_Logger.size());
                    Rebuild_Logger.pop();
                    pthread_mutex_unlock(&rebuild_logger_mutex_lock);                  
                    pthread_mutex_unlock(&working_flag_mutex);
                    run_operation(&new_root_node, Operation);
                    tmp_counter ++;
                    if (tmp_counter % 10 == 0) usleep(1);
                    pthread_mutex_lock(&working_flag_mutex);
                    pthread_mutex_lock(&rebuild_logger_mutex_lock);               
                } 
                rebuild_flag = false;  // rebuild flag should in here
               pthread_mutex_unlock(&rebuild_logger_mutex_lock);
            }

after fix this issue, this check not need

            if (!Rebuild_Logger.empty()){
                printf("\n\n\n\n\n\n\n\n\n\n\n ERROR!!! \n\n\n\n\n\n\n\n\n");
            }

hi
Thanks for sharing your work, it is a great improvement that make kdtree cost less time when add new points, however, if I want to delete some points, can this framework handle without build a new kdtree?

Doesn't seem to work with PointType = pcl::PointXYZL.

Thanks for your work, it's elegant and useful.

I would like to use nearest search in a openmp section, eg:

`
#pragma omp parallel for num_threads(4)
for (int i = 0; i < laserCloudSurfLastDSNum; i++)
{
PointType pointOri, pointSel, coeff;
std::vector pointSearchInd;
std::vector pointSearchSqDis;

pointOri = laserCloudSurfLastDS->points[i];
pointAssociateToMap(&pointOri, &pointSel); 
kdtreeSurfFromMap->nearestKSearch(pointSel, 5, pointSearchInd, pointSearchSqDis); //replaced by ikd-tree

}
`
Is it possible to do multiple search at the same time ? It seems that a mutex is used within the Nearest_Search(), which means that parallel operations actually save no time. Am i right ?

I had an issue where KD_TREE::InitTreeNode() didn't get valid mutex from pthread_mutex_init() because it ran out of handles (it returned nullptr and crashed later when accessing nullptr mutex pointer). Then I noticed that push_down_mutex_lock is never destroyed when KD_TREE_NODE is deleted.

I added pthread_mutex_destroy( &(*root)->push_down_mutex_lock ); to KD_TREE::delete_tree_nodes() and the problem went away. So currently it leaks mutex handles which you may ran out of if you create/delete lot of nodes.

你好，想请问下，如果一个ikd-tree已经建立好，有没有一种快速的方法可以实现把里面所有的点都减去一个相同的xyz坐标，理论上做完这个操作，树原本的结果不会改变

Hi! I have seen the paper, the ikd-tree is very novel and practical. But I see the data type of node is pcl::PointXYZ (demo file also). Now I want to change the data type from pcl::PointXYZ to my own struct type, In this struct, not only incorporate position, but also have static pointer, Can I use this type to build a ikd-tree?

I am doing some rewrite of this ikdtree to adapt my situation.
And I find you used nth_element while building a tree. According to my experiments there might be a bug.

Suppose at some point division-axis is 0, which is x-axis, let's use 1-D data to explain:

Suppose we have a vector [0,1,2,2,2,2,2,2,3,4] which is points' x-axis value after nth_element() function call, y-axis value is totally different, say [0,1,2,3,4,5,6,7,8,9]。nth_element（） divide these points into different group but not determinately which point is on left or right node. point (2,2) might be on the left or right.

Thus while searching, or delete or add by point. it not guaranteed to find this point.

when I use 'make -j 9',the error is found ,"undefined references to `pthread_mutex_trylock'" follow ,I use pcl-1.10.

Thanks for releasing great works.

"ikd_Tree.cpp", 886 line.
if (dist <= max_dist && (q.size() < k_nearest || dist < q.top().dist))
is it right?

or
if (dist <= max_dist*max_dist && (q.size() < k_nearest || dist < q.top().dist))

Stack trace (most recent call last):
#21 Object "/usr/lib/x86_64-linux-gnu/ld-2.31.so", at 0xffffffffffffffff, in
#20 Object "/home/jcwang/code/ws_di-lui-sam/src/di_lui_sam/cmake-build-debug/devel/lib/multi_proxy/multi_proxy_subMapFusion", at 0x555555600ead, in start
#19 Source "../csu/libc-start.c", line 308, in libc_start_main [0x7ffff45e6082]
#18 Source "/home/jcwang/code/ws_di-lui-sam/src/di_lui_sam/src/subMapFusion.cpp", line 2235, in main [0x555555601305]
2232: std::thread OptThread(&SubMapFusion::globalOptimizationThread, &SubMapF);
2233: std::thread pubLoopThread(&SubMapFusion::publishSCWithCloudThread, &SubMapF);
2234:
>2235: ros::spin();
2236:
2237: pubDesOtherThread.join();
2238: pubMapThread.join();
#17 Object "/opt/ros/noetic/lib/libroscpp.so", at 0x7ffff7f2a21e, in ros::spin()
#16 Object "/opt/ros/noetic/lib/libroscpp.so", at 0x7ffff7f41fce, in ros::SingleThreadedSpinner::spin(ros::CallbackQueue*)
#15 Object "/opt/ros/noetic/lib/libroscpp.so", at 0x7ffff7eee882, in ros::CallbackQueue::callAvailable(ros::WallDuration)
#14 Object "/opt/ros/noetic/lib/libroscpp.so", at 0x7ffff7eed171, in ros::CallbackQueue::callOneCB(ros::CallbackQueue::TLS*)
#13 Object "/opt/ros/noetic/lib/libroscpp.so", at 0x7ffff7f3f138, in ros::SubscriptionQueue::call()
#12 Source "/opt/ros/noetic/include/ros/subscription_callback_helper.h", line 144, in call [0x5555556fe2ca]
141: virtual void call(SubscriptionCallbackHelperCallParams& params)
142: {
143: Event event(params.event, create);
> 144: callback(ParameterAdapter

::getParameter(event));
145: }
146:
147: virtual const std::type_info& getTypeInfo()
#11 Source "/usr/include/boost/function/function_template.hpp", line 763, in operator() [0x555555702548]
760: if (this->empty())
761: boost::throw_exception(bad_function_call());
762:
> 763: return get_vtable()->invoker
764: (this->functor BOOST_FUNCTION_COMMA BOOST_FUNCTION_ARGS);
765: }
#10 Source "/usr/include/boost/function/function_template.hpp", line 158, in invoke [0x5555556b57eb]
155: f = reinterpret_cast<FunctionObj*>(function_obj_ptr.data);
156: else
157: f = reinterpret_cast<FunctionObj*>(function_obj_ptr.members.obj_ptr);
> 158: BOOST_FUNCTION_RETURN((f)(BOOST_FUNCTION_ARGS));
159: }
160: };
#9 Source "/usr/include/boost/function/function_template.hpp", line 763, in operator() [0x5555556c1db5]
760: if (this->empty())
761: boost::throw_exception(bad_function_call());
762:
> 763: return get_vtable()->invoker
764: (this->functor BOOST_FUNCTION_COMMA BOOST_FUNCTION_ARGS);
765: }
#8 Source "/usr/include/boost/function/function_template.hpp", line 158, in invoke [0x555555696649]
155: f = reinterpret_cast<FunctionObj>(function_obj_ptr.data);
156: else
157: f = reinterpret_cast<FunctionObj*>(function_obj_ptr.members.obj_ptr);
> 158: BOOST_FUNCTION_RETURN((*f)(BOOST_FUNCTION_ARGS));
159: }
160: };
#7 Source "/usr/include/boost/bind/bind.hpp", line 1306, in operator()<const boost::shared_ptr<const sensor_msgs::PointCloud2<std::allocator > >&> [0x5555556a70ac]
1303: template result_type operator()( A1 && a1 )
1304: {
1305: rrlist1< A1 > a( a1 );
>1306: return l_( type<result_type>(), f_, a, 0 );
1307: }
1308:
1309: template result_type operator()( A1 && a1 ) const
#6 Source "/usr/include/boost/bind/bind.hpp", line 319, in operator()<boost::mfi::mf1<void, SubMapFusion, const boost::shared_ptr<const sensor_msgs::PointCloud2<std::allocator > >&>, boost::bi::rrlist1<const boost::shared_ptr<const sensor_msgs::PointCloud2<std::allocator > >&> > [0x5555556b5515]
317: template<class F, class A> void operator()(type, F & f, A & a, int)
318: {
> 319: unwrapper::unwrap(f, 0)(a[base_type::a1_], a[base_type::a2_]);
320: }
321:
322: template<class F, class A> void operator()(type, F const & f, A & a, int) const
#5 Source "/usr/include/boost/bind/mem_fn_template.hpp", line 165, in operator() [0x5555556c1a47]
163: R operator()(T * p, A1 a1) const
164: {
> 165: BOOST_MEM_FN_RETURN (p->f_)(a1);
166: }
167:
168: template R operator()(U & u, A1 a1) const
#4 Source "/home/jcwang/code/ws_di-lui-sam/src/di_lui_sam/src/subMapFusion.cpp", line 681, in laserCloudInfoHandler [0x55555561e8f4]
679: isKeyframe(context_info);
680: buildFrameList(context_info);
> 681: buildSubmap(context_info);
682: }
683: // std::cout << "laser: finished! " << std::endl;
684: }
#3 Source "/home/jcwang/code/ws_di-lui-sam/src/di_lui_sam/src/subMapFusion.cpp", line 1109, in buildSubmap [0x555555623a08]
1106: _downsize_filtermap.setInputCloud(cloud_in_ego_odom);
1107: _downsize_filtermap.filter(_cloud_temp);
1108:
>1109: buildiKDTree(_cloud_temp);//////TODO：这里有问题，会重复释放内存
1110: mtx_map.lock();
1111: *_lidarmap_current += *_cloud_temp;
1112: _cloud_temp->clear();
#2 Source "/home/jcwang/code/ws_di-lui-sam/src/di_lui_sam/src/subMapFusion.cpp", line 1164, in buildiKDTree [0x555555624060]
1161: }
1162:
1163: double st_time = omp_get_wtime();
>1164: ikdtree.Add_Points(PointToAdd, true);
1165: double kdtree_incremental_time = omp_get_wtime() - st_time;
1166: }
#1 Source "/home/jcwang/code/ws_di-lui-sam/src/di_lui_sam/third_parties/ikd-Tree/ikd_Tree.cpp", line 501, in Add_Points [0x7ffff72eff4d]
498: mid_point.y = Box_of_Point.vertex_min[1] + (Box_of_Point.vertex_max[1] - Box_of_Point.vertex_min[1]) / 2.0;
499: mid_point.z = Box_of_Point.vertex_min[2] + (Box_of_Point.vertex_max[2] - Box_of_Point.vertex_min[2]) / 2.0;
500: PointVector().swap(Downsample_Storage);
> 501: Search_by_range(Root_Node, Box_of_Point, Downsample_Storage);
502: min_dist = calc_dist(PointToAdd[i], mid_point);
503: downsample_result = PointToAdd[i];
504: for (int index = 0; index < Downsample_Storage.size(); index++)
#0 Source "/home/jcwang/code/ws_di-lui-sam/src/di_lui_sam/third_parties/ikd-Tree/ikd_Tree.cpp", line 1268, in Search_by_range [0x7ffff72ecce4]
1265: if (!root->point_deleted)
1266: Storage.push_back(root->point);
1267: }
>1268: if ((Rebuild_Ptr == nullptr) || root->left_son_ptr != *Rebuild_Ptr)
1269: {
1270: Search_by_range(root->left_son_ptr, boxpoint, Storage);
1271: }
Segmentation fault (Address not mapped to object [(nil)])

Dear Admin:

First, thank you for sharing your invaluable codes.

But, I'd like to use your incremental Tree algorithm to achieve radius search; unfortunately, I think the code doesn't support the radius search function.

Is there any particular issue not implementing radius search?

Thanks in advance!

Hi, from what I can see in the code, you are using multiple threads, but all of the calculations are done by the CPU correct? Would it be possible to adjust the code to make use of the GPU using something like CUDA to be able to achieve even better performance?

我想创建一个自定义的PCL点云格式，然后使用IKD-TREE进行树的构建和搜索。
但是自定义的点云在创建树的时候代码报错：（尝试在头文件前面加上#define PCL_NO_PRECOMPILE仍然不起作用）
CMakeFiles/mesh_mapping_test.dir/src/test.cpp.o：在函数‘std::_Sp_counted_ptr<KD_TREE<PP>*, (__gnu_cxx::_Lock_policy)2>::_M_dispose()’中： /usr/include/c++/11/bits/shared_ptr_base.h:348：对‘KD_TREE<PP>::~KD_TREE()’未定义的引用 CMakeFiles/mesh_mapping_test.dir/src/test.cpp.o：在函数‘main.cold’中： /usr/include/c++/11/bits/shared_ptr_base.h:600：对‘KD_TREE<PP>::~KD_TREE()’未定义的引用

I can't understand the line 896, Isn't it supposed to be like this “ if(q.size()< k_nearest && (dist_left_node < q.top().dist || dist_right_node < q.top().dist)” ?

Hi,
thanks for your great works. ikdtree works well with one thread but not with multi thread. the
output are " *** Error in `./ikdtreeLoclization': double free or corruption (fasttop): 0x00007fcd1c000b50 *** "
and the test demo are:

    std::vector<PointType ,Eigen::aligned_allocator<PointType>> pointNear;
    std::vector<float> nearDis(nearNum);
    
    omp_set_num_threads(3);
    #pragma omp parallel for 
    for (int j = 0; j < lidarCurW->size() ; j++)
    {
            PointType pointJ=lidarCurW->points[j];
            ikdtree.Nearest_Search(pointJ,nearNum,pointNear,nearDis,5.0);
 }

hope for your reply, thanks

Hey,

can you explain to me what's the reason when this triggers?