Hi,

Zhe Li Via Geometry wrote:
Below is the visitor code I wrote. The struct 'tempnode' is used to be
stored as a temp result in the priority queue.



How should I change it to meet the requirement?

In the elements container of internal node there are pairs of MBR and node pointer. When you call apply_visitor() you're passing node and visitor into it and inside this function the node is dispatched either into internal_node or leaf and passed into your visitor. So you should rather store node pointer or node reference with MBR, not a copy of internal node. In fact you could simply store pairs that are contained in elements container. You could define the type of the pair like that:

typedef typename bgid::rtree::elements_type<internal_node>::type elements_type;
typedef boost::range_value<elements_type>::type mbr_node_ptr_pair_t;

Actually, my problem is quite similar to visiting the MBRs level by level
(breadth first), so if there is an example of breadth-first visiting using
visitor, I think I could figure out my problem according to it.

Here you go, breadth-first and depth-first printing of internal nodes MBRs and leafs elements numbers. Note that I only store node pointers of the nodes that are going to be traversed next in m_nodes container and that you have to keep traversing also when you reach leafs because there may be nodes left in the container.

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

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

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bgi::rtree<point, bgi::linear<3> > rtree;
typedef bg::model::box<point> box;

template
<
    typename Value,
    typename Options,
    typename Translator,
    typename Box,
    typename Allocators>
class breadth_first_visitor
    : public bgid::rtree::visitor
        <
            Value,
            typename Options::parameters_type,
            Box,
            Allocators,
            typename Options::node_tag,
            true
        >::type

{
    typedef typename bgid::rtree::internal_node
        <
            Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag
        >::type internal_node;

    typedef typename bgid::rtree::leaf
        <
            Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag
        >::type leaf;

    typedef typename Allocators::node_pointer node_pointer;

public:
    void operator()(internal_node const& n)
    {
        typedef typename bgid::rtree::elements_type<internal_node>::type elements_type;
        elements_type const& elements = bgid::rtree::elements(n);

        for ( typename elements_type::const_iterator it = elements.begin();
              it != elements.end() ; ++it)
        {
            // do something with MBR
            std::cout << bg::dsv(it->first) << std::endl;

            // add child node pointer to the container
            m_nodes.push_back(it->second);
        }

        traverse();
    }

    void operator()(leaf const& n)
    {
        std::cout << boost::size(bgid::rtree::elements(n)) << " elements in leaf" << std::endl;

        traverse();
    }

private:
    void traverse()
    {
        if (! m_nodes.empty())
        {
            node_pointer next = m_nodes.front();
            m_nodes.pop_front();

            bgid::rtree::apply_visitor(*this, *next);
        }
    }

    std::deque<node_pointer> m_nodes;
};

template
<
    typename Value,
    typename Options,
    typename Translator,
    typename Box,
    typename Allocators>
class depth_first_visitor
    : public bgid::rtree::visitor
        <
            Value,
            typename Options::parameters_type,
            Box,
            Allocators,
            typename Options::node_tag,
            true
        >::type

{
    typedef typename bgid::rtree::internal_node
        <
            Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag
        >::type internal_node;

    typedef typename bgid::rtree::leaf
        <
            Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag
        >::type leaf;

    typedef typename Allocators::node_pointer node_pointer;

public:
    void operator()(internal_node const& n)
    {
        typedef typename bgid::rtree::elements_type<internal_node>::type elements_type;
        elements_type const& elements = bgid::rtree::elements(n);

        for ( typename elements_type::const_iterator it = elements.begin();
              it != elements.end() ; ++it)
        {
            // do something with MBR
            std::cout << bg::dsv(it->first) << std::endl;

            // traverse
            node_pointer next = it->second;
            bgid::rtree::apply_visitor(*this, *next);
        }
    }

    void operator()(leaf const& n)
    {
        std::cout << boost::size(bgid::rtree::elements(n)) << " elements in leaf" << std::endl;
    }
};

template <typename Rtree>
inline void print_breadth_first(Rtree const& tree)
{
    typedef bgid::rtree::utilities::view<Rtree> RTV;
    RTV rtv(tree);

    breadth_first_visitor
        <
            typename RTV::value_type,
            typename RTV::options_type,
            typename RTV::translator_type,
            typename RTV::box_type,
            typename RTV::allocators_type
        > v;
   
    rtv.apply_visitor(v);
}

template <typename Rtree>
inline void print_depth_first(Rtree const& tree)
{
    typedef bgid::rtree::utilities::view<Rtree> RTV;
    RTV rtv(tree);

    depth_first_visitor
        <
            typename RTV::value_type,
            typename RTV::options_type,
            typename RTV::translator_type,
            typename RTV::box_type,
            typename RTV::allocators_type
        > v;
   
    rtv.apply_visitor(v);
}


int main()
{
    rtree tree;

    for (int i = 0 ; i < 10 ; i += 1)
        tree.insert(point(i, i));

    std::cout << "breadth first" << std::endl;
    print_breadth_first(tree);
    std::cout << "depth first" << std::endl;
    print_depth_first(tree);
}

I get the following results:

breadth first
((4, 4), (9, 9))
((0, 0), (3, 3))
((6, 6), (7, 7))
((4, 4), (5, 5))
((8, 8), (9, 9))
((0, 0), (1, 1))
((2, 2), (3, 3))
2 elements in leaf
2 elements in leaf
2 elements in leaf
2 elements in leaf
2 elements in leaf
depth first
((4, 4), (9, 9))
((6, 6), (7, 7))
2 elements in leaf
((4, 4), (5, 5))
2 elements in leaf
((8, 8), (9, 9))
2 elements in leaf
((0, 0), (3, 3))
((0, 0), (1, 1))
2 elements in leaf
((2, 2), (3, 3))
2 elements in leaf

Adam