如何使用boost::geometry::index::rtree查找球域内的所有邻近点？

1. 如何设置查询的包围盒（预期为单点） #

如果你的需求是查找与目标点完全重合的已有点，可以构造一个最小包围盒——将包围盒的最小点和最大点都设为目标点：

point2 target = ...; // 你的目标点
boost::geometry::model::box<point2> query_box(target, target);

将这个box传入RTree的query方法，就能得到所有与目标点坐标完全一致的点。

但结合你的业务场景（找欧氏距离小于epsilon的点），你实际需要的是目标点的epsilon邻域查询，这时应该构造一个以目标点为中心、边长为2*epsilon的轴对齐包围盒，以此缩小候选范围：

point2 target = ...;
double epsilon = ...;
// 构造包围盒的最小/最大点
point2 min_pt(target.x() - epsilon, target.y() - epsilon);
point2 max_pt(target.x() + epsilon, target.y() + epsilon);
boost::geometry::model::box<point2> query_box(min_pt, max_pt);

2. RTree是否仅支持矩形查询？有没有更合适的结构？ #

Boost Geometry的RTree本身原生只支持基于轴对齐包围盒的空间查询（比如相交、包含等），不直接支持球域（欧氏距离范围）查询，但可以通过“矩形预过滤+精确距离验证”的方式实现需求，且在二维场景下性能足够：

1. 先用上述构造的轴对齐包围盒查询RTree，得到所有落在矩形内的候选点；
2. 对每个候选点计算与目标点的欧氏距离，过滤出距离小于epsilon的点。

这种方式利用RTree快速排除大部分无关点，再通过精确计算得到最终结果，平衡了性能和实现复杂度。

如果追求原生支持球域查询的数据结构，可以考虑：

• ANN库：专注于近邻搜索，原生支持k近邻和欧氏距离范围查询，适合二维及高维场景；
• FLANN库：提供快速近似近邻搜索，支持多种距离度量，在大规模数据下性能表现优异；
• kd-tree实现：很多开源库或手写的kd-tree都原生支持球域范围查询，二维场景下实现成本较低。

内容的提问来源于stack exchange，提问作者0xbadf00d