как построить RTree, используя заданные точки данных - PullRequest
Новая
       7

как построить RTree, используя заданные точки данных

7 голосов
/ 01 мая 2011

Мне нужно построить R-дерево , используя заданные точки данных. Я искал реализацию R-дерева. Во всей реализации я нашел конструкцию r-дерева, когда в качестве входных данных дали координаты прямоугольника. Мне нужно построить r дерево, когда заданы данные, само по себе (оно может быть 1-мерным). Код должен позаботиться о создании прямоугольников, которые заключают эти точки данных и построить r дерево.

Ответы [ 3 ]

5 голосов
/ 23 декабря 2011

Используйте MBR ( Минимальный ограничивающий прямоугольник ) с min = max = координатой.Они все так делают.Хорошие реализации, однако, будут хранить точечные данные с примерно вдвое большей емкостью в листьях, чем в узлах каталога.

2 голосов
/ 09 января 2015

Если вы ищете реализацию C ++, то, что содержится в Boost.Geometry в настоящее время (Boost. 1.57), может хранить точки, ящики и сегменты. Очевидное преимущество состоит в том, что данные в листах дерева не дублируются, что означает, что используется меньше памяти, лучше кэширование и т. Д. Использование выглядит следующим образом: 

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/index/rtree.hpp>

#include <vector>

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

int main()
{
    typedef bg::model::point<float, 2, bg::cs::cartesian> point;
    typedef bg::model::box<point> box;

    // a container of points
    std::vector<point> points;

    // create the rtree
    bgi::rtree< point, bgi::linear<16> > rtree(points.begin(), points.end());

    // insert some additional points
    rtree.insert(point(/*...*/));
    rtree.insert(point(/*...*/));

    // find points intersecting a box
    std::vector<point> query_result;
    rtree.query(bgi::intersects(box(/*...*/)), std::back_inserter(query_result));

    // do something with the result
}
0 голосов
/ 26 декабря 2012

Я предполагаю, что использование Rtree для хранения очков кажется неправильным использованием. Хотя этот тип структуры предназначен для хранения пространственных данных, после некоторых исследований, которые я только что обнаружил, она лучше всего подходит для хранения областей с ненулевой областью (так как R в названии означает Region или Rectangle). Создание простой таблицы с хорошим индексом должно обеспечить лучшую производительность для обновления и поиска данных. Рассмотрим мой пример ниже: 

CREATE TABLE locations (id, latitude, longitude);
CREATE INDEX idx_locations ON locations (latitude, longitude);

предпочтительнее, чем 

CREATE VIRTUAL TABLE locations USING rtree( id, minLatitude, maxLatitude, minLongitude, maxLongitude);

, если вы просто планируете повторять minLatitude для maxLatitude и minLongitude для maxLongitude для каждой строки, чтобы представлять точки, а не прямоугольники. Хотя последний подход будет работать должным образом, Rtrees подходят для индексирования прямоугольных областей, и их использование для хранения точек является неправильным использованием с худшей производительностью. Предпочитаю составной индекс, как указано выше.

Дальнейшее чтение: http://www.deepdyve.com/lp/acm/r-trees-a-dynamic-index-structure-for-spatial-searching-ZH0iLI4kb0?key=acm

...