Boost R tree для пространственного поиска - PullRequest
Новая
       51

Boost R tree для пространственного поиска

0 голосов
/ 20 февраля 2019

Я пытаюсь создать дерево надстроек с алгоритмом упаковки, в котором будут храниться 2D геометрические точки.Просто чтобы прояснить, мне не нужен поиск по kNN, но мне нужно найти точки, которые находятся в стороне от горизонта точки, являющейся членом того же самого r-дерева (горизонт был бы радиусом).До сих пор я обнаружил примеры для дистанционного поиска с использованием случайной точки (а не точки, являющейся членом r-дерева).Я сделал проверку расстояния и индекса с помощью bg :: index :: удовлетворяет, передав метод, который проверяет, отличается ли индекс и является ли расстояние меньше радиуса.Также я использую внутри (поле), но я не уверен, что это правильный способ использовать пространственное поиск r дерева для точки, которая является членом того же r дерева.Потому что, насколько я понимаю, точка в r-дереве знает индекс ящиков, в которых она содержится, поэтому не было бы способа запросить только точку и расстояние, и при этом не закончить поиск по всему дереву.!?

это мой код 

#include "stdafx.h"
#include <boost/function_output_iterator.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <vector>
#include <iostream>


namespace bg = boost::geometry;
namespace bgi = bg::index;

typedef bg::model::point <double, 2, bg::cs::cartesian> point;
typedef std::pair<point, std::size_t> pointI;
typedef bg::model::box<point> box;
typedef std::pair<point, unsigned> value;

bool CheckIndexAndDist(pointI i, pointI j, size_t dist);

std::vector<uint64_t> res;
struct StoreDataCallback
{
    template <typename Value>
    void operator()(Value const& v)
    {
        res.push_back(v.second);
    }
};


int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<point> contourCenters; // has some value
    std::vector<pointI> cloud;

    int horizon = 3;
    double dX = 0;
    double length = 20;
    double width = 20;
    dX = length/10.0;

    for(int i = 0; i < length; i++)
    {
        for(int j = 0; j < width; j++)
        {
            point p;
            p.set<0>((-1.0 * length / 2.0) + dX  + j * dX);
            p.set<1>((-1.0 * width / 2.0) + dX  + i * dX);
            contourCenters.push_back(p);
        }
    }
    size_t id_gen = 0;
    std::transform(
            contourCenters.begin(), contourCenters.end(),
            back_inserter(cloud), 
            [&](point const& p) { return std::make_pair(p, id_gen++); }
        );

     bgi::rtree<pointI, bgi::quadratic<16> > rtree(cloud);

     // spatial search
    box query_box(point(cloud[10].first.get<0>() - 3.2*dX, cloud[10].first.get<1>() - 3.2*dX),point(cloud[10].first.get<0>() + 3.2*dX, cloud[10].first.get<1>() + 3.2*dX));
    StoreDataCallback callback;


    res.clear();
    rtree.query(
    bgi::within(query_box) &&
    bgi::satisfies([&](value const& v) {return CheckIndexAndDist(v, cloud[10],3.015*dX);}),
    boost::make_function_output_iterator(callback));

    return 0;
}

bool CheckIndexAndDist(pointI i, pointI j, size_t dist)
{
    if( i.second != j.second &&  (bg::distance(i.first, j.first) < dist))
        return true;
    else
        return false;
}

1 Ответ

0 голосов
/ 30 апреля 2019

Также я использую в (поле), но я не уверен, что это правильный путь

Это правильно, то есть внутри предиката есть пространственный предикат, позволяющий R-деревуКроме того, геометрически отфильтровываются точки во время запроса и удовлетворяется предикат.Если бы Boost.Geometry имел концепцию окружности / сферы, вы могли бы передать ее непосредственно в предикат внутри, и удовлетворение не потребовалось бы, но так как это не тот случай, когда вы должны передать рамку вокруг круга.

Официальный интерфейс не поддерживает тип запроса, который вы хотите выполнить.Чтобы сделать что-то другое, вам нужно реализовать свой собственный посетитель R-дерева и применить его к R-дереву, используя boost::geometry::index::detail::rtree::utilities::view.Посмотрите на этот поток для более подробной информации.

R-дерево не знает, где в его структуре можно найти точку.Поэтому, если вы хотите выбрать одну произвольную точку и получить все точки в некотором радиусе вокруг нее, вам все равно придется пройтись по R-дереву, чтобы найти, где оно находится в первую очередь, и затем искать вокруг него.Таким образом, этот вид поиска будет иметь смысл, если вы хотите выполнить его для некоторого количества элементов, содержащихся в R-дереве, более чем в 1, потому что тогда вам фактически придется пройти часть R-дерева, но затем для каждого элемента.вы бы предварительно настроили поиск по радиусу.Краевой случай будет делать это для всех точек, обходя все R-дерево сверху вниз и локально возвращаясь вверх в структуре R-дерева для каждой точки, чтобы получить другие точки вокруг нее.

...