12

我正在使用 boost::geometry 的Rtree实现来存储（大量）2D 点。现在我需要进行基于距离的最近邻查询。

但是，该手册仅将查询描述为矩形框（即“获取此矩形内的所有点”）或“KNN”查询（“从此处获取最近的“n”个点）。

我想要的实际上是“给我一组距离小于'n'的点”。

我注意到您可以定义一元谓词，但 is... 一元（因此，不适合两点的条件）。

手册记录了一些model::ring我起初认为可能适合圆形的类，但它实际上更像是一种分段线（多边形）。这个假设正确吗？

有没有另一种方法来处理这样的查询？还是根本不可能？

4

2 回答 2

9

记录在案的“用户定义的查询”中的最后一个示例显示了如何在谓词中使用 lambda。此 lambda 可以绑定范围内的其他变量，例如，您正在寻找其邻居的点。

这是一个小例子。该示例查找比 2 个单位更接近 (5, 5) 的点，以查找位于直线 上的点的集合y = x。它应该很容易修改，以便首先检查所寻找的点是否在 R-tree 中，或者直接从 R-tree 中获取。

#include <iostream>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/index/rtree.hpp>


namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef std::pair<point, unsigned> value;

int main(int argc, char *argv[])
{
    bgi::rtree< value, bgi::quadratic<16> > rtree;

    // create some values
    for ( unsigned i = 0 ; i < 10 ; ++i )
    {
        point p = point(i, i);
        rtree.insert(std::make_pair(p, i));
    }

    // search for nearest neighbours
    std::vector<value> returned_values;
    point sought = point(5, 5);
    rtree.query(bgi::satisfies([&](value const& v) {return bg::distance(v.first, sought) < 2;}),
                std::back_inserter(returned_values));

    // print returned values
    value to_print_out;
    for (size_t i = 0; i < returned_values.size(); i++) {
        to_print_out = returned_values[i];
        float x = to_print_out.first.get<0>();
        float y = to_print_out.first.get<1>();
        std::cout << "Select point: " << to_print_out.second << std::endl;
        std::cout << "x: " << x << ", y: " << y << std::endl;
    }

    return 0;
}

在 OS X 上使用通过 Macports 安装的 Boost 进行编译和运行：

$ c++ -std=c++11 -I/opt/local/include -L/opt/local/lib main.cpp -o geom && ./geom
Select point: 4
x: 4, y: 4
Select point: 5
x: 5, y: 5
Select point: 6
x: 6, y: 6
于 2014-04-07T10:58:53.777 回答
5

该手册记录了一些我最初认为可能适合圆形的 model::ring 类，但它实际上更像是一种分段线（多边形）。这个假设正确吗？

我认为这是正确的。

我注意到您可以定义一元谓词，但 is... 一元（因此，不适合两点的条件）。

“第二个”（或参考）点不会固定吗？因为那时您可以使用简单的绑定表达式来提供参考点。

此外，您可以使用非常大的 KNN 算法，n并在谓词上添加某种破坏条件：

中断或暂停查询

for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
      it != tree.qend() ; ++it )
{
    // do something with value
    if ( has_enough_nearest_values() )
        break;
}

这可以很好地工作，假设该算法已经按距离递增的顺序遍历了这些点（当然，您需要检查该假设）。

于 2014-04-07T10:39:47.377 回答