R-Trees: dois-je réinventer la roue?

J’essaie de comprendre comment implémenter un arbre R qui sera utilisé pour “sélectionner” un ensemble d’objects géomésortingques contenus dans un rectangle de délimitation. J’ai jeté un coup d’œil à l’ article sur Wikipedia, qui montre un exemple de disposition des données sous forme d’ arborescence B-Tree .

Je pourrais écrire un B-Tree et l’utiliser pour écrire un R-Tree, mais ce sont deux structures de données compliquées qu’il me faudrait déboguer, tester, etc. Je préférerais réutiliser une implémentation d’arborescence existante (std :: set / multiset) et assure l’opération de sorting.

En supposant que j’ai l’interface suivante pour mes formes:

class Shape { public: Shape(); virtual ~Shape(); const AABB & bounding_box() const = 0; }; 

Et fournissant ce foncteur pour commander des formes:

 struct OrderShapes { bool operator()(Shape * const & left, Shape * const & right) const { return right->bounding_box().contains(left->bounding_box()); } }; 

Est-ce qu’un std::set se comporterait comme un arbre R valide? Si non, comment puis-je résoudre ce problème sans réinventer la roue?

Vous pouvez également utiliser la bibliothèque Boost.Geometry:

http://www.boost.org/doc/libs/release/libs/geometry/doc/html/index.html

Si vous souhaitez utiliser vos propres types Point et AABB, vous devez les adapter aux concepts Point et Box afin d’indiquer à la bibliothèque Boost.Geometry comment gérer ces types. Voir la page suivante:

http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/reference/adapted/register/boost_geometry_register_box.html

sinon, vous pouvez utiliser ceux prédéfinis.

En supposant que vous souhaitiez stocker des pointeurs (j’utiliserai boost :: shared_ptr) dans l’arborescence, le code pourrait ressembler à ceci:

 #include  #include  #include  #include  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 Point; typedef bgm::box 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 > { typedef boost::shared_ptr 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, bgi::rstar<32> > rt; // Store some shapes rt.insert(boost::shared_ptr(new Shape())); rt.insert(boost::shared_ptr(new Shape())); rt.insert(boost::shared_ptr(new Shape())); /*...*/ // Search for some shapes std::vector > query_result; rt.query(bgi::intersects(AABB(/*...*/)), std::back_inserter(query_result)); BOOST_FOREACH(boost::shared_ptr & 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 & s, query_result) { rt.remove(s); } return 0; } 

N’oubliez pas que, étant donné que l’AABB est l’atsortingbut de Shape et que nous stockons des pointeurs, il est possible de modifier AABB depuis l’extérieur de l’index spatial. Vous ne devez pas modifier les données utilisées en tant que clé lorsque la valeur est stockée dans l’index ou le conteneur.

Si vous ne souhaitez pas stocker AABB dans la forme ni / et améliorer la sécurité des répertoires, vous pouvez stocker, par exemple, std :: pair . Vous ne pourrez pas modifier AABB utilisé pour l’indexation depuis l’extérieur de l’index. Dans ce cas, vous ne devez pas spécialiser bgi :: indexable <> car l’arborescence par défaut sait gérer le type std :: pair . Cela pourrait ressembler à ceci:

 // The value type typedef std::pair > MyVal; // The rtree bgi::rtree > rt; // Store a shape boost::shared_ptr s(new Shape()); rt.insert(std::make_pair(s->calculate_aabb(), s)); /* The rest of the code */ 

Les arbres R ne sont pas des arbres B. Ils ont quelques points communs, mais probablement pas plus que toute autre structure de données arborescente orientée bloc (= optimisée pour le disque).

IMHO, implémenter d’abord un B-Tree est bon pour deux choses: A) l’expérience, et B) obtenir une API stable pour une entrée / sortie de bloc rapide.

La principale difficulté de R-Trees n’est pas la requête . Ils sont assez simples à interroger. Le défi consiste à modifier efficacement l’arborescence, c’est-à-dire supprimer des éléments et en append, tout en maintenant l’équilibre de l’arbre. Dans un dataset à 1 dimension – c’est-à-dire dans un arbre B + -, cela est assez facile, car vous avez un voisin unique que vous pouvez utiliser pour l’équilibrage. Cela ne fonctionne plus dans les données de dimension supérieure.

Mais vous pouvez bien sûr rechercher des bibliothèques R-tree libspatialindex telles que libspatialindex

PS Pour interroger l’arborescence R, il faut des overlaps et non des contains .

std :: set se comporte comme un arbre R valide?

Définitivement non. La STL ne contient même pas d’implémentation B-tree. std :: set est simplement un arbre rouge-noir, pas un arbre B-tree.

Comment puis-je résoudre ce problème sans réinventer la roue?

Avez-vous vu cette réponse?