Boost:: geometry: ближайшие соседи, используя круг

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

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

Я хочу на самом деле "Получите мне множество точек, которые находятся на расстоянии меньше, чем" n ".

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

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

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

Ответ 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

Ответ 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;
}

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