|
|
Geometry : |
Subject: Re: [geometry] breadth first visiting with visitor for R tree's MBRs
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2018-03-02 00:13:26
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
Geometry list run by mateusz at loskot.net