Boost logo

Geometry :

From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2019-10-14 00:47:27


W dniu 13.10.2019 o 10:18, Zhe Li via Geometry pisze:
> I'm trying to use an aggregate-Rtree
> ( to
> quickly find out the number of records given a predicate.
Sorry, the article is behind the paywall so I can't read all of it. Do I
understand correctly that what you want is to know how many geometries
are there in the query region? And therefore it would be possible to
store aggregated numbers of geometries covered by each node of the
R-tree and later during the query access only this number and therefore
avoiding searching deeper parts of the R-tree?
> Currently, I use the following code, but it will traverse every node it has,
> which is not the aggregate-Rtree manner (and quite inefficient).
> ============
> size_t cardinality = 0; // number of matches in set
> auto count_only =
> boost::make_function_output_iterator([&cardinality](bgi::rtree<MyPoint,
> bgi::linear&lt;16>>::value_type const&) { ++cardinality; });
> Box query_region(MyPoint(-91, -181), MyPoint(91, 181));
> rtree.query(bgi::intersects(query_region), count_only);
> ============
> I'm wondering is there any method to fast adapt the boost Rtree to an
> aggregate-Rtree? Or can
> boost Rtree directly provide such functionality (I cannot find it through
> the document)?
It depends what parts of the functionality would you want to use. Do you
use the associative part of the R-tree, i.e. insert() and remove()
methods? Or do you only create the rtree once with a constructor and
then perform queries multiple times?

Even if you use insert(), when the query is done WRT the creation of the
R-tree? Would it be acceptable to update the R-tree with inserts, then
traverse the whole R-tree updating the aggregates, and only after that
perform the query? Or are inserts done as frequently as queries and
therefore aggregating the information from lower-level nodes should be a
part of insert()?

The complexity of the task depends what parts of the R-tree you need. If
you do not need to modify the insertion and removal algorithms and only
create the aggregates for the whole tree before performing queries it
should be fairly simple. You'd have to define your own node types, tell
the R-tree to use them by specializing some templates and write your own
query algorithm and an algorithm updating the aggregates stored in all
of the nodes of the R-tree. If you need to aggregate information during
insertion and removal of elements this would require to modify or
implement your insert and remove algorithms (based on existing ones).
And if you want to go even further (which I'm not sure if it's covered
by the article) and want to decide how the elements and nodes should be
distributed across the R-tree structure based on aggregates different
than the MBRs (the classic R-tree uses only MBRs to decide where the new
elements should be inserted and how should the nodes be divided when
there is overflow) it would require to write more algorithms called when
balancing of the R-tree is done during insertion.


Geometry list run by mateusz at