R-Trees: я должен заново изобрести колесо?
Я пытаюсь понять, как реализовать R-дерево, которое будет использоваться для «выбора» набора геометрических объектов, содержащихся в ограничивающем прямоугольнике. Я проверил статья в Википедии, которая показывает пример размещения данных в виде B-Tree.
я мог написать B-Tree и использовать его для написания R-Tree, но это две сложные структуры данных, которые мне придется отлаживать, тестировать и т. д. Я бы предпочел повторно использовать существующую реализацию дерева (std :: set / multiset) и обеспечить операцию сортировки.
Предполагая, что у меня есть следующий интерфейс для моих фигур:
class Shape
{
public:
Shape();
virtual ~Shape();
const AABB & bounding_box() const = 0;
};
И предоставление этого функтора для заказа Shapes:
struct OrderShapes
{
bool operator()(Shape * const & left, Shape * const & right) const
{
return right->bounding_box().contains(left->bounding_box());
}
};
Был бы std::set<Shape *, OrderShapes> вести себя как действительный R-Tree?
Если нет, как я могу решить эту проблему, не изобретая велосипед?
Решение
Вы также можете использовать библиотеку Boost.Geometry:
http://www.boost.org/doc/libs/release/libs/geometry/doc/html/index.html
Если вы хотите использовать свои собственные типы Point и AABB, вам следует адаптировать их к концепциям Point и Box, чтобы сообщить библиотеке Boost.Geometry, как обрабатывать эти типы. Например. см. следующую страницу:
в противном случае вы можете использовать предопределенные.
Предполагая, что вы хотите хранить указатели (я буду использовать boost :: shared_ptr) в rtree, код может выглядеть так:
#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/foreach.hpp>
#include <vector>
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
namespace bgm = boost::geometry::model;
/* The registration of your Point and Box types goes here */
// OR use predefined ones
typedef bgm::point<float, 2, bg::cs::cartesian> Point;
typedef bgm::box<Point> AABB;
class Shape
{
public:
Shape() {}
virtual ~Shape() {}
const AABB & bounding_box() const { return m_aabb; }
private:
AABB m_aabb;
};
// Tell the rtree how to extract the AABB from the Shape
namespace boost { namespace geometry { namespace index {
template <>
struct indexable< boost::shared_ptr<Shape> >
{
typedef boost::shared_ptr<Shape> V;
typedef AABB const& result_type;
result_type operator()(V const& v) const { return v->bounding_box(); }
};
}}} // namespace boost::geometry::index
int main()
{
// The rtree
bgi::rtree< boost::shared_ptr<Shape>, bgi::rstar<32> > rt;
// Store some shapes
rt.insert(boost::shared_ptr<Shape>(new Shape()));
rt.insert(boost::shared_ptr<Shape>(new Shape()));
rt.insert(boost::shared_ptr<Shape>(new Shape()));
/*...*/
// Search for some shapes
std::vector<boost::shared_ptr<Shape> > query_result;
rt.query(bgi::intersects(AABB(/*...*/)), std::back_inserter(query_result));
BOOST_FOREACH(boost::shared_ptr<Shape> & s, query_result)
{
/* Do something with each shape */
/* but don't modify the AABB if the Shape is stored in the rtree! */
}
// Remove them from the rtree
BOOST_FOREACH(boost::shared_ptr<Shape> & s, query_result)
{
rt.remove(s);
}
return 0;
}
Имейте в виду, что, поскольку AABB является атрибутом Shape, а мы храним указатели, можно изменять AABB вне пространственного индекса rtree. Вы не должны изменять данные, используемые в качестве Ключа, когда Значение хранится в индексе или контейнере.
Если вы не хотите хранить AABB внутри Shape или / и улучшать безопасность дерева, вы можете хранить, например, станд :: пара< AABB, boost :: shared_ptr>. Вы не сможете изменить AABB, используемый для индексации, снаружи индекса. В этом случае вы не должны специализировать bgi :: indexable<> потому что rtree по умолчанию знает, как обрабатывать std :: pair< Коробка, …> типа. Это может выглядеть так:
// The value type
typedef std::pair<AABB, boost::shared_ptr<Shape> > MyVal;
// The rtree
bgi::rtree<MyVal, bgi::rstar<32> > rt;
// Store a shape
boost::shared_ptr<Shape> s(new Shape());
rt.insert(std::make_pair(s->calculate_aabb(), s));
/* The rest of the code */
Другие решения
R-деревья являются не B-деревья. Они действительно имеют некоторые общие черты, но, вероятно, не больше, чем любая другая блочная (= дисковая оптимизация) древовидная структура данных.
ИМХО, реализация B-Tree в первую очередь хороша для двух вещей: A) опыта и B) получения стабильного API для быстрого блочного ввода-вывода.
Основная сложность с R-Trees заключается в не запрос. Они в значительной степени прямо к запросу. Задача состоит в том, как эффективно изменить дерево, то есть удалить элементы и добавить элементы, сохраняя при этом дерево сбалансированным. В одномерном наборе данных, т. Е. В дереве B +, это довольно просто, поскольку у вас есть уникальный сосед, который вы можете использовать для балансировки. Это больше не работает в данных более высокого измерения.
Но вы, конечно, можете найти существующие библиотеки R-дерева, такие как libspatialindex
Постскриптум Для запроса R-дерева вам нужно overlapsне contains,
std :: set ведет себя как действительное R-дерево?
Определенно нет. STL даже не содержит реализацию B-дерева. std :: set — это просто красно-черное дерево, а не B-дерево.
Как я могу решить эту проблему, не изобретая велосипед?