Многоуровневые запросы на R-деревьях (пересечение, объединение)

Question

Скажем, у меня есть следующие настройки:

У меня есть boost::geometry::index::rtree, который принимает в качестве ключа двумерное поле и в качестве значения точки.Первое измерение блока на практике будет применяться к (действительным замкнутым) интервалам, тогда как второе только к точке.

Таким образом, мой блок выглядит так:

  using namespace std;
  typedef bg::model::point<unsigned long, 2, bg::cs::cartesian> _pt_t;
  typedef bg::model::box<_pt_t> _box_t;
  typedef pair<_box_t, unsigned long> tree_v_t;
  typedef bgi::rtree<tree_v_t, bgi::quadratic<16> > rtree_t;

Abox будет всегда инициализироваться с помощью:

_box_t _mb(unsigned long i, unsigned long s, unsigned long d){
    _box_t b(_pt_t(s, i), _pt_t(s + d, i));
    return b;
  }

Теперь, допустим, я инициализировал rtree и хочу выполнить два вида сложных запросов:

1. при заданном наборе siинтервалов set<pair<unsigned int, unsigned int> > и набора sp точек set<unsigned int>, я хотел бы перебрать все значения, которые являются результатом следующего псевдокода запроса:

any(si, intersect(rtree_level1)) &&
any(sp, contains(rtree_level2)) &&
value in ps

Другими словами, я хочу, чтобы поддерево для дерева, которое содержало пересечение интервалов, содержащихся в si, и точек, содержащихся в sp, и его значенияв sp.Если вам нравится, вы можете предположить, что все интервалы в si не пересекаются.

учитывая набор spi точек и интервалов set<unsigned int, pair<unsigned int, unsigned int> >, я хотел бы повторить все значения, которые являются результатом следующего псевдокода запроса:

any(spi, intersect(rtree_level1)(spi.interval) && 
         contains(rtree_level2)(spi.point) &&
         value in spi.point
   )

Другими словами, я хочу объединение всех поддеревьев , которые происходят от каждого элемента spi, для которого они являются пересечением данногоинтервал, и они содержат только эти точки как ключи (второй уровень), так и значения.Это похоже на union все R-деревья, полученные из запроса 1 , если оба si и sp имеют один элемент.

Я могу понять, как я могу это сделать, используя предикат satisfy и применяя transform к итератору, созданному qbegin, но каков самый эффективный способ сделать это в boost?

Answer 1

Вот базовая программа с двойным индексом (R-дерево и std :: map), выполняющая двунаправленную индексацию: от символа к блоку / интервалу и от блока / интервала к символу:

Включает, iostream требуется только для вывода.

#include <boost/geometry.hpp>
#include <map>
#include <vector>
#include <iostream>

Пространства имен для удобства.

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

Основной двунаправленный индекс, позволяющий вставлять пары box / interval-char и находить box на основе charили вектор символов на основе коробки (пересекающийся).insert() объединяет блоки при необходимости.

template <typename Box, typename T>
class rtree_map_index
{
    typedef std::map<T, Box> map_type;
    typedef typename map_type::iterator map_iterator;
    typedef typename map_type::const_iterator map_const_iterator;
    typedef std::pair<Box, map_iterator> rtree_value;
    typedef bgi::rtree<rtree_value, bgi::rstar<4> > rtree_type;

public:
    void insert(Box const& box, T const& v)
    {
        std::pair<map_iterator, bool>
            p = m_map.insert(std::make_pair(v, box));

        map_iterator map_it = p.first;
        T const& map_val = map_it->first;
        Box & map_box = map_it->second;

        // new key,value inserted into map
        if (p.second)
        {
            // insert it to the r-tree
            m_rtree.insert(rtree_value(map_box, map_it));
        }
        // key already exists in map and box has to be expanded
        else if (! bg::covered_by(box, map_box))
        {
            // calculate expanded box
            Box new_box = map_box;
            bg::expand(new_box, box);

            // update r-tree
            m_rtree.remove(rtree_value(map_box, map_it));
            m_rtree.insert(rtree_value(new_box, map_it));

            // update map
            map_box = new_box;
        }
    }

    bool find(T const& v, Box & result) const
    {
        map_const_iterator it = m_map.find(v);
        if (it != m_map.end())
        {
            result = it->second;
            return true;
        }

        return false;
    }

    void find(Box const& box, std::vector<char> & result) const
    {
        std::vector<rtree_value> res;
        m_rtree.query(bgi::intersects(box), std::back_inserter(res));

        result.resize(res.size());
        for (size_t i = 0; i < res.size(); ++i)
            result[i] = res[i].second->first;
    }

private:
    rtree_type m_rtree;
    map_type m_map;
};

Основная функция с базовым вариантом использования.

int main()
{

для двумерных данных, хранящихся в r-дереве (блоки).

    {
        typedef bg::model::point<double, 2, bg::cs::cartesian> point;
        typedef bg::model::box<point> box;
        rtree_map_index<box, char> index;

        index.insert(box(point(0, 0), point(3, 3)), 'a');
        index.insert(box(point(1, 1), point(4, 4)), 'a');
        index.insert(box(point(5, 5), point(6, 6)), 'b');

        box res1;
        index.find('a', res1);

        std::cout << bg::wkt(res1) << std::endl;

        std::vector<char> res2;
        index.find(box(point(4, 4), point(5, 5)), res2);

        BOOST_ASSERT(res2.size() == 2);
        std::cout << res2[0] << std::endl;
        std::cout << res2[1] << std::endl;
    }

для одномерных данных, хранящихся в r-дереве (интервалы)

    {
        typedef bg::model::point<double, 1, bg::cs::cartesian> point;
        typedef bg::model::box<point> box;
        rtree_map_index<box, char> index;

        index.insert(box(point(0), point(3)), 'a');
        index.insert(box(point(1), point(4)), 'a');
        index.insert(box(point(5), point(6)), 'b');

        box res1;
        index.find('a', res1);

        std::cout << "(" << bg::get<0, 0>(res1) << ", " << bg::get<1, 0>(res1) << ")" << std::endl;

        std::vector<char> res2;
        index.find(box(point(4), point(5)), res2);

        BOOST_ASSERT(res2.size() == 2);
        std::cout << res2[0] << std::endl;
        std::cout << res2[1] << std::endl;
    }

Конец.

    return 0;
}

Обратите внимание, что вместо rtreeВы могли бы использовать interval_map.Вы должны быть в состоянии построить на вершине rtree_map_index.Вы можете добавить конструктор, создающий map и rtree из контейнера элементов типа std::pair<Box, T>, чтобы воспользоваться преимуществами алгоритма упаковки r-дерева.Вы можете реализовать любую нужную вам функцию find().И т.д.