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

Я пытаюсь создать дерево boost r с алгоритмом упаковки, в котором будут храниться двумерные геометрические точки. Просто чтобы быть ясным, мне не нужен поиск kNN, мне нужно найти точки, которые находятся в стороне от горизонта точки, которая является членом того же дерева r (горизонт будет радиусом). То, что я нашел до сих пор, было примерами поиска на расстоянии с использованием случайной точки (не точки, которая является членом r-дерева). Я выполнил проверку расстояния и индекса, используя bg::index::satisfies, передав метод, который проверяет, отличается ли индекс и меньше ли расстояние, чем радиус. Также я использую внутри (поле), но я не уверен, что это правильный способ использования пространственного поиска дерева 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;
}
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
0
1 027
1

Ответы 1

Also I use within(box), but I'm not sure that is the correct way

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

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

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

Другие вопросы по теме