How to set Boost RTree Node with template class

Question

I have two files: header.h and code.cpp, I can not write any boost namespace on code.cpp, so all "boost::geometry::etc..." calls go on header.h. The idea is to implement two template classes: one for the RTree and other for the RTree Node, this way the user may include the header.h file and implement the RTree on code.cpp using the two template classes on header.h. This is what I have so far:

header.h:

template< class TT > class Node
{
    using PointType     = boost::geometry::model::d2::point_xy< TT >;
    using BoxType       = boost::geometry::model::box< PointType >;
    using NodeType      = std::pair< BoxType, std::string >;
    NodeType node;
public:
    Node(){}
    template< class T >
    Node( const BBox< T > &box, const std::string nodeName ){
        node = std::make_pair( BoxType{ PointType{ box.xLo(), box.yLo() },
                PointType{ box.xHi(), box.yHi() } }, nodeName );
    }
};


template< class TT > class RTree
{
    using RTreeType = boost::geometry::index::rtree< TT, boost::geometry::index::quadratic< 16 > >;
    RTreeType rtree;    
public:
    RTree(){}
    template< T >
    void insertBox( const BBox< T > &box, const std::string nodeName ) {
        rtree.insert( Node< T >( box, nodeName ) );
    }
    
    template< T >
    void query( const BBox< T > &box, std::vector< Node< T > > &queryResult ) {
        rtree.query( boost::geometry::index::intersects( Node< T >( box, "" ) ),
                      std::back_inserter( queryResult ) );
    }    
};

Some of the errors I am getting:

