提高::几何：最近的邻居用圈子 [英] boost::geometry: nearest neighbors using a circle

问题描述

我使用的是 RTREE 实施的boost ::几何存储（大量的）2D点。现在我需要做的基于距离的最近neigbors查询。

I am using the Rtree implementation of boost::geometry to store (lots of) 2D points. Now I need to do distance-based nearest neigbors queries.

但是，手动<一个href=\"http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html\">only描述查询矩形箱（​​即把我的一切，此矩形内的点）或KNN查询（给我从这里最近的'N'点）。

However, the manual only describes queries as rectangular boxes (i.e. "Get me all the points that are inside this rectangle") or "KNN" queries ("Get me the nearest 'n' points from here).

我要的其实是给我是在距离小于'N'点的集合。

What I want is actually "Get me the set of points that are at a distance less than 'n'".

我注意到，你可以定义一个unary- predicate，但是是...一元（因此，并不适用于两点的情况）。

I noticed that you can define a unary-predicate, but is is... unary (thus, not suitable for a condition on two points).

本手册文件中某些<一个href=\"http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/reference/models/model_ring.html\"><$c$c>model::ring我想在第一类可能适合了一圈，但它实际上更多的是一种一分段线（多边形）的。是假设是正确的？

The manual documents some model::ring class that I thought at first might fit for a circle, but it is actually more a kind of a piece-wise line (a polygon). Is that assumption correct ?

有另一种方式来处理这样的查询？或者是根本不可能的？

Is there another way to process such a query ? Or is it simply not possible ?

推荐答案

的<一个href=\"http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html#geometry.spatial_indexes.queries.user_defined_unary_$p$pdicate\">last例如，在记录的用户自定义查询展示了如何在predicate使用lambda。这拉姆达可以绑定其他变量的范围，例如，他的邻居你正在寻找的点。

The last example in the documented "User-defined queries" shows how to use a lambda in the predicate. This lambda can bind other variables in the scope, for instance, the point whose neighbors you are looking for.

下面是一个小例子。这个例子寻找那些更接近点（5,5），比2个单位，为趴在直 Y = X 点的集合。应该很容易以第一检查，如果寻求点处于R-树，或直接把它弄出来的R树的修改

Here is a small example. The example looks for points that are closer to (5, 5) than 2 units, for a collection of points that lie on the straight y = x. It should be easy to modify in order to check first if the sought point is in the R-tree, or get it directly out of the 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;
}

编译并通过安装MacPorts的OS X上运行升压：

Compile and run with Boost installed via Macports on OS X:

$ 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

这篇关于提高::几何：最近的邻居用圈子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！