Update R-tree to insert after query

Question

I would like to use the GEOS R-tree implementation to store the items of a growing structure. However, I also need to query from the tree during the growth process to make sure that growing substructures do not overlap.

This means that I need to alternatively query from and insert to the tree. However, qerying from GEOS R-tree triggers the build function, and inserting to a "built" tree is forbidden.

My question is therefore "is there a way around this?". From my (limited) understanding of R-trees, this should be possible: there are supposed to support this kind of dynamic update without having to be rebuilt from scratch, so how can I do that with GEOS? I've seen nothing in the C-API, and not much more than the cause of my problem:

// Cannot insert items into an STR packed R-tree after it has been built
assert(!built);

Answer 1

Code comments from JTS (from which GEOS is ported) summarize the R-tree implementation (and its design tradeoffs) as follows:

The STR packed R-tree is simple to implement and maximizes space utilization; that is, as many leaves as possible are filled to capacity. Overlap between nodes is far less than in a basic R-tree. However, once the tree has been built (explicitly or on the first call to #query), items may not be added or removed.

GEOS provides a Quadtree implementation that can be used when dynamic behavior is required, but it is not accessible through the GEOS C API.

Perhaps libspatialindex or boost::geometry would have an implementation that meets your needs.