Geometry Boost List: Re: [geometry] Question about packing

From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2021-08-31 09:53:02

Hi Panagiotis,

W dniu 31.08.2021 o 03:00, Panagiotis SIMATIS via Geometry pisze:
>
> Hello
>
> I would like to know which algorithm is used for packing the RTree.
>
> In the introduction both STR and TGS are referenced.
>
> Is the packing algorithm a hybrid of these two?
>
> If so, how does that work? If an explanation is tedious, I am happy to 
> look through the code if you could provide me the path.
>
Yest, it's a hybrid of these two algorithms and is also related to the 
creation algorithm of a variant of kd-tree (balanced kdtree storing 
points in contiguous memory space). The difference between r-tree and 
this kd-tree variant is that there are more children nodes per node and 
that objects different than points can be stored so if needed the R-tree 
algorithm works on centroids. Here is a short description and the code:

https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/pack_create.hpp#L107

Out of curiosity, why do you ask?

Adam