动态最临近点算法求助

[wdc63]

当前项目有实现以下算法的需求:

1 二维点集的最临近点查询，一次只需查询一个临近点

2 查询返回后需要实时删除得到的临近点

3 在未来某个时间需要重新插入前面被删除的对象

4 点集数不超过 50000 ，点由两个单精度浮点数定义，取值范围-500 ，500

5 对初次建立数据结构或者索引的时间或内存没有特别的需求，只要不太夸张就行。

使用 c#开发，非 unity ，整个项目对性能十分敏感，已经测试了 codeandcats 的 kdtree 开源库( https://github.com/codeandcats/KdTree )，实测很慢，对于 10000 个点进行 10000 次查询(同时进行删除操作)要花费 300ms-1800ms ，而我看到的类似 c++库 10 万点集进行十万次查询只需要个位数毫秒。codeandcats 的算法中很多浪费，例如返回的节点是新建的，因此在删除的时候需要遍历 kdtree 对比找到相应的节点。

类似的还有 ericreg 的 kdtree ，号称比前者快 7.5 倍，但是没有实现删除功能。希望性能能达到 10000 个点的查询和动态删增能达到 1 万次低于 5ms 。

也搜索过各种 rtree quadtree octree 等等，没有发现能完整实现需要功能的开源库。目前不太想自己重新造轮子，请问各位大佬有没有满足上述需求，性能较好的 c#可用的库。如果没有请各位大佬按上述需求指一条最优的算法解决方案。

[nightwitch]

有现成的 c++库的话且满足需求的话，包装一下导出 dll 给 c ＃用呗

[wdc63]

@nightwitch C++基础太弱，之前尝试过一个简单 单文件库都没能搞定，现成可用的库十几个.cpp 文件，难以下手。

[wdc63]

现在两条路线：1 PH-Tree ，据作者描述 phtree 的查询插入和删除操作都是 O(logn)的复杂度，但是看了下代码很多 https://github.com/tzaeschke/phtree
2 还是使用传统的 KDTree ，由于本项目在删除插入的工作中不会重新插入任何新点，只是把已经被选择的暂时移除，然后再移动回来而已，因此这里就直接用一个 flag 标记已经被删除的点，在 kdtree 查询最近点时，遇到这种已经被“删除”的点直接跳过。目前已经根据现有项目有一个初步实现，实测这种方法性能还不错。