Geometry Boost List: [geometry] breadth first visiting with visitor for R tree's MBRs

Subject: [geometry] breadth first visiting with visitor for R tree's MBRs
From: Zhe Li (17902731r_at_[hidden])
Date: 2018-03-01 05:00:34

Dear all,

I'm a research student currently studying the effect of the number of MBRs
in KNN search. So I need to extract a specific number of MBRs from an R
tree. The extraction algorithm could be described as:

   •Put the root node in a priority queue, with descending order regarding
its coverage area 

   •Pop the head from the priority queue, and insert its sub-nodes into the
priority queue

   •Until the total MBRs exceed the specified number of MBRs or there are
not enough MBRs

But I met some problem using the visitor when implementing the above
algorithm. When I try to add the sub-nodes into the priority queue, it
failed.

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? 

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.

Regards, Zhe

namespace bg = boost::geometry;

namespace bgi = boost::geometry::index;

namespace bgid = bgi::detail;

typedef bgi::rtree<Point, bgi::linear&lt;3>> rtree;

typedef bg::model::point<float, 2, bg::cs::cartesian> point;

typedef bg::model::box<Point> box;

typedef bgid::rtree::utilities::view<rtree> RTV;

BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET(Point, double,
bg::cs::spherical_equatorial<bg::degree>, getX, getY, setX, setY)

template <typename Value, typename Options, typename Translator, typename
Box, typename Allocators>

class mbr_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 bgid::rtree::elements_type<internal_node>::type
elements_type;

    

    struct tempnode{

        tempnode(Box &b, internal_node &node){

            box = b;

            inode = node;

        }

        Box box;

        internal_node inode= nullptr;

    };

    

    // descending order

    struct cmp_tempnode{

        bool operator()(tempnode &node1, tempnode &node2){

            Box box1 = node1.box;

            Box box2 = node2.box;

            double area1 = (box1.m_max_corner.m_values[0] -
box1.m_min_corner.m_values[0]) * (box1.m_max_corner.m_values[1] -
box1.m_min_corner.m_values[1]);

            double area2 = (box2.m_max_corner.m_values[0] -
box2.m_min_corner.m_values[0]) * (box2.m_max_corner.m_values[1] -
box2.m_min_corner.m_values[1]);

            return area1 < area2;

        };

    };

    

public:

    int number;

    vector<Box> MBRs;

    void operator()(internal_node const& n)

    {

        elements_type const& elements = bgid::rtree::elements(n);

        

        if(number <= elements.size()){

            // should return all first level mbrs.

            for ( typename elements_type::const_iterator it =
elements.begin();

                 it != elements.end() ; ++it)

            {

                MBRs.push_back(it->first);

            }

        } else {

            // need further decompose, using priority queue

            priority_queue<tempnode, vector&lt;tempnode>, cmp_tempnode>
prqueue;

            for ( typename elements_type::const_iterator it =
elements.begin();

                 it != elements.end() ; ++it){

                Box box = it->first;

                internal_node ns = *(it->second);

                tempnode node(box, ns);

                prqueue.push(node);

            }

            while(prqueue.size() < number && prqueue.size() != 0){

                tempnode tnode = prqueue.top();

                prqueue.pop();

                elements_type subelements =
bgid::rtree::elements(tnode.inode);

                for (typename elements_type::const_iterator it =
subelements.begin(); it != subelements.end(); ++it){ // failed
!!!!!!!!!!!!!!!!!!!!!!!!!!!!

                    Box box = it->first;

                    internal_node ns = *(it->second);

                    tempnode node(box, ns);

                    prqueue.push(node);

                }

                // some other operation
            }

            

            // put MBRs from priority queue to vector

        }

    }

};

--
Sent from: http://boost-geometry.203548.n3.nabble.com/