Maybe the implementation you are looking at has bugs or is incorrect. Nobody is perfect.
Note that the R*-tree tries to minimize overlap enlargement, not overlap itself.
Some overlap will likely be unavoidable. If there already is overlap, you cannot expect this to decreate when inserting additional rectangles. But you can try to at least not increase the amount of overlap.
As for performance considerations, check whether you need to actually compute the intersection rectangles. Try to instead of computing area(intersection())
to do a function intersectionSize()
. This does make a difference. For example, if A.maxX = 1
and B.minX = 2
I can immediately give the intersection size of 0, without looking at any of the other dimensions.
Avoid eagerly precomputing all intersections etc. that you could need. Instead, compute only those that you actually need. Profile your code, and see if you can optimize the critical codepaths. There usually are some low hanging fruit there.