error: could not convert 'boost::geometry::index::detail::indexable<Node<int>, false>::NOT_VALID_INDEXABLE_TYPE31::assert_arg()' from 'mpl_::failed************(boost::geometry::index::detail::indexable<Node<int>, false>::NOT_VALID_INDEXABLE_TYPE::************)(Node<int>)' to 'mpl_::assert<false>::type' {aka 'mpl_::assert<false>'}
31 |     BOOST_MPL_ASSERT_MSG(
|     ^
|     |
|     mpl_::failed************ (boost::geometry::index::detail::indexable<Node<int>, false>::NOT_VALID_INDEXABLE_TYPE::************)(Node<int>)

...

error: could not convert 'boost::geometry::traits::point_type<Node<int> >::NOT_IMPLEMENTED_FOR_THIS_POINT_TYPE45::assert_arg()' from 'mpl_::failed************ (boost::geometry::traits::point_type<Node<int> >::NOT_IMPLEMENTED_FOR_THIS_POINT_TYPE::************)(mpl_::assert_::types<Node<int>, mpl_::na, mpl_::na, mpl_::na>)' to 'mpl_::assert<false>::type' {aka 'mpl_::assert<false>'}
45 |     BOOST_MPL_ASSERT_MSG
|     ^
|     |
|     mpl_::failed************ (boost::geometry::traits::point_type<Node<int> >::NOT_IMPLEMENTED_FOR_THIS_POINT_TYPE::************)(mpl_::assert_::types<Node<int>, mpl_::na, mpl_::na, mpl_::na>)

...

error: no type named 'type' in 'struct boost::geometry::traits::point_type<Node<int> >'
66 |         >::type type;
|                 ^~~~

It seems to me I have to use indexable. Although I am not sure how I am supposed to do it with the code I already have. Any help is welcome, thanks in advance.

Can you make the sample self-contained? What is Bbox? – sehe Aug 20 '22 at 15:37 — sehe, Aug 20 '22 at 15:37

sehe · Accepted Answer · 2022-08-20T16:27:21.737

We had to guess what BBox is. But all in all it looks like you "just" want a tree with nodes that are (box, name).

I'd suggest skipping the Node class (and all of the generics that wouldn't work anyways because you hardcoded the conversion to Node<T> anyways, which only works if the geometries were convertable (box and box don't interconvert).

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/index/rtree.hpp>
namespace bg  = boost::geometry;
namespace bgi = boost::geometry::index;

namespace detail {
    template <typename Coord> using Point = bg::model::d2::point_xy<Coord>;
    template <typename Coord> using BBox  = bg::model::box<Point<Coord>>;
    template <class Coord> using Node     = std::pair<BBox<Coord>, std::string>;
}

template <class Coord> struct RTree {
    using Point     = detail::Point<Coord>;
    using Box       = detail::BBox<Coord>;
    using Node      = detail::Node<Coord>;
    using RTreeType = bgi::rtree<Node, bgi::quadratic<16>>;

    void insertBox(Box box, const std::string nodeName) {
        rtree.insert(Node(box, nodeName));
    }

    using Result = std::vector<Node>;

    void query(Box box, Result& queryResult) {
        rtree.query(bgi::intersects(box), back_inserter(queryResult));
    }

  private:
    RTreeType rtree;
};

int main() {
    using Tree = RTree<double>;
    Tree x;
    x.insertBox({{1.0, 2.0}, {7.0, 8.0}}, "first");
    x.insertBox({{2.0, 3.0}, {6.0, 7.0}}, "second");

    Tree::Result v;
    x.query({{3.0, 4.0}, {5.0, 6.0}}, v);

    for (auto& [box,name] : v)
        std::cout << std::quoted(name) << ": " << bg::wkt(box) << "\n";
}

Prints

"first": POLYGON((1 2,1 8,7 8,7 2,1 2))
"second": POLYGON((2 3,2 7,6 7,6 3,2 3))

More

If really you're not showing the full picture, and you need Node<T> to be more than shown, consider

deriving from std::pair and using the existing indexable<> implementation
providing your own IndexableGetter

Showing the second Live On Coliru:

namespace detail {
    template <typename Coord> using Point = bg::model::d2::point_xy<Coord>;
    template <typename Coord> using BBox  = bg::model::box<Point<Coord>>;

    template <class Coord> struct Node {
        using Indexable = BBox<Coord>;
        using Id        = std::string;
        Indexable box;
        Id  name;

        Node(Indexable b, Id n) : box(std::move(b)), name(std::move(n)) {}

        struct Getter {
            using result_type = Indexable const&;
            result_type operator()(Node const& v) const { return v.box; }
        };
    };
}

template <typename Coord>
struct bgi::indexable<::detail::Node<Coord>>
    : ::detail::Node<Coord>::Getter {};

No further changes, still printing

"first": POLYGON((1 2,1 8,7 8,7 2,1 2))
"second": POLYGON((2 3,2 7,6 7,6 3,2 3))

The existence of Node class is because I want it to be possibly a pair or only Coord. So the idea I had was to implement a BaseNode class and inherit with two other with and without the pair. This way the user can use both options as he wants. Do you have any other suggestion to do so? — gudé, Aug 22 '22 at 18:10
Btw, BBox is another class already existent in the implementation I am working with. It is different from BoxType — gudé, Aug 22 '22 at 18:17
The code on header.h is already within an existing namespace and I am getting an error `error: declaration of 'struct boost::geometry::index::indexable >' in namespace 'mySpace' which does not enclose 'boost::geometry::index'`. I can only use indexable outside a namespace? — gudé, Aug 22 '22 at 18:53
You can not specialize `indexable` from within your own namespace, yes. So move the specialization outside `mySpace`. With regard to the other comments, if you have specific questions please post them - with relevant code. For now "Do you have any suggestion to do that" - yes, use the approach with the custom indexable getter shown — sehe, Aug 23 '22 at 05:32
Hi @sehe. Thanks a lot your answer helped so much. I have only one more question, I don't believe it requires another post here. I will implement now two other classes that inherit from Node, and their values will differ. How should I proceed with ::indexable, should I call it twice for each of them or only once for the base class? — gudé, Aug 24 '22 at 20:25
... I think you do need to at least show what you mean. This is what I imagine you meant: http://coliru.stacked-crooked.com/a/efab3e7c89fce833 Note that I chose not to specialize the `indexable<>` trait here but used the generalized `IndexableGetter` explicitly. — sehe, Aug 24 '22 at 21:35
That's not the code you have, because it doesn't even declare BBox. It's impossible to see what's wrong if the code is missing. May you can use my example as a starting point if you can't figure out how to make your own code self-contained? — sehe, Aug 26 '22 at 08:03

score 0 · Answer 2 · answered Sep 04 '22 at 14:30

For future reference.

I had trouble understanding how Boost sets the interface for the user to define their own object as the RTree node. It seems there are more than one way to do this (using macros for example). One of them is how @sehe pointed out, by using the Indexable functor. So this awkward struct Getter with a function description is a functor which overloads the () operator, and this is how Boost knows how to get coordinates from my own class.

How to set Boost RTree Node with template class

2 Answers2

More