boost::geometry：使用圆查找最近邻居

Question

boost::geometry：使用圆查找最近邻居

c++boostboost-geometry

15

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

然而，手册只描述了矩形框查询（即“获取所有在此矩形内的点”）或KNN查询（“从这里获取最近的'n'个点）。

我想要的是“获取距离小于'n'的点集”。

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

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

还有其他处理这种查询的方法吗？还是根本不可能？

- kebs

2个回答

7

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

我认为这是正确的。

我注意到您可以定义一个一元谓词，但它是...一元的（因此，不适合两点之间的条件）。第二个（或参考）点不能固定吗？因为那样你就可以使用简单的绑定表达式来提供参考点。

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

Breaking or pausing the query

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;
}

假设算法已按距离升序遍历点（当然，您需要检查这个假设），那么这可能会非常有效。

- sehe

谢谢你的回答，实际上你是对的，我混淆了关于谓词的事情，一个具有适当绑定的一元谓词应该可以胜任这项工作，我会尽快测试。你的第二个建议也很有趣，但我认为它不适用，因为点密度不均匀（完全不均匀...），有些请求将返回0，而其他请求将返回非常大量的点。 - kebs

1

@kebs 我的意思是你可以使用标准的NNK，并在距离阈值之后将其截断。这假设点按最近到最远的顺序访问（这在空间索引中可能是真实的，但也可能不是 - 我对库的这部分知之甚少）。 - sehe

1

请注意，kNN查询会更慢，因为内部执行的操作比空间查询更多。 - Adam Wulkiewicz

1

在最近查询迭代器的情况下，保证首先获取最接近的点。在query()函数的情况下，您可以假设输出的顺序是随机的（尽管这并不完全正确）。 - Adam Wulkiewicz

4

@sehe 我写了这个。我会在文档中添加一些附加信息。顺便说一句，Boost现在可以在GitHub上获取，因此如果您认为应该添加/扩展某些内容，请随意fork仓库并创建pull request。文档使用QuickBook格式，例如关于查询的章节可以在此处找到：https://github.com/boostorg/geometry/blob/develop/doc/index/rtree/query.qbk 如果您想自己构建文档并遇到问题，可以通过邮件列表与我们联系：http://lists.boost.org/mailman/listinfo.cgi/geometry - Adam Wulkiewicz

显示剩余6条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- logc · Accepted Answer

在文档中最后一个"用户定义查询"的示例展示了如何在谓词中使用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;
}

在Mac 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