boost::geometry: ближайшие соседи по кругу

Question

Я использую реализацию Rtree Boost:: Geometry для хранения (много) 2D точек. Теперь мне нужно сделать дистанционные запросы ближайших соседей.

Тем не менее, руководство описывает запросы только в виде прямоугольников (например, "Получите мне все точки, которые находятся внутри этого прямоугольника") или запросов "KNN" ("Получите мне ближайшие 'n' точек отсюда).

То, что я хочу, это на самом деле "получить мне набор точек, которые находятся на расстоянии меньше, чем" н "".

Я заметил, что вы можете определить унарный предикат, но он... унарный (таким образом, не подходит для условия по двум точкам).

Руководство документирует некоторые model::ring класс, который я подумал сначала, может подходить для круга, но на самом деле это скорее кусочная линия (многоугольник). Это предположение верно?

Есть ли другой способ обработать такой запрос? Или это просто невозможно?

Answer 1

Последний пример в документированных "Определяемых пользователем запросах" показывает, как использовать лямбду в предикате. Эта лямбда может связывать другие переменные в области видимости, например, точку, соседей которой вы ищете.

Вот небольшой пример. Пример ищет точки, которые ближе к (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;
}

Скомпилируйте и запустите Boost, установленный через Macports на 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

Answer 2

Руководство описывает некоторый класс model::ring, который, на мой взгляд, может подходить для круга, но на самом деле это скорее кусочная линия (многоугольник). Это предположение верно?

Я думаю, что это правильно.

Я заметил, что вы можете определить унарный предикат, но он... унарный (таким образом, не подходит для условия по двум точкам).

Не будет ли зафиксирована "вторая" (или контрольная) точка? Потому что тогда вы можете использовать простое выражение связывания для указания контрольной точки.

---

Кроме того, вы можете использовать алгоритм 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;
}

Это может работать довольно хорошо, если предположить, что алгоритм уже пересекает точки в порядке возрастания расстояния (вы, конечно, захотите проверить это предположение).