boost :: geometry:使用圆圈的最近邻居

Question

我正在使用boost :: geometry 的Rtree实现来存储(大量)2D点.现在我需要做距离最近的neigbors查询.

但是,本手册仅将查询描述为矩形框(即"获取此矩形内的所有点")或"KNN"查询("从此处获取最近的'n'点).

我想要的实际上是"让我得到距离小于'n'的点集."

我注意到你可以定义一元谓词,但是是......一元(因此,不适合两点的条件).

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

有没有其他方法来处理这样的查询？或者它根本不可能？

Answer 1

记录在案的"用户定义查询"中的最后一个示例显示了如何在谓词中使用lambda.此lambda可以绑定范围中的其他变量,例如,您要查找其邻居的点.

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

#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

Answer 2

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

我认为这是正确的。

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

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

此外，您可以使用非常大的 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;
}

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